二叉树遍历

缘起

邓俊辉 数据结构和算法(C++语言版) 第五章例子

分析

二叉树常见的遍历有 先序遍历、中序遍历、后序遍历、层序遍历, 前三者本质是栈，后者是队列

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
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>

//#define LOCAL
#define N 10

using namespace std;

struct Node { // 节点
	char data; // 节点数据
	Node *left; // 左娃
	Node *right; // 右娃
	int flag; // 标志, 0 表示 目前左子树尚未遍历完, 1表示已经添加了左孩子进栈, 2表示已经添加了右孩子进栈, 具体体现在右子树的节点已经开始加入栈中了, 这个成员变量仅仅用于后续非递归遍历, 其他的用不上
	Node(char data):data(data),left(NULL),right(NULL),flag(0){}
}*root; // 根节点

// 构建二叉树
void build()
{
	root = new Node('A');
	Node *B = new Node('B');
	Node *C = new Node('C');
	Node *D = new Node('D');
	Node *E = new Node('E');
	Node *F = new Node('F');
	Node *G = new Node('G');
	Node *H = new Node('H');
	Node *K = new Node('K');
	root->left = B;
	B->right = C;
	C->left =D;
	root->right = E;
	E->right = F;
	F->left = G;
	G->left = H;
	G->right = K;
}

// 先序遍历递归版
void traversePreRecurse(Node *root)
{
	if(!root) return;
	cout << root->data;
	traversePreRecurse(root->left);
	traversePreRecurse(root->right);
}

// 先序遍历非递归版(即栈版)
void traversePreNonRecurse(Node *root)
{
	stack<Node*> s;
	while(1)
	{
		while(root)
		{
			cout<<root->data;
			s.push(root);
			root = root->left; // 不断的左移
		}
		if (s.empty()) break; // 如果经过上述左移动 依旧是栈空的话, 则表明算法已经结束
		root = s.top();
		s.pop(); // 弹栈(因为它已经cout过了)
		root = root->right; // 得到root的目的仅仅是跳到右子树上去
	}
}

// 中序遍历递归版
void traverseInRecurse(Node *root)
{
	if(!root) return;
	traverseInRecurse(root->left);
	cout << root->data;
	traverseInRecurse(root->right);
}

// 中序遍历非递归版(即栈版)  注意, 和先序遍历非递归版本差别就是 什么时候打印
void traverseInNonRecurse(Node *root)
{
	stack<Node*> s;
	while(1)
	{
		while(root)
		{
			s.push(root); // 不打印, 先全部兜着(因为是中序)
			root = root->left;
		}
		if (s.empty()) break;
		root = s.top();
		s.pop();
		cout<< root->data; // 和先序差别只有这一行而已, 这里是打印中间的节点
		root = root->right;
	}
}

// 后序遍历递归版
void traversePostRecurse(Node *root)
{
	if(!root) return;
	traversePostRecurse(root->left);
	traversePostRecurse(root->right);
	cout << root->data;
}

// 后序遍历非递归版(即栈版)
void traversePostNonRecurse(Node *root)
{
	stack<Node *> s;
	s.push(root);
	while(1)
	{
		if (s.empty()) return; // 如果根节点都出去了，则后序遍历也完了.
		Node *p = s.top();
		s.pop(); // 取顶
		if (!p->flag) // 如果没加入过左孩子
		{
			while(p) // 一路向左加左孩子
			{
				s.push(p);
				p->flag = 1; // 变更状态为已经加入过左孩子
				p = p->left;
			}
		}
		else // 如果已经加入过左孩子了
		{
			if (p->right && p->flag==1) // 如果有右孩子并且尚未加入过右孩子
			{
				p->flag = 2; // 变更状态为已经加入过右孩子
				s.push(p); // 此时p还不能撤, 因为右子树还没考察完毕
				s.push(p = p->right); // 压栈右孩子, 并且跳到右子树上去
			}
			else cout << p->data; // 如果没有右孩子或者已经加过右孩子了, 而弹栈到了自己 表明自已的左边和右边都处理完毕，要处理自己了
		}
	}
}

// 层序遍历, 使用队列
void traverseLevel(Node *root)
{
	queue<Node*> q;
	q.push(root);
	while(!q.empty()) // 只要队列不空
	{
		Node *current = q.front();
		cout << current->data;
		q.pop(); // 出队列
		if (current->left)q.push(current->left);
		if (current->right) q.push(current->right);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	build();
	//traversePreRecurse(root); // ABCDEFGHK
	//traverseInRecurse(root); // BDCAEHGKF
	//traversePostRecurse(root); // DCBHKGFEA
	//traversePreNonRecurse(root);
	//traverseInNonRecurse(root);
	traversePostNonRecurse(root);
	//traverseLevel(root); // ABECFDGHK
	return 0;
}

最后说一下

中序+先序

中序+后序

可以唯一还原一棵二叉树

先序+后序 不可以唯一还原一棵二叉树.

兹麻里, 一定要有中序