2023年6月22日发(作者：)
数据结构与算法系列研究五——树、⼆叉树、三叉树、平衡排序⼆叉树AVL树、⼆叉树、三叉树、平衡排序⼆叉树AVL⼀、树的定义 树是计算机算法最重要的⾮线性结构。树中每个数据元素⾄多有⼀个直接前驱，但可以有多个直接后继。树是⼀种以分⽀关系定义的层次结构。
a.树是n(≥0)结点组成的有限集合。{N.沃恩} (树是n(n≥1)个结点组成的有限集合。{}) 在任意⼀棵⾮空树中： ⑴有且仅有⼀个没有前驱的结点----根(root)。 ⑵当n>1时，其余结点有且仅有⼀个直接前驱。 ⑶所有结点都可以有0个或多个后继。 b. 树是n(n≥0)个结点组成的有限集合。 在任意⼀棵⾮空树中： ⑴有⼀个特定的称为根（root）的结点。 ⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的⼦集T1，T2，…，Tm。 每个集合本⾝⼜是⼀棵树，并且称为根的⼦树（subtree）
树的固有特性---递归性。即⾮空树是由若⼲棵⼦树组成，⽽⼦树⼜可以由若⼲棵更⼩的⼦树组成。 树的基本操作 1、InitTree(&T) 初始化 2、DestroyTree(&T) 撤消树 3、CreatTree(&T,F) 按F的定义⽣成树 4、ClearTree(&T) 清除 5、TreeEmpty(T) 判树空 6、TreeDepth(T) 求树的深度 7、Root(T) 返回根结点 8、Parent(T,x) 返回结点 x 的双亲 9、Child(T,x,i) 返回结点 x 的第i 个孩⼦ 10、InsertChild(&T,&p,i,x) 把 x 插⼊到 P的第i棵⼦树处
11、DeleteChild(&T,&p,i) 删除结点P的第i棵⼦树 12、traverse(T) 遍历 树的结点：包含⼀个数据元素及若⼲指向⼦树的分⽀。
●结点的度: 结点拥有⼦树的数⽬ ●叶结点: 度为零的结点 ●分枝结点: 度⾮零的结点 ●树的度: 树中各结点度的最⼤值 ●孩⼦: 树中某个结点的⼦树的根
●双亲: 结点的直接前驱
●兄弟: 同⼀双亲的孩⼦互称兄弟
●祖先: 从根结点到某结点j 路径上的所有结点（不包括指定结点）。
●⼦孙: 某结点的⼦树中的任⼀结点称为该结点的⼦孙
●结点层次: 从根结点到某结点 j 路径上结点的数⽬（包括结点j） ●树的深度: 树中结点的最⼤层次 ●有向树：结点间的连线是有向的。我们所讲的树都是有向的。
●有序树: 若树中结点的各⼦树从左到右是有次序的,称该树为有序树,否则为⽆序树 ●森林: 由 m 棵互不相交的树构成 F=(T1,T2,.......Tm) ⼀棵树去掉根结点后就变成了森林。 ⼆叉树的性质 ⼆叉树的第i层结点数最多为2^(i-1)个(i>0)。 深度为K的⼆叉树⾄多有(2^k)-1个结点(K>0)。 对任何⼀棵⼆叉树，设n0,n1,n2分别是度为0,1,2的结点数，则有：n0＝n2+1 证明:
∵ n= n0+ n1 + n2 (n为结点总数) b= n1 +2 n2 (b 为分⽀总数) b=n-1 (除根结点外,任⼀结点都有分⽀连⼊⽗结点) ∴ n=b+1= n1 +2 n2 +1= n0+ n1 + n2 整理得: n0 = n2 +1 具有n个结点的完全⼆叉树⾼度为
具有n个结点的完全⼆叉树具有如下特征： ① i=1 根结点，⽆双亲 i>1 其双亲结点为 (PARENT(i)= ) ② 2i>n 结点i⽆左孩，否则 lchild(i)=2i ③ 2i+1>n 结点i⽆右孩，否则 rchild(i)=2i+1⼆、⼆叉树三序遍历2.1．实验内容 1.⽤先序递归遍历法建⼆叉树 2.输出三序递归遍历与层次遍历节点访问次序,三序遍历要求使⽤⾮递归和递归两种 3.⽤先序，中序遍历序列建⼆叉树 4.后序遍历复制⼀棵⼆叉树,计算叶⼦个数和树的深度 5.输出后序递归遍历及层次遍历结果2.2.输⼊与输出 输⼊：输⼊建⽴⼆叉树的先序序列并且带‘#’，⽤以建树 输出 ：输出四种遍历的序列和⽤先序中序序列建成的⼆叉树2.3．关键数据结构与算法描述关键数据结构：⼆叉树的结构，节点，左孩⼦右孩⼦；栈的数据结构⽤以采⽤⾮递归⽅式遍历⼆叉树，循环队列的数据结构⽤以层次遍历⼆叉树。具体代码如下： 1 typedef struct TreeNode 2 { 3 ElemType elem; 4 struct TreeNode *LChild,*RChild; 5 }BiTree,*BinaryTree; //⼆叉树数据结构 6 typedef struct Queue 7 { 8 BinaryTree value[MAXSIZE]; 9 int front,rear;10 }LinkQueue; //队列数据结构11 typedef BinaryTree ElemType1; //为BinaryTree起别名12 typedef struct Stack13 {14 ElemType1 StackElem[MAXSIZE];15 int top;16 }STACK; //栈的数据结构View Code算法描述：⽤递归⽅法进⾏先序，中序，后序遍历都⼗分⽅便与简单，因为利⽤了树的左右结构。若树空时什么也不做，否则，按照便利的次序依次递归访问即可，如先序遍历：//先序递归遍历void PreOrderTraverse(BinaryTree tree){ if(tree!=NULL) { visit(tree);
PreOrderTraverse(tree->LChild); PreOrderTraverse(tree->RChild); }}View Code⽽对于⾮递归的三序遍历，就需要栈来做数据结构了，对于前序，中序遍历来说，只需要从根节点开始，⼀直往左⾛，直⾄最左边左⼦树为空，并且在这个过程中，若是先序遍历对于路上的节点都要访问并且⼊栈直⾄访问到到最左边的节点，然后退栈访问退栈节点的右⼦树；若是中序遍历则只需不断的向左⾛并且⼊栈但不访问，直⾄最左边，然后访问最左边节点。然后退栈并访问该节点，⽤同样的⽅法访问退栈节点的右⼦树。最后若栈为空，则访问完成。故此设⽴⼀个⼀直向左⾛访问并且⼊栈的函数如下（中序与此类似，暂不赘述）：/***⼀直向左⾛直⾄获得最左边的指针*************/BinaryTree GofarleftVisit(BinaryTree tree,STACK *s){ if(!tree) return NULL; //若⽆树直接返回 BinaryTree p=tree; visit(p); //先访问逻辑根节点 while(p->LChild)
{ push(s,p); //把访问之后的⼊栈以便访问右⼦树 visit(p->LChild); //访问左⼦树 p=p->LChild; //不断向左移动直⾄为空 } return p;}⾮递归先序遍历的算法为：//⽤⾮递归法先序访问void PreOrder(BinaryTree tree){ if(!tree) return ; STACK s; InitStack(&s);
BinaryTree p; p=GofarleftVisit(tree,&s); //获得最左指针 while(p) { if(p->RChild) p=GofarleftVisit(p->RChild,&s); //右边继续向左⾛ else if(!IsEmptyStack(&s))
{ pop(&s,p); } else p=NULL; //栈空时退出 }}View Code 对于⾮递归后序遍历，根据其特点，先遍历左⼦树再遍历右⼦树，最后访问根节点。则需⽤两个指针cur和pre来分别标记当前指针和前⼀个指针的位置。注意压栈时先压根节点，再压右⼦树，最后左⼦树。若当前指针cur指向叶⼦节点则需访问，或者pre指针不为空并且pre指向的节点恰是当前指针指向的左或右节点则代表pre⼦树的下⼀层已经⽆树，并且若等于左指针则右边已⽆节点，（右边若有则访问完左边之后必然先访问右边⽽不会跳到头节点）；若等于右节点，则左边已访问完或⽆左边（因右边先压栈）。具体代码如下：//⾮递归后序遍历void postOrder(BinaryTree tree)
{ STACK s; InitStack(&s); BinaryTree cur,pre=0; push(&s,tree); /*****⽤两个指针来判断，如果为叶⼦节点或者左右⼦树都访问过就访问该节点****/ while(!IsEmptyStack(&s)) { cur=gettop(&s); if((cur->LChild==NULL&&cur->RChild==NULL)|| (pre!=NULL&&(pre==cur->RChild||pre==cur->LChild))) { //注意pre只要与⼀个相等，若为左⼦树则⽆右⼦树； //若为右⼦树则必然访问过左⼦树或⽆左⼦树 visit(cur); //如果当前结点为叶⼦节点或者孩⼦节点都已被访问就访问 pop(&s,cur); pre=cur; //标记上次被访问的节点 } else { if(cur->RChild!=NULL) push(&s,cur->RChild); //注意先把右⼦树⼊栈再⼊左⼦树，才能保持先访问左⼦树后访问右⼦树，后进先出！ if(cur->LChild!=NULL)
push(&s,cur->LChild); } }
}View Code
接下来是⽤队列数据结构层次遍历。其实就是迭代的过程，先访问头节点，然后进左⼉⼦，右⼉⼦。每次出队列后都要访问该节点，然后再看该节点是否有左右⼦树若有则按照先左后右的顺序进队排在队尾等待遍历然后不断地循环迭代直⾄队为空则遍历结束。很容易理解！具体代码如下：//队列进⾏的⼆叉树层次遍历void HierarchyBiTree(BinaryTree tree){ LinkQueue Q; //注意此处不能是指针 InitQueue(&Q); BinaryTree p=tree;
if (tree==NULL) return ;
visit(p);
if (p->LChild) EnQueue(&Q,&p->LChild); //若指针不空则⼊队列 if (p->RChild) EnQueue(&Q, &p->RChild); //若指针不空则⼊队列 while (!IsEmpty(&Q))
{
DeQueue(&Q, &p); //弹出指针进⾏访问 visit(p);
if (p->LChild)
EnQueue(&Q, &p->LChild); //对指针所指的结构进⾏判断若左右⼦树不空 if (p->RChild) EnQueue(&Q, &p->RChild); //则先进左⼦树，后进右⼦树，以保证从左到右遍历 }}View Code
然后关于⼆叉树的复制，先复制左⼦树，然后复制右⼦树，最后复制头节点；在复制左右⼦树的时候同时也是复制树，故可⽤递归实现。同理，关于求叶⼦节点，求树的深度也是如此⽤递归即可实现，复制树的具体代码如下：/************后序遍历复制⼀棵⼆叉树*************/void CopyBiTree(BinaryTree tree,BinaryTree &newtree){ BinaryTree lchild,rchild; if(!tree) { newtree=NULL; } if(tree->LChild)//若左⼦树存在则递归复制 { CopyBiTree(tree->LChild,lchild); } else { lchild=NULL; //否则为零 } if(tree->RChild) { CopyBiTree(tree->RChild,rchild); } else { rchild=NULL; } newtree=(BinaryTree)malloc(sizeof(BiTree)); newtree->elem=tree->elem; newtree->LChild=lchild;
newtree->RChild=rchild;}View Code
最后就是根据先序和中序序列建树，有⼀定的难度需要⽤到递归和分治法的⼀些知识。⾸先可以证明⽤先序，中序遍历序列是可以还原⼆叉树的，因为根据先序序列可以很清楚的知道⼆叉树的根节点就是第⼀个元素，然后以这个节点把中序序列分成两半，在这个节点左边的必是左⼦树（因为是中序序列），⽽在其右边的是右⼦树，⽽左⼦树右⼦树有是⼀个树，故可以在更⼩的范围内找到左⼦树的根节点，在以该节点为分界点，在更⼩的范围内查找下去，右⼦树也是如此。在递归的过程中要注意进⾏⽐较的两个序列长度必然要相等，递归终⽌的条件就是左边分到不能再⽐，右边也向右不能再⽐为⽌。这样也就在递归中建⽴了⼆叉树。具体代码如下：//⾸先得到中序序列⼆分后左边的长度int get_left_len(int rootpos,int in_begin,int in_end,char * pre_order,char * in_order ){ for(int i = in_begin; i <= in_end; i++) { if(in_order[i] == pre_order[rootpos]) { return i-in_begin; //以双亲节点为分界点划分，返回左边的真实长度 } } return -1; //若没有则返回负值，⽤于判断}void creat(BinaryTree *pnode,int pre_begin,int pre_end,int in_begin,int in_end, char * pre_order,char * in_order){ *pnode =(BinaryTree)malloc(sizeof(BiTree)); //申请空间 BinaryTree temp = *pnode; //创建遍历指针 temp->elem = pre_order[pre_begin]; //开始必为根节点 temp->LChild = NULL; //⼀定要初始化为0 temp->RChild = NULL; if(pre_begin == pre_end) { return ; //只有⼀个节点，则已创建完毕 } int left_len = get_left_len(pre_begin,in_begin,in_end,pre_order,in_order); if(left_len > 0) //若没有会返回-1；若为0，则上⾯已创建；否则创建左⼦树 { creat(&temp->LChild,pre_begin+1,pre_begin+left_len, in_begin,in_begin+left_len-1,pre_order,in_order); } if(left_len < (in_end - in_begin)) //若left_len+inbegin>in_end-1则已经结束，否则创建右⼦树 { creat(&temp->RChild,pre_begin+left_len+1,pre_end, in_begin+left_len+1,in_end,pre_order,in_order); }}View Code2.4.测试与理论 具体的测试与理论见下图测试数据⼀：先序遍历：ABDFCEG中序遍历：DFBAECG后序遍历：FDBEGCA输⼊数据: ABD#F###CE##G##对于测试先序和中序序列建树的序列为char * pre_order = "ABDEGJCFHIK";//先序序列char * in_order = "DBGJEACFIKH"; //中序序列输出结果截图：测试数据⼆： 先序遍历：ABDEGJCFHIK中序遍历：DBGJEACFIKH后序遍历：DJGEBKIHFCA输⼊序列：ABD##EG#J###C#F#HI#K###输出结果见下图：2.5.附录 1 #include "stdio.h" 2 #include "stdlib.h" 3 #include "iostream" 4 using namespace std; 5 #define MAXSIZE 100 6 #define OK 1 7 #define NO 0 8 /**********************************************/ 9 typedef int status; 10 typedef char ElemType; 11 typedef struct TreeNode 12 { 13 ElemType elem; 14 struct TreeNode *LChild,*RChild; 15 }BiTree,*BinaryTree; //⼆叉树数据结构 16 typedef struct Queue 17 { 18 BinaryTree value[MAXSIZE]; 19 int front,rear; 20 }LinkQueue; //队列数据结构 21 typedef BinaryTree ElemType1; //为BinaryTree起别名 22 typedef struct Stack 23 { 24 ElemType1 StackElem[MAXSIZE]; 25 int top; 26 }STACK; //栈的数据结构 27 /************************************************/ 28 /*************以下是循环队列的定义**************/ 29 void InitQueue( LinkQueue *q) 30 { 31 q->front=-1; //注意初始化为-1 32 q->rear=-1; 33 } 34 status IsEmpty(LinkQueue *q) 35 { 36 if(q->rear==q->front) 37 return OK; //循环队列开始为空或者运⾏时出队的光标指到⼊队的光标 38 else 39 return NO; 40 } 41 status IsFull(LinkQueue *q) 42 { 43 if(q->front==(q->rear+1)%MAXSIZE) 44 return OK; //队满的标志就是q->front指向哑元且哑元左边为q->rear 45 else 46 return NO; 47 } 48 void EnQueue(LinkQueue *q, BinaryTree *tree) 49 { 50 if(IsFull(q)) 50 if(IsFull(q)) 51 return ; //⼊队操作，若队满则不能⼊队 52 q->rear=(++(q->rear))%MAXSIZE; //注意⼀定要先⾃加，再赋值 53 q->value[q->rear]=*tree; 54 } 55 void DeQueue(LinkQueue *q, BinaryTree *tree) 56 { 57 if(IsEmpty(q)) 58 return ; 59 q->front=(++q->front)%MAXSIZE; 60 *tree=q->value[q->front]; //注意tree是指向指针的指针，不然将出错
61 } 62 /**************************************************************/ 63 /******************以下是栈的定义******************************/ 64 void InitStack(STACK *s) 65 { 66 s->top=-1; //初始化 67 } 68 void push(STACK *s,ElemType1 e) 69 { 70 if(s->top>=MAXSIZE-1) 71 return ; 72 s->StackElem[++s->top]=e; //压栈 73 } 74 void pop(STACK *s,ElemType1 &e) 75 { 76 if(s->top<=-1) 77 return ; 78 e=s->StackElem[s->top]; //出栈 79 s->top--; 80 } 81 ElemType1 gettop(STACK *s) 82 { 83 return s->StackElem[s->top]; //获得栈顶元素 84 } 85 status IsEmptyStack(STACK *s) //判断是否栈空 86 { 87 if(s->top==-1) 88 return OK; 89 else 90 return NO; 91 } 92 /******************************************************************/ 93 /***************递归创建⼆叉树，要求读⼊先序序列和‘#’****************/ 94 BinaryTree CreatTree(BinaryTree tree) 95 { 96 char ch; 97 if((ch=getchar())=='#') 98 tree=NULL; 99 else100 {101 tree=(BinaryTree)malloc(sizeof(BiTree));102 tree->elem=ch;103 tree->LChild=CreatTree(tree->LChild);104 tree->RChild=CreatTree(tree->RChild);105 }106 return tree;107 }108 //最简单的访问⼆叉树109 void visit(BinaryTree tree)110 {111 printf("%c ",tree->elem);112 }113 /**************以下是四种对⼆叉树的遍历⽅法***********************/114 //先序递归遍历115 void PreOrderTraverse(BinaryTree tree)116 {117 if(tree!=NULL)118 {119 visit(tree);
120 PreOrderTraverse(tree->LChild);121 PreOrderTraverse(tree->RChild);122 }123 }124
125 /***⼀直向左⾛直⾄获得最左边的指针*************/126 BinaryTree GofarleftVisit(BinaryTree tree,STACK *s)127 {128 if(!tree)129 return NULL; //若⽆树直接返回130 BinaryTree p=tree;131 visit(p); //先访问逻辑根节点132 while(p->LChild)
133 {134 push(s,p); //把访问之后的⼊栈以便访问右⼦树135 visit(p->LChild); //访问左⼦树136 p=p->LChild; //不断向左移动直⾄为空137 }138 return p;139 }140 //⽤⾮递归法先序访问141 void PreOrder(BinaryTree tree)142 {143 if(!tree)144 return ;145 STACK s;146 InitStack(&s);
147 BinaryTree p;148 p=GofarleftVisit(tree,&s); //获得最左指针149 while(p)150 {151 if(p->RChild)152 p=GofarleftVisit(p->RChild,&s); //右边继续向左⾛153 else154 if(!IsEmptyStack(&s))
155 {156 pop(&s,p);157 }158 else159 p=NULL; //栈空时退出160 }161 }162
163 //中序递归遍历
164 void InOrderTraverse(BinaryTree tree)165 {166 if(tree!=NULL)167 {168 InOrderTraverse(tree->LChild);169 visit(tree);170 InOrderTraverse(tree->RChild);171 }172 }173 //中序⾮递归遍历⼆叉树174 BinaryTree gofarleft(BinaryTree tree,STACK *s)175 {176 if(!tree)177 return NULL;178 BinaryTree p=tree;179 while(p->LChild) //⼀直向左⾛，不断⼊栈180 {181 push(s,p);
182 p=p->LChild;183 }184 return p;185 }186 void InOrder(BinaryTree tree)187 {188 if(!tree)189 return ;190 STACK s;191 InitStack(&s);192 BinaryTree p;193 p=gofarleft(tree,&s);194 while(p)195 {196 visit(p); //先访问最左元素197 if(p->RChild)198 p=gofarleft(p->RChild,&s);199 else200 if(!IsEmptyStack(&s))201 {202 pop(&s,p); //向上追溯203 }204 else205 p=NULL; //栈空时恰访问完206 }207 }208 /************************************/209 209
210 //后序递归遍历211 void PostOrderTraverse(BinaryTree tree)212 {213 if(tree!=NULL)214 {215 PostOrderTraverse(tree->LChild);216 PostOrderTraverse(tree->RChild);217 visit(tree);218 }219 }220 //⾮递归后序遍历221 void postOrder(BinaryTree tree)
222 {223 STACK s;224 InitStack(&s);225 BinaryTree cur,pre=0;226 push(&s,tree);227 /*****⽤两个指针来判断，如果为叶⼦节点或者左右⼦树都访问过就访问该节点****/228 while(!IsEmptyStack(&s))229 {230 cur=gettop(&s);231 if((cur->LChild==NULL&&cur->RChild==NULL)||232 (pre!=NULL&&(pre==cur->RChild||pre==cur->LChild)))233 { //注意pre只要与⼀个相等，若为左⼦树则⽆右⼦树；234 //若为右⼦树则必然访问过左⼦树或⽆左⼦树235 visit(cur); //如果当前结点为叶⼦节点或者孩⼦节点都已被访问就访问
236 pop(&s,cur);237 pre=cur; //标记上次被访问的节点
238 }239 else240 {241 if(cur->RChild!=NULL)242 push(&s,cur->RChild); //注意先把右⼦树⼊栈再⼊左⼦树，才能保持先访问左⼦树后访问右⼦树243 if(cur->LChild!=NULL)
244 push(&s,cur->LChild);245 }246 }
247 }248 /******************************************************/249 //队列进⾏的⼆叉树层次遍历250 void HierarchyBiTree(BinaryTree tree)251 {252 LinkQueue Q; //注意此处不能是指针253 InitQueue(&Q);254 BinaryTree p=tree;
255 if (tree==NULL)256 return ;
257 visit(p);
258 if (p->LChild)259 EnQueue(&Q,&p->LChild); //若指针不空则⼊队列260 if (p->RChild)261 EnQueue(&Q, &p->RChild); //若指针不空则⼊队列262 while (!IsEmpty(&Q))
263 {
264 DeQueue(&Q, &p); //弹出指针进⾏访问265 visit(p);
266 if (p->LChild)
267 EnQueue(&Q, &p->LChild); //对指针所指的结构进⾏判断若左右⼦树不空268 if (p->RChild)269 EnQueue(&Q, &p->RChild); //则先进左⼦树，后进右⼦树，以保证从左到右遍历270 }271 }272 /***************************************************/273 /********计算叶⼦节点数*************/274 void CountLeaf(BinaryTree tree,int &count)275 {276 if(tree)277 {278 if((tree->LChild==NULL)&&(tree->RChild==NULL))279 count++;280 CountLeaf(tree->LChild,count);281 CountLeaf(tree->RChild,count);282 }283 }284 /************计算树的深度**************/285 int TreeDepth(BinaryTree tree)286 {287 int depth,ldepth,rdepth;288 if(!tree)289 depth=0;290 else291 {292 ldepth=TreeDepth(tree->LChild);293 rdepth=TreeDepth(tree->RChild);294 depth=(ldepth>rdepth ? ldepth:rdepth)+1;
295 }296 return depth;297 }298 /************后序遍历复制⼀棵⼆叉树*************/299 void CopyBiTree(BinaryTree tree,BinaryTree &newtree)300 {301 BinaryTree lchild,rchild;302 if(!tree)303 {304 newtree=NULL;305 }306 if(tree->LChild)//若左⼦树存在则递归复制307 {308 CopyBiTree(tree->LChild,lchild);309 }310 else311 {312 lchild=NULL; //否则为零313 }314 if(tree->RChild)315 {316 CopyBiTree(tree->RChild,rchild);317 }318 else319 {320 rchild=NULL;321 }322 newtree=(BinaryTree)malloc(sizeof(BiTree));323 newtree->elem=tree->elem;324 newtree->LChild=lchild;
325 newtree->RChild=rchild;326 }327 /*****************************************************/
328 /*************根据先序和中序序列建⼆叉树*******************/329 //⾸先得到中序序列⼆分后左边的长度330 int get_left_len(int rootpos,int in_begin,int in_end,char * pre_order,char * in_order )331 {332 for(int i = in_begin; i <= in_end; i++)333 {334 if(in_order[i] == pre_order[rootpos])335 {336 return i-in_begin; //以双亲节点为分界点划分，返回左边的真实长度337 }338 }339 return -1; //若没有则返回负值，⽤于判断340 }341
342 void creat(BinaryTree *pnode,int pre_begin,int pre_end,int in_begin,int in_end,343 char * pre_order,char * in_order)344 {345 *pnode =(BinaryTree)malloc(sizeof(BiTree)); //申请空间346 BinaryTree temp = *pnode; //创建遍历指针347 temp->elem = pre_order[pre_begin]; //开始必为根节点348 temp->LChild = NULL; //⼀定要初始化为0349 temp->RChild = NULL;350 if(pre_begin == pre_end)351 {352 return ; //只有⼀个节点，则已创建完毕353 }354 int left_len = get_left_len(pre_begin,in_begin,in_end,pre_order,in_order);355 if(left_len > 0) //若没有会返回-1；若为0，则已创建；否则创建左⼦树356 {357 creat(&temp->LChild,pre_begin+1,pre_begin+left_len,358 in_begin,in_begin+left_len-1,pre_order,in_order);359 }360 if(left_len < (in_end - in_begin)) //若left_len+inbegin>in_end-1则已经结束，否则创建右⼦树361 {362 creat(&temp->RChild,pre_begin+left_len+1,pre_end,363 in_begin+left_len+1,in_end,pre_order,in_order);364 }365 }366 /*********************************************************/367 void MainMenu( )368 {368 {369 BinaryTree tree=0,newtree;370 int count=0,depth;371 /**********display***********/372 tree=CreatTree(tree);373 printf("前序遍历：n");374 PreOrderTraverse(tree);375 printf("n中序遍历：n");376 InOrderTraverse(tree);377 printf("n后序遍历：n");378 PostOrderTraverse(tree);379 printf("n层次遍历⼆叉树:n");380 HierarchyBiTree(tree);
381 printf("n⾮递归先序遍历n");382 PreOrder(tree);383 printf("n⾮递归中序遍历n");384 InOrder(tree);385 printf("n⾮递归后序遍历n");386 postOrder(tree);387 /********algorithm************/388 CountLeaf(tree,count);389 printf("n叶⼦个数为:%dn",count);390 depth=TreeDepth(tree);391 printf("n树的深度为：%dn",depth);392 printf("n复制⼆叉树后的结果：n");393 CopyBiTree(tree,newtree);394 printf("n先序遍历：n");395 PreOrderTraverse(newtree);396 printf("n中序遍历：n");397 InOrderTraverse(newtree);398 printf("n后序遍历：n");399 PostOrderTraverse(newtree);400 printf("n层次遍历⼆叉树:n");401 HierarchyBiTree(newtree);
402 /*********⽤先序和中序建树并输出*************/403 char * pre_order = "ABDEGJCFHIK";//先序序列404 char * in_order = "DBGJEACFIKH"; //中序序列405 BinaryTree root = NULL;406 creat(&root,0,strlen(pre_order)-1,0,strlen(in_order)-1,pre_order,in_order);407 printf("⽤先序和中序建树后的结果：n");408 printf("n后序遍历：n");409 PostOrderTraverse(root);410 printf("n层次遍历⼆叉树:n");411 HierarchyBiTree(root);
412 printf("n操作结束n");413 }414
415 /* 测试数据 ABD#F###CE##G## */416 /* 测试数据 ABD##EG#J###C#F#HI#K### */
417 int main()418 {419 MainMenu();420 return 0;421 }422
View Code三、三叉树——带双亲指针的⼆叉树⾮递归遍历3.1．实验内容 建⽴三叉链表存储结构，实现三序⾮递归遍历。3.2．输⼊与输出 输⼊：带有“#”的⼆叉树字符串。 输出：三序遍历的结果。3.3．关键数据结构与算法描述关键数据结构： 三叉链表的数据结构如下：typedef char ElemType;typedef struct TriTree
{ ElemType elem; struct TriTree *lchild,*rchild,*parent;}*TRITREE,TriTreeNode;
算法描述： 三叉链表的创建和⼆叉树创建基本相同，只不过增加了双亲指针就要给其赋值，根节点的双亲为NULL,其他节点在先序递归遍历建⼆叉树的时候赋值，若该节点有左右⼦树，则左右节点的双亲指针就指向该节点。具体代码为：if(tree->lchild){ tree->lchild->parent=tree;//指向双亲节点}if(tree->rchild){ tree->rchild->parent=tree;//指向双亲节点}View Code然后是三序遍历，1.⾸先是先序⾮递归遍历，先遍历头节点，再遍历左⼦树，然后是右⼦树，注意到从此处的双亲指针的⽤法，可以回溯。因此，当树不为空的时候，⾸先遍历该节点，然后看是否有左⼦树，若有则指向左⼦树，若⽆左⼦树，则看是否有右⼦树，若有则指向右⼦树。如果左右⼦树都不存在，则是叶⼦节点需要回溯。选定⼀个“记录指针p”，永远指向遍历指针刚刚⾛过的位置。⽽遍历指针则回溯。若遍历指针的左⼉⼦为p，并且右⼉⼦不空则遍历右⼦树；若回溯到根节点的双亲则结束。否则继续回溯。直⾄两种情况出现⼀种。⼀直循环就可实现先序遍历。代码如下： 1 //⾮递归先序遍历三叉链表 2 void preorder(TRITREE tree) 3 { 4 TRITREE p; 5 while(tree) //有树就循环 6 { 7 visit(tree); //访问根节点 8 if(tree->lchild) 9 {10 tree=tree->lchild ; //⼀定要先看左⼦树再看右⼦树11 }12 else if(tree->rchild )13 {14 tree=tree->rchild ; //进⼊下⼀循环15 }16 else
17 while(1)
18 {19 p=tree;20 tree=tree->parent;//形成连接结构21 if(!tree)22 break; //若⽆树则退出23 if(tree->lchild == p&&tree->rchild )24 {
25 tree=tree->rchild ; //访问完左⼦树，访问右⼦树26 break;27 }28
29 }30 }31 }View Code2.中序遍历思想是先遍历左⼦树再遍历头节点，最后遍历右⼦树。因回溯时有左⼦树和右⼦树两种情况，则⽤⼀个标量来记录mark=0代表未遍历左⼦树，mark=1代表已遍历左⼦树。则当树不空时开始循环，mark开始置为零。要是没遍历左⼦树则要先遍历左⼦树。左⼦树遍历之后mark置为⼀。然后看以该节点为根的右⼦树是否存在若存在则遍历，若不存在则回溯，同样设p跟随遍历节点，若是左边回溯则遍历该节点，若是右边回溯则继续向上推进，若推进到最上⾯则遍历结束。具体代码如下： 1 //⾮递归中序遍历三叉链表 2 void inorder(TRITREE tree) 3 { 4 TRITREE p; 5 int mark=0;//表⽰左⼦树未遍历 6 while(tree) 7 { 8 if(mark==0) 9 {10 if(tree->lchild)11 {12 tree=tree->lchild;//⼀直到最左边的节点13 }14 else15 {16 mark=1; //然后标记左边已遍历，其实在下⾯遍历17 }18 }19 else20 {21 visit(tree); //遍历标记节点22 if(tree->rchild)23 {24 tree=tree->rchild;//若有右⼦树，则移位25 mark=0; //标记未遍历，回到上步26 }27 else28 { //若⽆右⼦树，则回溯29 while(1)
30 {31 p=tree;32 tree=tree->parent;33 if(!tree)34 break;35 if(tree->lchild == p)36 {
37 mark=1;//表⽰左孩⼦遍历过38 break;39 }40 }41
42 }43 }44 }45 }
View Code3.后序遍历需要设定⼀个标量flag分别表⽰（0）：左⼦树未遍历（1）：左⼦树已遍历，该遍历右⼦树；（2）右⼦树已遍历，应遍历头节点。则开始flag=0；开始遍历遍历完左⼦树flag=1；开始遍历右⼦树，此时若右⼦树还是棵树则要flag=0；判断这棵树的左右⼦树情况直⾄右边也被遍历则要遍历头节点置flag=2；开始访问。访问完后要进⾏回溯，若是从左边过来的就要访问右边，若是从右边过来的则要访问该节点。⼀直循环就可得到结果，具体代码如下：//⾮递归后序遍历三叉链表void postorder(TRITREE tree){ int flag=0;//标志变量可取0，1，2三种状态 TRITREE p; while(tree) { switch(flag) { case 0://左⼦树未遍历 if(tree->lchild) tree=tree->lchild; else flag=1; break; case 1://右⼦树未遍历 if(tree->rchild) { tree=tree->rchild; flag=0; //右⼦树可能是⼀棵树，重新遍历树的左孩⼦ } else { flag=2; //没有右⼦树则开始遍历头节点 } break; case 2: //开始遍历头节点 visit(tree); p=tree; tree=tree->parent; //回溯判断 if(tree) { if(p==tree->lchild) { flag=1;//左孩⼦已遍历，开始右⼦树 } else { flag=2;//右孩⼦已遍历，开始遍历头节点 } } break; } }}View Code
3.4.测试与理论 测试数据：先序遍历：ABDFCEG中序遍历：DFBAECG后序遍历：FDBEGCA输⼊数据: ABD#F###CE##G##结果见下图显⽰:3.5.附录 1 #include "stdio.h" 2 #include "iostream.h" 3 #include "stdlib.h" 4 typedef char ElemType; 5 typedef struct TriTree 6 { 7 ElemType elem; 8 struct TriTree *lchild,*rchild,*parent; 9 }*TRITREE,TriTreeNode; 10
11
12 //先序遍历创建三叉链表 13 TRITREE CreatTree(TRITREE &tree) 14 { 15 char ch; 16 if((ch=getchar())=='#') 17 tree=NULL; 18 else 19 { 20 tree=(TRITREE)malloc(sizeof(TriTreeNode)); 20 tree=(TRITREE)malloc(sizeof(TriTreeNode)); 21 tree->elem=ch; 22 tree->lchild=CreatTree(tree->lchild); 23 tree->rchild=CreatTree(tree->rchild); 24 //增加parent指针，若⽆左右孩⼦则不⽤赋值 25 if(tree->lchild) 26 { 27 tree->lchild->parent=tree;//指向双亲节点 28 } 29
30 if(tree->rchild) 31 { 32 tree->rchild->parent=tree;//指向双亲节点 33 } 34 } 35 return tree; 36 } 37 //最简单的访问⼆叉树 38 void visit(TRITREE tree) 39 { 40 printf("%c ",tree->elem); 41
42 } 43 //⾮递归先序遍历三叉链表 44 void preorder(TRITREE tree) 45 { 46 TRITREE p; 47 while(tree) //有树就循环 48 { 49 visit(tree); //访问根节点 50 if(tree->lchild) 51 { 52 tree=tree->lchild ; //⼀定要先看左⼦树再看右⼦树 53 } 54 else if(tree->rchild ) 55 { 56 tree=tree->rchild ; //进⼊下⼀循环 57 } 58 else
59 while(1)
60 { 61 p=tree; 62 tree=tree->parent;//形成连接结构 63 if(!tree) 64 break; //若⽆树则退出 65 if(tree->lchild == p&&tree->rchild ) 66 {
67 tree=tree->rchild ; //访问完左⼦树，访问右⼦树 68 break; 69 } 70
71 } 72 } 73 } 74 //⾮递归中序遍历三叉链表 75 void inorder(TRITREE tree) 76 { 77 TRITREE p; 78 int mark=0;//表⽰左⼦树未遍历 79 while(tree) 80 { 81 if(mark==0) 82 { 83 if(tree->lchild) 84 { 85 tree=tree->lchild;//⼀直到最左边的节点 86 } 87 else 88 { 89 mark=1; //然后标记左边已遍历，其实在下⾯遍历 90 } 91 } 92 else 93 { 94 visit(tree); //遍历标记节点 95 if(tree->rchild) 96 { 97 tree=tree->rchild;//若有右⼦树，则移位 98 mark=0; //标记未遍历，回到上步 99 }100 else100 else101 { //若⽆右⼦树，则回溯102 while(1)
103 {104 p=tree;105 tree=tree->parent;106 if(!tree)107 break;108 if(tree->lchild == p)109 {
110 mark=1;//表⽰左孩⼦遍历过111 break;112 }113 }114
115 }116 }117 }118 }
119
120 //⾮递归后序遍历三叉链表121 void postorder(TRITREE tree)122 {123 int flag=0;//标志变量可取0，1，2三种状态124 TRITREE p;125 while(tree)126 {127 switch(flag)128 {129 case 0://左⼦树未遍历130 if(tree->lchild)131 tree=tree->lchild;132 else133 flag=1;134 break;135 case 1://右⼦树未遍历136 if(tree->rchild)137 {138 tree=tree->rchild;139 flag=0; //右⼦树可能是⼀棵树，重新遍历树的左孩⼦140 }141 else142 {143 flag=2; //没有右⼦树则开始遍历头节点144 }145 break;146 case 2: //开始遍历头节点147 visit(tree);148 p=tree;149 tree=tree->parent; //回溯判断150 if(tree)151 {152 if(p==tree->lchild)153 {154 flag=1;//左孩⼦已遍历，开始右⼦树155 }156 else157 {158 flag=2;//右孩⼦已遍历，开始遍历头节点159 }160 }161 break;162 }163 }164 }165
166 //abd#f###ce##g##167 int main()168 {169 TRITREE tree;170
171 tree=CreatTree(tree);172 tree->parent=0;173 cout< int data;//信息 int bf;//平衡因⼦ struct BSTNode *lchild,*rchild; //平衡树左右⼉⼦指针 }BSTNode,*BSTree;//平衡⼆叉排序树结构的定义 核⼼算法： 建⽴平衡排序⼆叉树算是算法中⽐较复杂的⼀个了，但是找到核⼼之后，也就只是⽐较复杂⼀些罢了，多练习⼀下即可。那核⼼是什么呢？要回答这个问题，就要深刻理解“平衡”和“排序”两个词的含义。顾名思义，平衡⼆叉树加上排序⼆叉树即是所要建的树。1.平衡⼆叉树要求每⼀个节点的左⼦树深度减去右⼦树的深度的绝对值要⼩于1。2.排序⼆叉树要求按照中序遍历该⼆叉树得到从⼩到⼤排序的序列。因此在每插⼊⼀个结点的时候都要判断是否平衡，1.若平衡则按照排序⼆叉树的⽅法插⼊之，然后刷新平衡因⼦即可。2.重要是不平衡的时候就要从最接近的不平衡的地⽅旋转的让它平衡，这样继续下去，不断插⼊就可以得到排序平衡⼆叉树。 下⾯主要解释⼀下旋转⽅法：旋转共有4种⽅式，其实，最核⼼的只有两种基本操作即是L_Rotate( )和R_Rotate( )，分别是左旋和右旋。对于LL型，即是最先出错的节点平衡因⼦是2，左⼉⼦平衡因⼦是1，运⽤⼀次右旋操作再刷新平衡因⼦即可。根据镜像对称原则，RR型与此是对应的，如法炮制即可。重要的并且复杂的是LR和RL操作，这两个操作也是镜像对称的只讲⼀个即可。就⽐如LR吧，最先出错的节点的平衡因⼦是2，该节点的左孩⼦的平衡因⼦是-1.则要对左孩⼦为根的⼦树进⾏左旋，然后对该最近节点进⾏右旋，刷新平衡因⼦即可。具体算法如下： 1 /**************************两个基本操作*****************************/ 2 void L_Rotate(BSTree &p) 3 { 4 //对以*p为根的⼆叉排序树做左旋处理，处理之后p指向新的树根结点 5 //和R_Rotate()镜像对称 6 BSTree rc; 7 rc = p->rchild; 8 p->rchild = rc->lchild; 9 rc->lchild = p; 10 p = rc; 11 } 12 void R_Rotate(BSTree &p) 13 { 14 //对以*p为根的⼆叉排序树做右旋处理，处理之后p指向新的树根结点 15 //注意此处引⽤的好处就是不⽤再出现双亲指针 16 BSTree lc; 17 lc=p->lchild; //指向B的位置 18 p->lchild=lc->rchild; //此处转换仍保持中序遍历不变性 19 lc->rchild=p; //更改a的指针位置 20 p=lc; //lc变成新的a 21 } 22 /**********************四个旋转操作，每两个在⼀起*****************/ 23 //包含LL和LR 24 void LeftBalance(BSTree &T) 25 { //对已*T为根的⼆叉排序树做左平衡旋转处理 26 BSTree lc,rd; 27 lc = T->lchild; //lc调整左边 28 switch(lc->bf) 29 { 30 case LH://若是左边⾼则为LL型，只需旋转即可 31 T->bf = lc->bf = EH; //旋转后平衡因⼦均为0 32 R_Rotate(T); //LL型需要右旋转 33 break; 34 case RH://若是右边⾼，则为LR型，需分两步调整 35 rd = lc->rchild; //找到不确定因⼦rd 36 switch(rd->bf)//对不确定因⼦进⾏讨论 37 { 38 case LH://左边⾼调整后 39 T->bf = RH;//根节点右边变⾼ 40 lc->bf = EH; //lc变平衡 41 break; 42 case EH://rd有左右节点 43 T->bf = lc->bf = EH; //调整后持平 44 break; 45 case RH://右边⾼ 46 T->bf = EH;//根节点平衡 47 lc->bf = LH;//lc节点变成左边⾼ 48 break; 49 } 50 rd->bf=EH; //调整后rd节点⼀定平衡，且变成新的头节点 51 L_Rotate(T->lchild); //1.先左旋 51 L_Rotate(T->lchild); //1.先左旋 52 R_Rotate(T); //2.再右旋 53 } 54 } 55 /*************右平衡操作，包含RR和RL*******************************/ 56 void RightBalance(BSTree &T) 57 { 58 //对已*T为根的⼆叉排序树做右平衡旋转处理 59 //因为为LeftBalance(BSTree &T)的镜像，注释则省略 60 BSTree lc,rd; 61 lc = T->rchild; 62 switch(lc->bf) 63 { 64 case RH://右边⾼，RR型 65 T->bf = lc->bf = EH; 66 L_Rotate(T); 67 break; 68 case LH://左边⾼，RL型，分两步旋转 69 rd = lc->lchild; 70 switch(rd->bf) 71 { 72 case RH: 73 T->bf = LH; 74 lc->bf = EH; 75 break; 76 case LH: 77 T->bf = EH; 78 lc->bf = RH; 79 break; 80 case EH: 81 T->bf = lc->bf = EH; 82 break; 83 } 84 rd->bf = EH; 85 R_Rotate(T->rchild); //1.先右旋 86 L_Rotate(T); //2.再左旋 87 } 88 } 89 ⾄于插⼊操作主要就是判断树是不是平衡，若不平衡是左边还是右边，对于添加的新节点改变了树的平衡了没有，改变了左边的还是右边的，然后进⾏相应的旋转处理。具体算法如下： 90 int InsertAVL(BSTree &T, int key, bool &taller) 91 { 92 //若在平衡⼆叉排序树中不存在与关键字key相等的结点，则将关键字插⼊树中 93 //布尔变量taller表⽰树是否“长⾼” 94 if(T==NULL) 95 { 96 T = (BSTree)malloc(sizeof(BSTNode)); 97 T->data = key; 98 T->bf = EH;//叶⼦结点其平衡因⼦肯定为0 99 T->lchild = T->rchild = NULL;100 taller = 1;//树长⾼了101 }102 else103 {104 if(key==T->data)105 {//如果树中已存放此关键字则不予插⼊106 taller = 0;107 return 0;108 }109 if(key View Code4.4．理论与测试 理论：如图，给定⼀个序列的节点数组，按照⼏种变换规则得到了图⽰的排序⼆叉树，可以得到三序遍历和平衡因⼦。（由于图形⽐较多，暂时为⼿⼯画图） 该序列为：47, 63, 54,28,31,14,26,53,99,81 先序遍历：31，26，14，28，54，47，53，81，63，99 中序遍历：14，26，28，31，47，53，54，63，81，99 平衡因⼦：31和47的平衡因⼦为-1，其他的都为0测试：运⾏程序之后输出为：由先序和中序序列可以还原出树的原型，对照可知结果是正确的。4.5．讨论与体会 排序⼆叉树的中序遍历结果即为升序排列，但是运算速率不是最⾼的，为了寻找更好的⽅法，平衡排序⼆叉树便诞⽣了。对于开创者⽽⾔这是令⼈称赞的，但是对于后学者来说，在学习算法的核⼼思想的同时，更重要的是别⼈是怎样想到的，当⼀个现实⽣活的需要放在眼前是，我们要有开创的眼光，具有创新能⼒，这点是⾮常重要的，因为对于应⽤上来说有了第⼀个其他的就不再令⼈惊奇了。同时，递归，引⽤，开关、选择分⽀语句的运⽤也要引起注意。学习图的最好⽅法，就是数形结合，⼀定要多画图。4.6．附录（源代码） 1 #include 2 #include 15 void R_Rotate(BSTree &p) 16 { 17 //对以*p为根的⼆叉排序树做右旋处理，处理之后p指向新的树根结点 18 //注意此处引⽤的好处就是不⽤再出现双亲指针 19 BSTree lc; 20 lc=p->lchild; //指向B的位置 21 p->lchild=lc->rchild; //此处转换仍保持中序遍历不变性 22 lc->rchild=p; //更改a的指针位置 23 p=lc; //lc变成新的a 24 } 25 void L_Rotate(BSTree &p) 26 { 27 //对以*p为根的⼆叉排序树做左旋处理，处理之后p指向新的树根结点 28 //和R_Rotate()镜像对称 29 BSTree rc; 30 rc = p->rchild; 31 p->rchild = rc->lchild; 32 rc->lchild = p; 33 p = rc; 34 } 35 //包含LL和LR 36 void LeftBalance(BSTree &T) 37 { //对已*T为根的⼆叉排序树做左平衡旋转处理 38 BSTree lc,rd; 39 lc = T->lchild; //lc调整左边 40 switch(lc->bf) 41 { 42 case LH://若是左边⾼则为LL型，只需旋转即可 43 T->bf = lc->bf = EH; //旋转后平衡因⼦均为0 44 R_Rotate(T); //LL型需要右旋转 45 break; 46 case RH://若是右边⾼，则为LR型，需分两步调整 47 rd = lc->rchild; //找到不确定因⼦rd 48 switch(rd->bf)//对不确定因⼦进⾏讨论 49 { 50 case LH://左边⾼调整后 51 T->bf = RH;//根节点右边变⾼ 52 lc->bf = EH; //lc变平衡 53 break; 54 case EH://rd有左右节点 55 T->bf = lc->bf = EH; //调整后持平 56 break; 57 case RH://右边⾼ 58 T->bf = EH;//根节点平衡 59 lc->bf = LH;//lc节点变成左边⾼ 60 break; 61 } 62 rd->bf=EH; //调整后rd节点⼀定平衡，且变成新的头节点 63 L_Rotate(T->lchild); //1.先左旋 64 R_Rotate(T); //2.再右旋 65 } 66 } 67 /*************右平衡操作，包含RR和RL*******************************/ 68 void RightBalance(BSTree &T) 69 { 70 //对已*T为根的⼆叉排序树做右平衡旋转处理 71 //因为为LeftBalance(BSTree &T)的镜像，注释则省略 72 BSTree lc,rd; 73 lc = T->rchild; 74 switch(lc->bf) 75 { 76 case RH://右边⾼，RR型 77 T->bf = lc->bf = EH; 78 L_Rotate(T); 79 break; 80 case LH://左边⾼，RL型，分两步旋转 81 rd = lc->lchild; 82 switch(rd->bf) 83 { 84 case RH: 85 T->bf = LH; 86 lc->bf = EH; 87 break; 88 case LH: 89 T->bf = EH; 90 lc->bf = RH; 91 break; 92 case EH: 93 T->bf = lc->bf = EH; 94 break; 95 } 96 rd->bf = EH; 97 R_Rotate(T->rchild); //1.先右旋 98 L_Rotate(T); //2.再左旋 99 }100 }101 102 int InsertAVL(BSTree &T, int key, bool &taller) 103 {104 //若在平衡⼆叉排序树中不存在与关键字key相等的结点，则将关键字插⼊树中105 //布尔变量taller表⽰树是否“长⾼”106 if(T==NULL)107 {108 T = (BSTree)malloc(sizeof(BSTNode));109 T->data = key;110 T->bf = EH;//叶⼦结点其平衡因⼦肯定为0111 T->lchild = T->rchild = NULL;112 taller = 1;//树长⾼了113 }114 else115 {116 if(key==T->data)117 {//如果树中已存放此关键字则不予插⼊118 taller = 0;119 return 0;120 }121 if(key 170 //访问函数，输出节点以及相应平衡因⼦171 void VisitTree(BSTree &T)172 { //输出结点172 { //输出结点173 if(T!=NULL) 174 {175 printf("%d ",T->data); 176 printf("平衡因⼦: %dn",T->bf); 177 }178 } 179 180 void PreOrderTraverse(BSTree &T)181 {//递归实现先序遍历182 if(T!=NULL)183 VisitTree(T);184 if(T->lchild)185 PreOrderTraverse(T->lchild);186 if(T->rchild)187 PreOrderTraverse(T->rchild);188 } 189 190 void InOrderTraverse(BSTree &T)191 {//递归实现中序遍历192 if(T->lchild)193 InOrderTraverse(T->lchild);194 if(T!=NULL)195 VisitTree(T);196 if(T->rchild)197 InOrderTraverse(T->rchild);198 } 199 int main( )200 {201 BSTree T;202 bool taller=0;203 int i;204 T=NULL;205 int a[50]={47,63,54,28,31,14,26,53,99,81};206 for(i=0;i<10;i++)207 {208 InsertAVL(T,a[i],taller); 209 }210 printf("先序遍历:n"); 211 PreOrderTraverse(T); 212 printf("n中序遍历:n");213 InOrderTraverse(T); 214 printf("n");215 return 0;216 }View Code
发布者：admin，转转请注明出处：http://www.yc00.com/web/1687381563a5821.html
评论列表（0条）