如何二叉链表存储的二叉树转换为一维数组结构

二叉树的链式存储结构有三个数据域如何在不增加存储的情况下变成循环链表

顺序存储结构二叉树存储结构的类型定义：＃define MAX_SIZE  100 typedef telemtype sqbitree[MAX_SIZE];12用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。  对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中，如图6-6(c)所示。 对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中，链式存储结构设计不同的结点结构可构成不同的链式存储结构。 12(1) 结点的类型及其定义 ① 二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域typedef s...全部

  顺序存储结构二叉树存储结构的类型定义：＃define MAX_SIZE  100 typedef telemtype sqbitree[MAX_SIZE];12用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。
   对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中，如图6-6(c)所示。 对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中，链式存储结构设计不同的结点结构可构成不同的链式存储结构。
  12(1) 结点的类型及其定义 ① 二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域typedef struct BTNode{  ElemType  data ;struct BTNode  *Lchild , *Rchild ;}BTNode ;1234② 三叉链表结点。
  除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点typedef struct BTNode_3{  ElemType  data ;struct BTNode_3  *Lchild , *Rchild , *parent ;}BTNode_3 ;1234遍历二叉树(Traversing Binary Tree)遍历二叉树(Traversing Binary Tree)：是指按指定的次序（规律）依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
   访问：指对结点做某种处理。如：输出信息、修改结点的值等。 次序（规律）：二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，所以在访问完一个结点之后，下一个被访问的结点面临着不同的选择。
  因此，需要寻找一种次序（规律），使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。
     若规定先左后右，则只有前三种情况三种情况，分别是：123DLR——先(根)序遍历。 LDR——中(根)序遍历。 LRD——后(根)序遍历。 已知二叉树，写出先序序列、中序序列、后序序列 已知先序序列和中序序列，确定二叉树 已知后序序列和中序序列，确定二叉树遍历算法对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。
   递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。 非递归算法中的控制是由设计者定义和使用堆栈来实现的。先序遍历二叉树1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 访问根结点； ⑵ 先序遍历左子树(递归调用本算法)； ⑶ 先序遍历右子树(递归调用本算法)。
  先序遍历的递归算法void  PreorderTraverse(BTNode  *T)     {    if  (T==NULL)                return;    visit(T->data) ;       /*  访问根结点  */PreorderTraverse(T->Lchild) ; //再先序遍历左子树PreorderTraverse(T->Rchild) ; //再先序遍历右子树}说明：1、visit()函数是访问结点的数据域，其要求视具体问题而定,可以是最简单的打印输出。
        2、树采用二叉链表的存储结构，用指针变量T来指向。12345678910112 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴ 访问p所指向的结点； ⑵ q=p->Rchild ，若q不为空，则q进栈； ⑶ p=p->Lchild ，若p不为空，转(1)，否则转(4)； ⑷ 退栈到p ，转(1)，直到栈空为止。
   算法实现：#define  MAX_STACK_SIZE  50void  PreorderTraverse( BTNode  *T){  BTNode  *Stack[MAX_STACK_SIZE ] ,*p=T, *q ;int  top=0 ;if  (T==NULL)  printf(“ Binary Tree is Empty! ”) ;else {  do      {  visit( p-> data ) ;   q=p->Rchild ;          if  ( q!=NULL )  stack[top ]=q ;          p=p->Lchild ;          if (p==NULL&& top!=0)             {top-- ；p=stack[top] ; }      }   while (p!=NULL) ;}}。
  收起