11 二叉树-链式存储-先序遍历、中序遍历、后序遍历和层序遍历的非递归算法实现

数据类型定义见同上一篇文章详见代码内容

这里使用了C++自带的stl模板中的stack模板

简化了很多工作

写出stl模板的前辈，您真是太伟大了

具体的算法描述见代码注释

显然的，非递归算法的执行效率要高于递归算法。

直接上代码实现内容：

  1 #include<iostream>
  2 #include<stdlib.h>
  3 #include<cstdio>
  4 #include<stack>
  5 using namespace std;
  6 #define TRUE 1
  7 #define FALSE 0
  8 #define OK 1
  9 #define ERROR 0
 10 #define OVERFLOW -2
 11 typedef int Status;
 12 typedef int ElemType;
 13 
 14 /*存储结构描述*/
 15 typedef struct BitNode
 16 {
 17     int data;
 18     struct BitNode *lchild,*rchild;
 19 } BitNode,*BiTree;
 20 /*建立树*/
 21 void initTree(BiTree &T)
 22 {
 23     int x;
 24     cin>>x;
 25     if(x==0)
 26     {
 27         T=NULL;
 28     }
 29     else  //按照先序遍历建树
 30     {
 31         T=(BitNode*)malloc(sizeof(BitNode));
 32         T->data=x;
 33         initTree(T->lchild);
 34         initTree(T->rchild);
 35     }
 36 }
 37 
 38 void visit(BiTree T)
 39 {
 40     cout<<T->data<<' ';
 41 }
 42 /*非递归遍历*/
 43 /*中序遍历*/
 44 /*1、这里直接使用了stl模板中的stack实现栈的功能*/
 45 /*2、算法描述：
 46   ①扫描根结点的所有左孩子→有?就一一进栈！
 47   ②一直到左孩子没有了→退栈，访问根结点→向右子树出发→① 如果没有右孩子了→③
 48   ③退栈，访问根结点→①……
 49   终止：栈空，p也空（即走到最后一个结点的右孩子为空……走到了尽头）
 50 */
 51 void InOrder(BiTree T)
 52 {
 53     stack<BiTree> S;
 54     BiTree p=T;
 55     while(p||!S.empty())
 56     {
 57         if(p)
 58         {
 59             S.push(p);
 60             p=p->lchild;
 61         }
 62         else
 63         {
 64             p=S.top();
 65             S.pop();
 66             visit(p);
 67             p=p->rchild;
 68         }
 69     }
 70 }
 71 
 72 /*先序遍历*/
 73 /*其实原理和中序遍历相似，只是访问结点的顺序改变了！
 74   如果理解了中序遍历的非递归算法，先序遍历也就能理解了。这里不再赘述了。
 75 */
 76 void PreOrder(BiTree T)
 77 {
 78     stack<BiTree> S;
 79     BiTree p=T;
 80     while(p||!S.empty())
 81     {
 82         if(p)
 83         {
 84             visit(p);
 85             S.push(p);
 86             p=p->lchild;
 87         }
 88         else{
 89             p=S.top();
 90             S.pop();
 91             p=p->rchild;
 92         }
 93     }
 94 }
 95 /*后序遍历*/
 96 void PostOrder(BiTree T)
 97 {
 98     stack<BiTree> S;
 99     BiTree p=T,r=NULL;//这个r用来标记最近访问的结点
100     while(p||!S.empty())
101     {
102         if(p)
103         {
104             S.push(p);
105             p=p->lchild;
106         }
107         else{
108             p=S.top();
109             if(p->rchild&&p->rchild!=r)
110             {
111                 p=p->rchild;
112                 S.push(p);
113                 p=p->lchild;
114             }
115             else {
116                 p=S.top();
117                 S.pop();
118                 visit(p);
119                 r=p;
120                 /*标记为最近访问的结点。初学者可能会疑惑为什么要标记呢？
121                 这是用于【右孩子A是叶子结点，访问了以后要退回A的爸爸（A的根结点），有了r的标记，爸爸就可以知道它的孩子们是否都已访问完了，只有当孩子们都已经访问完以后才能访问根结点。*/
122                 p=NULL;
123             }
124         }
125     }
126 }
127 int main()
128 {
129     BiTree tree;
130     cout<<"Create tree in preOrder.:"<<endl;
131     initTree(tree);
132     cout<<"--- show the preorder sequence: ---"<<endl;
133     PreOrder(tree);
134     cout<<endl;
135     cout<<"--- show the inorder sequence: ---"<<endl;
136     InOrder(tree);
137     cout<<endl;
138     cout<<"--- show the postorder sequence: ---"<<endl;
139     PostOrder(tree);
140     return 0;
141 }

层序遍历：

写完前面三个新加上的

解释见代码注释

 1 /*层序遍历*/
 2 /*算法描述
 3 1、初始化一个队列用来存放树结点
 4 2、队非空时：
 5     （1）队首出队并访问值
 6     （2）如果该结点有左右孩子→顺序入队尾→（1）
 7   队为空时结束
 8 */
 9 void LevelOrder(BiTree T)
10 {
11     queue<BiTree> Q;
12     BiTree p;Q.push(T);//让根结点入队
13     while(!Q.empty())
14     {
15         p=Q.front();
16         Q.pop();
17         visit(p);
18         if(p->lchild!=NULL) Q.push(p->lchild);
19         if(p->rchild!=NULL) Q.push(p->rchild);
20     }
21 }

代码实现截图