C++ 遍历二叉树实例详解
2叉数又叫红黑树，关于2叉数的遍历问题，有很多，一般有三种常用遍历方法：
(1)前序遍历(2)中序遍历(3)后续遍历
以下是经典示例：
|
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
|
#include "stdafx.h"
#include<stdio.h>
#include<malloc.h>
#include <math.h >
#define MaxSize 20
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
//建立二叉树
void CreateBiTree(BiTree *T)
{
char ch;
scanf("%c",&ch);
getchar();
if(ch==' ')
{
printf("不产生子树。\n");
*T=NULL;
}
else
{
if(!(*T=(BiTNode *)malloc(sizeof(BiTNode))))
{
printf("分配空间失败");
return;
}//生成一个新节点
(*T)->data = ch;
printf("产生左右子树。\n");
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
//递归前序遍历
void Preorder(BiTNode *T)
{
if(T)
{
printf("%c ",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//递归中序遍历
void Inorder(BiTNode *T)
{
if(T)
{
Inorder(T->lchild);
printf("%c ",T->data);
Inorder(T->rchild);
}
}
//递归后序遍历
void Postorder(BiTNode *T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c ",T->data);
}
}
//非递归前序遍历
void NPreorder(BiTNode *T)
{
BiTNode *stack[MaxSize],*p;
int top=-1;
if(T)
{
top++;
stack[top]=T; //根节点进栈
while(top>-1) //栈不为空时循环
{
p=stack[top]; //退栈并访问该节点
top--;
printf("%c ",p->data);
if(p->rchild) //右孩子进栈
{
top++;
stack[top]=p->rchild;
}
if(p->lchild) //左孩子进栈
{
top++;
stack[top]=p->lchild;
}
}
}
}
//非递归中序遍历
void NInorder(BiTNode *T)
{
BiTNode *stack[MaxSize],*p;
int top=-1;
p=T;
while(p||top!=-1)
{
if(p)
{
top++;
stack[top]=p;
p=p->lchild;
} //根节点进栈，遍历左子树
else //根节点退栈，访问根节点，遍历右子树
{
p=stack[top];
top--;
printf("%c ",p->data);
p=p->rchild;
}
}
}
//非递归后序遍历
void NPostorder(BiTNode *T)
{
BiTNode *stack[MaxSize],*p;
int flag,top=-1;
do
{
while(T)
{
top++;
stack[top]=T;
T=T->lchild;
} //所有左节点进栈
p=NULL; //p总是指向当前节点的前一个已经访问过的节点
flag=1; //flag为1表示当前节点已经访问过了
while(top!=-1 && flag)
{
T=stack[top];
if(T->rchild==p) //右子树不存在或者已经被访问过时
{
printf("%c ",T->data);
top--;
p=T; //调整p指针
}
else
{
T=T->rchild;
flag=0; //调整访问标志
}
}
} while(top!=-1);
}
//层次遍历二叉树
void Translever(BiTNode *T)
{
struct node
{
BiTNode *vec[MaxSize];
int f,r; //r为队尾，f为队头
}queue;
BiTNode *p;
p=T;
queue.f=0;
queue.r=0;
if(T)
printf("%c ", p->data);
queue.vec[queue.r]=p;
queue.r=queue.r+1;
while(queue.f<queue.r)
{
p=queue.vec[queue.f];
queue.f=queue.f+1;
if(p->lchild)
{
printf("%c ",p->lchild->data);
queue.vec[queue.r]=p->lchild;
queue.r=queue.r+1;
}
if(p->rchild)
{
printf("%c ",p->rchild->data);
queue.vec[queue.r]=p->rchild;
queue.r=queue.r+1;
}
}
printf("\n");
}
//求二叉树的深度
int Depth(BiTNode *T)
{
int dep1,dep2;
if(T==NULL)
return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2)
return(dep1+1);
else
return(dep2+1);
}
}
//输出二叉树
void Disptree(BiTNode *T)
{
if(T)
{
printf("%c",T->data);
if(T->lchild || T->rchild)
{
printf("(");
Disptree(T->lchild);
if(T->rchild)
printf(",");
Disptree(T->rchild);
printf(")");
}
}
}
|
main.cpp
|
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
|
void main()
{
BiTree T=NULL;
char j;
int sign = 1;
printf("本程序可以进行建立二叉树、递归与非递归先序、中序、后序遍历二叉树、层次遍历二叉树、输出二叉树的扩展序列的操作。\n");
printf("请将二叉树的先序序列输入以建立二叉树，叶子节点用空格代替。\n");
printf("您必须一个一个地输入字符。\n");
while(sign)
{
printf("请选择: \n");
printf("0.生成二叉树 1.求二叉树的深度\n");
printf("2.递归先序遍历 3.非递归先序遍历\n");
printf("4.递归中序遍历 5.非递归中序遍历\n");
printf("6.递归后序遍历 7.非递归后序遍历\n");
printf("8.层次遍历 9.输出二叉树的广义表形式\n");
printf("q.退出程序\n");
scanf("%c",&j);
getchar();
switch(j)
{
case '0':
printf("生成二叉树:");
CreateBiTree(&T);
printf("\n");
printf("\n");
break;
case '1':
if(T)
{
printf("此二叉树的深度为:");
printf("%d",Depth(T));
printf("\n");
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '2':
if(T)
{
printf("递归先序遍历二叉树:");
Preorder(T);
printf("\n");
printf("\n");
}
else
printf("二叉树为空!\n");
break;
case '3':
if(T)
{
printf("非递归先序遍历二叉树:");
NPreorder(T);
printf("\n");
printf("\n");
}
else
printf("二叉树为空!\n");
break;
case '4':
if(T)
{
printf("递归中序遍历二叉树:");
Inorder(T);
printf("\n");
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '5':
if(T)
{
printf("非递归中序遍历二叉树:");
NInorder(T);
printf("\n");
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '6':
if(T)
{
printf("递归后序遍历二叉树:");
Postorder(T);
printf("\n");
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '7':
if(T)
{
printf("非递归后序遍历二叉树:");
NPostorder(T);
printf("\n");
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '8':
if(T)
{
printf("层次遍历二叉树:");
Translever(T);
printf("\n");
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '9':
if(T)
{
printf("输出二叉树:");
Disptree(T);
printf("\n");
printf("\n");
}
else printf("二叉树为空!\n");
break;
default:
sign=0;
printf("程序运行结束，按任意键退出!\n");
}
}
}
|
示例：
转换成双向链表
先序列：H F C D M I N
中序列：C F D H I M N
后序列：C D F I N M H
|
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
|
#include <iostream>
using namespace std;
struct BSTreeNode{
char m_val;
BSTreeNode *m_pLeft;
BSTreeNode *m_pRight;
};
BSTreeNode *pHead;//链表显示的头结点
BSTreeNode *pListIndex;//游标指针
void showOrderLiust(BSTreeNode *pCurrent);
void createBSTree(BSTreeNode *&pCurrent,char ch)
{
if (NULL == pCurrent) {
pCurrent = new BSTreeNode;
pCurrent->m_val = ch;
pCurrent->m_pLeft = NULL;
pCurrent->m_pRight = NULL;
}else {
if (pCurrent->m_val > ch) {
createBSTree(pCurrent->m_pLeft,ch);
}else if (pCurrent->m_val < ch) {
createBSTree(pCurrent->m_pRight,ch);
}
else
{
return;
}
}
}
//遍历二叉树/*先序遍历*/
void PreOrderTraverse(BSTreeNode *pCurrent)
{
if (NULL == pCurrent) {
return;
}
if (NULL!=pCurrent)
{
//先遍历根节点
cout<<pCurrent->m_val<<endl;
//在遍历左节点
PreOrderTraverse(pCurrent->m_pLeft);
//在遍历右节点
PreOrderTraverse(pCurrent->m_pRight);
}
}
//中序遍历
void InOrderTraverse(BSTreeNode *pCurrent)
{
if (NULL == pCurrent) {
return;
}
if (NULL != pCurrent->m_pLeft) {
InOrderTraverse(pCurrent->m_pLeft);
}
showOrderLiust(pCurrent);
//在遍历右节点
if (NULL != pCurrent->m_pRight) {
InOrderTraverse(pCurrent->m_pRight);
}
}
//后序遍历
void EndOrderTraverse(BSTreeNode *pCurrent)
{
if (NULL == pCurrent) {
return;
}
if (NULL != pCurrent->m_pLeft) {
EndOrderTraverse(pCurrent->m_pLeft);
}
cout<<pCurrent->m_val<<endl;
//在遍历右节点
if (NULL != pCurrent->m_pRight) {
EndOrderTraverse(pCurrent->m_pRight);
}
}
/*该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向*/
void showOrderLiust(BSTreeNode *pCurrent)
{
pCurrent->m_pLeft = pListIndex;
if (NULL != pListIndex) {
pListIndex->m_pRight = pCurrent;
}else
{
pHead = pCurrent;
}
pListIndex = pCurrent;
cout<<pCurrent->m_val<<endl;
}
int main(int argc,char**argv)
{
BSTreeNode *pRoot = NULL;
pHead = NULL;
pListIndex = NULL;
createBSTree(pRoot,'H');
createBSTree(pRoot,'F');
createBSTree(pRoot,'C');
createBSTree(pRoot,'D');
createBSTree(pRoot,'M');
createBSTree(pRoot,'I');
createBSTree(pRoot,'N');
PreOrderTraverse(pRoot);
InOrderTraverse(pRoot);
EndOrderTraverse(pRoot);
delete pRoot;
return 0;
}
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/fanyun_01/article/details/57085668