现在的位置: 首页 > 综合 > 正文

二叉树遍历的各种算法

2014年10月03日 ⁄ 综合 ⁄ 共 3541字 ⁄ 字号 小 中 大 ⁄ 评论关闭

   二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。

     二叉树有两种存储结构：顺序存储和链式存储

    顺序存储：  （对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用）

[cpp] view
plaincopy

  1. typedef struct   
  2. {  
  3.     ElemType data[MaxSize];  
  4.     int n;  
  5. }SqBTree;  

  链式存储：

[csharp] view
plaincopy

  1. typedef struct node  
  2. {  
  3.     ElemType data;  
  4.     struct node *lchild;  
  5.     struct node *rchild;  
  6. } BTNode;  


二叉树三种递归的遍历方法：

先序遍历 访问根节点→先序遍历左子树→先序遍历右子树
中序遍历 中序遍历左子树→访问根节点→中序遍历右子树
后序遍历 后序遍历左子树→后序遍历右子树→访问根节点

二叉树遍历的递归算法：

[cpp] view
plaincopy

  1. void preOrder(BTNode *b)  //先序遍历递归算法  
  2. {  
  3.     if (b!=NULL)  
  4.     {  
  5.         visit(b);  
  6.         preOrder(b->lchild);  
  7.         preOrder(b->rchild);  
  8.     }  
  9. }  
  10. void InOrder(BTNode *b)   //中序遍历递归算法  
  11. {  
  12.     if(b!=NULL)  
  13.     {  
  14.         InOrder(b->lchild);  
  15.         visit(b);  
  16.         InOrder(b->rchild);  
  17.     }  
  18. }  
  19. void PostOrder(BTNode *b)   //后序遍历递归算法  
  20. {  
  21.     if(b!=NULL){  
  22.         PostOrder(b->lchild);  
  23.         PostOrder(b->rchild);  
  24.         visit(b);  
  25.     }  
  26. }  

二叉树非递归遍历算法：

有两种方法：①用栈存储信息的方法  ②增加指向父节点的指针的方法    暂时只介绍下栈的方法

先序遍历：

[cpp] view
plaincopy

  1. void PreOrder(BTNode *b)  
  2. {  
  3.     Stack s;  
  4.     while(b!=NULL||!s.empty())  
  5.     {  
  6.         if(b!=NULL){  
  7.             visit(b);  
  8.             s.push(b);  
  9.             b=b->left;  
  10.         }  
  11.         else{  
  12.             b=s.pop();  
  13.             b=b->right;  
  14.         }  
  15.     }  
  16. }  

中序遍历：

[cpp] view
plaincopy

  1. void InOrder(BTNode *b){  
  2.     Stack s;  
  3.     while(b!=NULL||!s.empty()){  
  4.         if (b!=NULL)  
  5.         {  
  6.             s.push(b);  
  7.             s=s->left  
  8.         }  
  9.         if(!s.empty()){  
  10.             b=s.pop();  
  11.             visit(b);  
  12.             b=b->right;  
  13.         }  
  14.     }  
  15. }  

后序遍历：

[cpp] view
plaincopy

  1. void PostOrder(BTNode *b){  
  2.     Stack s;  
  3.     while(b!=NULL){  
  4.         s.push(b);  
  5.     }  
  6.     while(!s.empty()){  
  7.         BTNode* node=s.pop();  
  8.         if(node->bPushed){  
  9.             visit(node);  
  10.         }  
  11.         else{  
  12.             s.push(node);  
  13.             if(node->right!=NULL){  
  14.                 node->right->bPushed=false;  
  15.                 s.push(node->right);  
  16.             }  
  17.             if(node->left!=NULL){  
  18.                 node->left->bpushed=false;  
  19.                 s.push(node->left);  
  20.             }  
  21.         node->bPushed=true;  //如果标识位为true,则表示入栈  
  22.         }         
  23.     }  
  24. }  

层次遍历算法：（用队列的方法）

[cpp] view
plaincopy

  1. void levelOrder(BTNode *b){  
  2.     Queue Q;  
  3.     Q.push(b);  
  4.     while(!Q.empty()){  
  5.         node=Q.front();  
  6.         visit(node);  
  7.         if(NULL!=node->left){  
  8.             Q.push(node->left);  
  9.         }  
  10.         if(NULL!=right){  
  11.             Q.push(node->right);  
  12.         }  
  13.     }  
  14. }<span style=""></span>  

已知先序和中序求后序的算法：（已知后序和中序求先序的算法类似，但已知先序和后序无法求出中序）

[cpp] view
plaincopy

  1. int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */  
  2. {  
  3.     int i;  
  4.     for(i=s;i<=e;i++)  
  5.     if(A[i]==c) return i;  
  6. }  
  7. /* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */  
  8. /* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */  
  9. /* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */  
  10. void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)  
  11. {  
  12.     char c;  
  13.     int k;  
  14.     if(in_s>in_e) return ; /* 非法子树，完成。 */  
  15.     if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */  
  16.      return ;  
  17.     }  
  18.     c=pre[pre_s]; /* c储存根节点。 */  
  19.     k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */  
  20.     pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */  
  21.     pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */  
  22.     printf("%c",c); /* 根节点输出。 */  
  23. }  
  24. main()  
  25. {  
  26.     char pre[]="abdc";  
  27.     char in[]="bdac";  
  28.     printf("The result:");  
  29.     pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);  
  30.     getch();  
  31. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞