首页 / 算法 / 二叉树的各种遍历

二叉树的各种遍历

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的各种遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3688字，纯文字阅读大概需要6分钟。

内容图文

转载地址http://blog.csdn.net/SJF0115/article/details/8645991

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。

二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：

 

  1. //二叉树结点  
  2. typedef struct BiTNode{  
  3.     //数据  
  4.     char data;  
  5.     //左右孩子指针  
  6.     struct BiTNode *lchild,*rchild;  
  7. }BiTNode,*BiTree;  

 

 

二叉树的创建：

通过读入一个字符串，建立二叉树的算法如下：

 

  1. //按先序序列创建二叉树  
  2. int CreateBiTree(BiTree &T){  
  3.     char data;  
  4.     //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树  
  5.     scanf("%c",&data);  
  6.     if(data == ‘#‘){  
  7.         T = NULL;  
  8.     }  
  9.     else{  
  10.         T = (BiTree)malloc(sizeof(BiTNode));  
  11.         //生成根结点  
  12.         T->data = data;  
  13.         //构造左子树  
  14.         CreateBiTree(T->lchild);  
  15.         //构造右子树  
  16.         CreateBiTree(T->rchild);  
  17.     }  
  18.     return 0;  
  19. }  


二叉树的遍历：

 

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

递归算法：

 

  1. //输出  
  2. void Visit(BiTree T){  
  3.     if(T->data != ‘#‘){  
  4.         printf("%c ",T->data);  
  5.     }  
  6. }  
  7. //先序遍历  
  8. void PreOrder(BiTree T){  
  9.     if(T != NULL){  
  10.         //访问根节点  
  11.         Visit(T);  
  12.         //访问左子结点  
  13.         PreOrder(T->lchild);  
  14.         //访问右子结点  
  15.         PreOrder(T->rchild);  
  16.     }  
  17. }  
  18. //中序遍历  
  19. void InOrder(BiTree T){  
  20.     if(T != NULL){  
  21.         //访问左子结点  
  22.         InOrder(T->lchild);  
  23.         //访问根节点  
  24.         Visit(T);  
  25.         //访问右子结点  
  26.         InOrder(T->rchild);  
  27.     }  
  28. }  
  29. //后序遍历  
  30. void PostOrder(BiTree T){  
  31.     if(T != NULL){  
  32.         //访问左子结点  
  33.         PostOrder(T->lchild);  
  34.         //访问右子结点  
  35.         PostOrder(T->rchild);  
  36.         //访问根节点  
  37.         Visit(T);  
  38.     }  
  39. }  

 

非递归算法：

<1>先序遍历：

【思路】：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

 

  1. /* 先序遍历(非递归) 
  2.    思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 
  3. */  
  4. void PreOrder2(BiTree T){  
  5.     stack<BiTree> stack;  
  6.     //p是遍历指针  
  7.     BiTree p = T;  
  8.     //栈不空或者p不空时循环  
  9.     while(p || !stack.empty()){  
  10.         if(p != NULL){  
  11.             //存入栈中  
  12.             stack.push(p);  
  13.             //访问根节点  
  14.             printf("%c ",p->data);  
  15.             //遍历左子树  
  16.             p = p->lchild;  
  17.         }  
  18.         else{  
  19.             //退栈  
  20.             p = stack.top();  
  21.             stack.pop();  
  22.             //访问右子树  
  23.             p = p->rchild;  
  24.         }  
  25.     }//while  
  26. }  

 

 

<2>中序遍历

【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
         先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

 

  1. void InOrder2(BiTree T){  
  2.     stack<BiTree> stack;  
  3.     //p是遍历指针  
  4.     BiTree p = T;  
  5.     //栈不空或者p不空时循环  
  6.     while(p || !stack.empty()){  
  7.         if(p != NULL){  
  8.             //存入栈中  
  9.             stack.push(p);  
  10.             //遍历左子树  
  11.             p = p->lchild;  
  12.         }  
  13.         else{  
  14.             //退栈，访问根节点  
  15.             p = stack.top();  
  16.             printf("%c ",p->data);  
  17.             stack.pop();  
  18.             //访问右子树  
  19.             p = p->rchild;  
  20.         }  
  21.     }//while  
  22. }  


<3>后序遍历

 

【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

 

  1. //后序遍历(非递归)  
  2. typedef struct BiTNodePost{  
  3.     BiTree biTree;  
  4.     char tag;  
  5. }BiTNodePost,*BiTreePost;  
  6.   
  7. void PostOrder2(BiTree T){  
  8.     stack<BiTreePost> stack;  
  9.     //p是遍历指针  
  10.     BiTree p = T;  
  11.     BiTreePost BT;  
  12.     //栈不空或者p不空时循环  
  13.     while(p != NULL || !stack.empty()){  
  14.         //遍历左子树  
  15.         while(p != NULL){  
  16.             BT = (BiTreePost)malloc(sizeof(BiTNodePost));  
  17.             BT->biTree = p;  
  18.             //访问过左子树  
  19.             BT->tag = ‘L‘;  
  20.             stack.push(BT);  
  21.             p = p->lchild;  
  22.         }  
  23.         //左右子树访问完毕访问根节点  
  24.         while(!stack.empty() && (stack.top())->tag == ‘R‘){  
  25.             BT = stack.top();  
  26.             //退栈  
  27.             stack.pop();  
  28.             BT->biTree;  
  29.             printf("%c ",BT->biTree->data);  
  30.         }  
  31.         //遍历右子树  
  32.         if(!stack.empty()){  
  33.             BT = stack.top();  
  34.             //访问过右子树  
  35.             BT->tag = ‘R‘;  
  36.             p = BT->biTree;  
  37.             p = p->rchild;  
  38.         }  
  39.     }//while  
  40. }  

 

<4>层次遍历

【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。

 

  1. //层次遍历  
  2. void LevelOrder(BiTree T){  
  3.     BiTree p = T;  
  4.     //队列  
  5.     queue<BiTree> queue;  
  6.     //根节点入队  
  7.     queue.push(p);  
  8.     //队列不空循环  
  9.     while(!queue.empty()){  
  10.         //对头元素出队  
  11.         p = queue.front();  
  12.         //访问p指向的结点  
  13.         printf("%c ",p->data);  
  14.         //退出队列  
  15.         queue.pop();  
  16.         //左子树不空，将左子树入队  
  17.         if(p->lchild != NULL){  
  18.             queue.push(p->lchild);  
  19.         }  
  20.         //右子树不空，将右子树入队  
  21.         if(p->rchild != NULL){  
  22.             queue.push(p->rchild);  
  23.         }  
  24.     }  
  25. }  


 

测试用例：

技术分享

输入：

ABC##DE#G##F###

输出：

技术分享

原文：http://www.cnblogs.com/waiwai4701/p/4250463.html

内容总结

以上是互联网集市为您收集整理的二叉树的各种遍历全部内容，希望文章能够帮你解决二叉树的各种遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1047291.html

来源：【匿名】