C/C++实现二叉树的遍历（深度优先，广度优先）

二叉树的遍历

广度优先遍历

·层次遍历

深度优先遍历

1.前序遍历
2.中序遍历
3.后序遍历

完整代码：

#include<iostream>
using namespace std;
typedef char Type;
//@lining
//二叉树存储结构：二叉链表
typedef struct B
{
	Type data;
	struct B* LChild;
	struct B* RChild;
}BiTreeNode, * BiTree;
//二叉树的深度
int BiTreeDepth(BiTree& T)
{
	int i, j;
	if (!T)
		return 0;
	if (T->LChild)
		i = BiTreeDepth(T->LChild);
	else
		i = 0;
	if (T->RChild)
		j = BiTreeDepth(T->RChild);
	else
		j = 0;
	return i > j ? i + 1 : j + 1;
}
//销毁树
void DestroyBiTree(BiTree& T)
{
	if (T)
	{
		if (T->LChild)                /* 有左孩子 */
			DestroyBiTree(T->LChild); /* 销毁左孩子子树 */
		if (T->RChild)                /* 有右孩子 */
			DestroyBiTree(T->RChild); /* 销毁右孩子子树 */
		delete T;                     /* 释放根结点 */
		T = NULL;                     /* 空指针赋0 */
	}
}
//构造空二叉树T
void InitBiTree(BiTree& T)
{
	T = NULL;
	return;
}
//先序建立二叉树
void CreatBitree(BiTree& T)//传入指针引用
{
	Type ch;
	cin >> ch;
	if (ch == '#')
	{
		T = NULL;
	}
	else
	{
		T = new BiTreeNode;
		T->data = ch;
		//递归
		CreatBitree(T->LChild);//构造左子树
		CreatBitree(T->RChild);//构造右子树
	}
}
//层序遍历二叉树
void LevelorderBitree(BiTree& T)
{
	if (!T)
	{
		return;
	}
	BiTree Q[100],  q = NULL;
	//front作为输出索引，rear作为存储索引
	int front = -1, rear = -1;
	if (!T)
	{
		return;
	}
	Q[++rear] = T;
	while (front != rear)
	{
		q = Q[++front];
		cout << q->data << " ";
		if (q->LChild != NULL)
		{
			Q[++rear] = q->LChild;
		}
		if (q->RChild != NULL)
		{
			Q[++rear] = q->RChild;
		}
	}
}
//先序遍历二叉树
void PreorderBitree(BiTree T)
{
	if (!T)
	{
		return;
	}
	cout << T->data << " ";
	PreorderBitree(T->LChild);
	PreorderBitree(T->RChild);
}
//中序遍历二叉树
void MediumorderBitree(BiTree T)
{
	if (!T)
	{
		return;
	}
	MediumorderBitree(T->LChild);
	cout << T->data << " ";
	MediumorderBitree(T->RChild);
}
//后序遍历二叉树
void PostorderBitree(BiTree T)
{
	if (!T)
	{
		return;
	}
	PostorderBitree(T->LChild);
	PostorderBitree(T->RChild);
	cout << T->data << " ";
}
//判断树是否存在
bool BiTreeEmpty(BiTree& T)
{
	if (!T)
		return false;
	else
		return true;
}
void test()
{
	BiTree T = new BiTreeNode;
	InitBiTree(T);
	cout << "请输入先序遍历顺序下各个结点的值，空结点用#代替:" << endl;
	CreatBitree(T);
	//DestroyBiTree(T);
	if (BiTreeEmpty(T))
	{
		cout << "层序遍历顺序：" << endl;
		LevelorderBitree(T);
		cout << endl << "先序遍历顺序：" << endl;
		PreorderBitree(T);
		cout << endl << "中序遍历顺序：" << endl;
		MediumorderBitree(T);
		cout << endl << "后序遍历顺序：" << endl;
		PostorderBitree(T);
		cout << endl << "二叉树的深度为" << BiTreeDepth(T) << endl;
	}
	else
	{
		cout << "该树不存在" << endl;
	}
	//测试样例：ABDH#K###E##CFI###G#J##
}
int main()
{
	test();
	return 0;
}
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