C++⼆叉树的先序，中序，后序遍历
三种遍历⽅式都分为递归与⾮递归的⽅式。三种遍历⽅式的递归思想相同。后序遍历⾮递归⽅法分为两种，具体见代码。
构造⽅式：
1 #include<iostream>
2 #include<stack>
3using namespace std;
4
5 typedef struct BiTNode{
6char data;
7int lvisited,rvisited;//左、右孩⼦是否访问过，1表⽰已访问（此项只在后序⾮递归2算法中需要）
8struct BiTNode *lchild,*rchild;
9 }BiTNode,*BiTree;
10
11void InitBiTree(BiTree &T)//构造空⼆叉树
12 {
13    T=NULL;
14 }
15void CreateBiTree(BiTree &T)//⽣成⼆叉树
16 {
17char ch;
18    cin>>ch;
19if(ch=='0')//0代表空
20        T=NULL;
21else
22    {
23        T=(BiTree)malloc(sizeof(BiTNode));//⽣成根结点
24if(!T)
25        {
26            cout<<"⽣成结点错误！"<<endl;
27return;
28        }
29        T->data=ch;
30        T->lvisited=0;
31        T->rvisited=0;
32        CreateBiTree(T->lchild);
33        CreateBiTree(T->rchild);
34    }
35 }
三种遍历⽅式代码：
1void PreOrder(BiTree T)//先序递归遍历
2 {
3if(T!=NULL)
4    {
5        cout<<T->data<<"";
6        PreOrder(T->lchild);
7        PreOrder(T->rchild);
8    }
9 }
10void SqlPreOrder(BiTree T)//先序⾮递归遍历
11 {
12    stack<BiTree> s;
13    BiTree p=T;
14while(p || !s.empty())
15    {
16if(p)
17        {
18            cout<<p->data<<"";
19            s.push(p);
20            p=p->lchild;
21        }
22else
23        {
24            p();
25            p=p->rchild;
26            s.pop();
27        }
28    }
29 }
30
31
32先序中序后序遍历二叉树
33void InOrder(BiTree T)//中序递归遍历
34 {
35if(T!=NULL)
36    {
37        InOrder(T->lchild);
38        cout<<T->data<<"";
39        InOrder(T->rchild);
40    }
41 }
42void SqInOrder(BiTree T)//中序⾮递归遍历
43 {
44    stack<BiTree> s;
45    BiTree p=T;
46while(p || !s.empty())
47if(p)
48        {
49            s.push(p);
50            p=p->lchild;
51        }
52else
53        {
54            p();
55            cout<<p->data<<"";
56            s.pop();
57            p=p->rchild;
58        }
59 }
60
61
62
63void PostOrder(BiTree T)//后序递归遍历
64 {
65if(T!=NULL)
66    {
67        PostOrder(T->lchild);
68        PostOrder(T->rchild);
69        cout<<T->data<<"";
70    }
71 }
72
73//后序⾮递归遍历1思路：因为后序⾮递归遍历⼆叉树的顺序是先访问左⼦树，再访问后⼦树，最后 74//访问根结点。当⽤堆栈来存储结点，必须分清返回根结点时，是从左⼦树返回的，还是从右⼦树 75//返回的。所以，使⽤辅助指针r，其指向最近访问过的结点。
76void SqlPostOrder1(BiTree T)//后序⾮递归遍历1
77 {
78    stack<BiTree> s;
79    BiTree p=T,r;
80while(p || !s.empty())
81    {
82if(p)                            //⾛到最左边
83        {
84            s.push(p);
85            p=p->lchild;
86        }
87else//向右
88        {
89            p();//取栈顶结点
90if(p->rchild && p->rchild!=r)//如果右⼦树存在，且未被访问过
91            {
92                p=p->rchild;
93                s.push(p);
94                p=p->lchild;            //再⾛到最左
95            }
96else//否则，访问栈顶结点并弹出
97            {
98                cout<<p->data<<"";
99                r=p;                    //记录该结点
100                s.pop();
101                p=NULL;                    //结点访问完后，重置p指针
102            }
103        }
104    }
105 }
106//思路2：在结点中增加标志域，记录是否已被访问。
107void SqlPostOrder2(BiTree T)//后序⾮递归遍历2
108 {
109    stack<BiTree> s;
110    BiTree p=T;
111while(p || !s.empty())
112    {
113if(p && p->lvisited==0)                    //左⾛，且左⼦树未被访问
114        {
115            p->lvisited=1;
116            s.push(p);
117            p=p->lchild;
118        }
119else
120        {
121            p();
122if(p->rchild!=NULL && p->rvisited==0)//右⼦树未被访问，右⾛⼀步123            {
124                p->rvisited=1;
125                p=p->rchild;
126            }
127else//访问栈顶元素并弹栈
128            {
129                cout<<p->data<<"";
130                s.pop();
131if(!s.empty())
132                    p();
133else//当最后⼀个元素弹栈出去后，结束134return ;
135            }
136        }
137    }
138 }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。