实验目标：
1、创建二叉树
2、用非递归算法先中后序遍历二叉树 (难点)
3、分别求出二叉树中度为 0、1、2的结点个数
4、求出树的高度
参考博客:
Article_1
Article_2
难点在于非递归遍历，用栈来模拟递归的过程
二叉树结构
1
2
3
4
| typedef struct node{
char data;
struct node *lchild, *rchild;
}BiTNode,*BiTree;
|
创建二叉树
1
2
3
4
5
6
7
8
9
10
| void CreateBiTree(BiTree &t){
char ch; cin>>ch;
if(ch=='#') t=NULL;
else{
t=new node;
t->data=ch;
CreateBiTree(t->lchild);
CreateBiTree(t->rchild);
}
}
|
层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void Level(BiTree L){
cout<<"层序遍历:\n";
if(!L) return ;
queue<BiTree> q;
q.push(L);
while(!q.empty()){
BiTree fr=q.front();
q.pop();
if(fr) cout<<fr->data<<' ';
else continue;
q.push(fr->lchild);
q.push(fr->rchild);
}
}
|
前序遍历
递归
1
2
3
4
5
6
7
8
9
| void preOrder1(BinTree *root)
{
if(root!=NULL)
{
cout<<root->data<<"";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
|
非递归
用栈模拟递归
对比递归算法，当递归调用自己时就把当前状态入栈!
操作： 对于当前子树，1.不空就输出根节点并把当前指针入栈，然后更新指针指向左子树，2. 空就更新指针指向栈顶的右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void PreOreder(BiTree L){
cout<<"前序遍历:\n";
if(!L) return ;
stack<BiTree> st;
while(L || !st.empty()){
while(L){
cout<<L->data<<' ';
st.push(L);
L=L->lchild;
}
if(!st.empty()){
L=st.top();
st.pop();
L=L->rchild;
}
}
}
|
中序遍历
递归
1
2
3
4
5
6
7
8
9
| void inOrder1(BinTree *root)
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<"";
inOrder1(root->rchild);
}
}
|
非递归
和前序一样，只不过改成在当前节点没有左子树时输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void MidOreder(BiTree L){
cout<<"中序遍历:\n";
stack<BiTree> st;
while(L || !st.empty()){
while(L){
st.push(L);
L = L->lchild;
}
if (!st.empty()){
L = st.top();
st.pop();
cout<<L->data<<' ';
L=L->rchild;
}
}
}
|
后序遍历
递归
1
2
3
4
5
6
7
8
9
| void postOrder1(BinTree *root)
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
cout<<root->data<<"";
}
}
|
非递归
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题，解决方案如下。
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
void PostOrder(BiTree L){
cout<<"后序遍历:\n";
if(!L) return ;
stack<BiTree> st;
st.push(L);
BiTree pre=L;
while(!st.empty()){
BiTree temp=st.top();
if((!temp->lchild && !temp->rchild) || (!temp->rchild && temp->lchild==pre) || temp->rchild==pre){
cout<<temp->data<<' ';
pre=temp;
st.pop();
}
else{
if(temp->rchild) st.push(temp->rchild);
if(temp->lchild) st.push(temp->lchild);
}
}
}
|
求度数简单这里不单独放代码了
全代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#include <bits/stdc++.h>
using namespace std;
typedef struct node{
char data;
struct node *lchild, *rchild;
}BiTNode,*BiTree;
int cnt0,cnt1,cnt2,high;
void CreateBiTree(BiTree &t){
char ch; cin>>ch;
if(ch=='#') t=NULL;
else{
t=new node;
t->data=ch;
CreateBiTree(t->lchild);
CreateBiTree(t->rchild);
}
}
void find(BiTree t,int h){
if(!t) return ;
high=max(high,h);
if(t->lchild && t->rchild) cnt2++;
else if(!t->lchild && !t->rchild) cnt0++;
else cnt1++;
find(t->lchild,h+1);
find(t->rchild,h+1);
}
void Level(BiTree L){
cout<<"层序遍历:\n";
if(!L) return ;
queue<BiTree> q;
q.push(L);
while(!q.empty()){
BiTree fr=q.front();
q.pop();
if(fr) cout<<fr->data<<' ';
else continue;
q.push(fr->lchild);
q.push(fr->rchild);
}
}
void PreOreder(BiTree L){
cout<<"前序遍历:\n";
if(!L) return ;
stack<BiTree> st;
while(L || !st.empty()){
while(L){
cout<<L->data<<' ';
st.push(L);
L=L->lchild;
}
if(!st.empty()){
L=st.top();
st.pop();
L=L->rchild;
}
}
}
void MidOreder(BiTree L){
cout<<"中序遍历:\n";
stack<BiTree> st;
while(L || !st.empty()){
while(L){
st.push(L);
L = L->lchild;
}
if (!st.empty()){
L = st.top();
st.pop();
cout<<L->data<<' ';
L=L->rchild;
}
}
}
void PostOrder(BiTree L){
cout<<"后序遍历:\n";
if(!L) return ;
stack<BiTree> st;
st.push(L);
BiTree pre=L;
while(!st.empty()){
BiTree temp=st.top();
if((!temp->lchild && !temp->rchild) || (!temp->rchild && temp->lchild==pre) || temp->rchild==pre){
cout<<temp->data<<' ';
pre=temp;
st.pop();
}
else{
if(temp->rchild) st.push(temp->rchild);
if(temp->lchild) st.push(temp->lchild);
}
}
}
void Traverse(BiTree L){
cout<<'\n';
Level(L);
cout<<'\n';
PreOreder(L);
cout<<'\n';
MidOreder(L);
cout<<'\n';
PostOrder(L);
cout<<'\n';
}
int main()
{
BiTree L;
CreateBiTree(L);
Traverse(L);
find(L,1);
cout<<"树的高度为: "<<high<<'\n';
cout<<"度数为0的节点数量: "<<cnt0<<'\n';
cout<<"度数为1的节点数量: "<<cnt1<<'\n';
cout<<"度数为2的节点数量: "<<cnt2<<'\n';
return 0;
}
|
wechat
alipay