数据结构与算法系列研究五——树、二叉树、三叉树、平衡排序二叉树AVL(2)

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 Code

2.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))
 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     else
100     {
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         else
154             if(!IsEmptyStack(&s))   
155             {
156                 pop(&s,p);
157             }
158             else
159                 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         else
200             if(!IsEmptyStack(&s))
201             {
202                 pop(&s,p);      //向上追溯
203             }
204             else
205                 p=NULL;     //栈空时恰访问完
206     }
207 }
208 /************************************/
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         else
240         {
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     else
291     {
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     else
311     {
312         lchild=NULL; //否则为零
313     }
314     if(tree->RChild)
315     {
316         CopyBiTree(tree->RChild,rchild);
317     }
318     else
319     {
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;                        //一定要初始化为0
349     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 {
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叶子个数为:%d\n",count);
390     depth=TreeDepth(tree);
391     printf("\n树的深度为：%d\n",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     

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-121392-2.html