二叉搜索树(BST)创建以及层次、先、中、后序遍历_creatbst是什么

---

前言

提起二叉树，刚刚结束的大二上学期那可真把我折磨死了，当时连c都没摸清楚的我，至今还记得实验课上老师要求我们写出二叉树的先中后序遍历时我尴尬的表情QAQ，那时真是的太难了，连一个for循环都要反复去理解才看得懂。趁寒假比较闲，笔者又去学了一遍二叉树，顺便写个博客，记录一下自我的提升。那么，我们开始吧~~

结构体定义：

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
1
2
3
4
5
6
7
8

---

创建二叉搜索树(BST)

void Tree::createBst(vector<int>& nodes) {
	//初始化根节点
	root = new TreeNode(nodes[0]);
	for (int i = 1; i < nodes.size(); ++i) {
		//将每一个数添加到树中
		TreeNode* node = root;//从根节点查找
		int val = nodes[i];
		TreeNode* newNode = new TreeNode(val);
		while (node) {
			if (val < node->val) {
				if (node->left == nullptr) {//已经到了枝节末端
					node->left = newNode;
					break;
				}
				node = node->left;
			}
			else {
				if (node->right == nullptr) {
					node->right = newNode;
					break;
				}
				node = node->right;
			}
		}
	}
}
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

层次遍历

使用一个队列来对孩子节点进行存储，因为队列拥有先进先出(FIFO)的特点，在遍历到一个节点时都是将其子节点依次放入队列中，那么等遍历到这些子节点时也是一连串地，形成了我们需要的层次感
普通的顺序输出:

void Tree::levelTraversal(TreeNode* root){
	queue<TreeNode*> que;
	que.emplace(root);
	while (que.empty() == 0) {
		TreeNode* node = que.front();
		que.pop();
		cout << node->val << " ";
		if (node->left != nullptr)
			que.push(node->left);
		if (node->right != nullptr)
			que.push(node->right);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

再贴一个格式化输出的代码：（按行输出）

void Tree::levelTraversalFormat(TreeNode* root){
	queue<TreeNode*> que;
	que.emplace(root);
	//用两个指针分别记录当前层最后一个节点以及下一层最右节点的位置
	TreeNode* cur = root, * next = nullptr;
	while (que.empty() == 0) {
		TreeNode* node = que.front();
		que.pop();
		cout << node->val << " ";
		if (node->left != nullptr) {
			que.push(node->left);
			next = node->left;
		}
		if (node->right != nullptr) {
			que.push(node->right);
			next = node->right;
		}
		if (node == cur) {//如果到达了该层最后一个节点，更新cur
			cout << endl << "\t";
			cur = next;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

递归

递归遍历二叉树的代码量比较少，较非递归而言更容易理解，由于三种写法过于相似，这里只贴上前序遍历，中序、后序可以查看最后的完整代码。

void Tree::preOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	cout << root->val << " ";
	preOrder(root->left);
	preOrder(root->right);
}
1
2
3
4
5
6
7

---

递归的处理方式是系统自动将暂时未处理的信息存入内存栈中，最后一步一步完成，因此我们可以借助STL中的模板类 栈(stack) 实现迭代；
需要注意的是栈是 先进后出(FILO) 的规则，所以我们将数据压入栈中的时候需要留心它们的先后顺序，以免处理出错。

先序非递归

对于先序遍历，只需要注意一下压栈的顺序：先压入右节点，再压入左节点，这样在弹栈的时候可以表现出先弹出左节点再弹出右节点的效果。

void Tree::nonRecurPreOrder(TreeNode* root) {//根左右
	stack<TreeNode*> stk;
	stk.push(root);
	while (stk.empty() == 0) {// 这样写是为了增强代码可读性，等价于 !stk.empty()
		TreeNode* node = stk.top();
		stk.pop();
		cout << node->val << ' ';
		if (node->right)
			stk.push(node->right);//先压入右节点
		if (node->left)
			stk.push(node->left);//再压入左节点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

中序非递归

一般求解

中序非递归与先序（前序）的代码风格差异很大，原因在于 先序遍历中根节点一经访问就可以对其操作，但是对于中序(LDR)，也就是先找左孩子，直到该节点的没有左孩子或者它的左孩子以及被处理掉了，这时才能输出中间节点（根节点）;
首先需要处理其左子树，通过一个while循环找到该节点对应的最左端的节点，对其操作后继续对其右子树进行相同的过程(找到右子节点最左端的节点)
代码如下：

void Tree::nonRecurinOrder(TreeNode* root) {
	stack<TreeNode*> stk;
	TreeNode* cur = root;
	while (cur != nullptr || stk.empty() == 0) {
		while (cur != nullptr) {
			stk.push(cur);
			cur = cur->left;
		}
		cur = stk.top();
		cout << cur->val << " ";
		stk.pop();
		cur = cur->right;//继续查找右孩子
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

标记法

中序非递归另一种写法：

无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢， 就是要处理的节点放入栈之后，紧接着放入一个NULL作为标记。

void Tree::nonRecurinOrderMark(TreeNode* root) {
	//在压入根节点时多压入一个NULL: 含义是待处理节点(下一回遇上的时候可以直接输出，而不必要判断再加入它的孩子节点)
	stack<TreeNode*> stk;
	stk.push(root);
	while (stk.empty() == 0) {
		TreeNode* node = stk.top();
		stk.pop();
		if (node != nullptr) {//不为空节点，对其进行存储
			if (node->right)
				stk.push(node->right);
			stk.push(node);
			stk.push(nullptr);
			if (node->left)
				stk.push(node->left);
		}
		else {
			node = stk.top();//再次获取栈顶元素， 然后直接输出，不需要再进行压栈
			stk.pop();
			cout << node->val << " ";
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

后序非递归

void Tree::nonRecurPostOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	stack<TreeNode*> stk;
	TreeNode* prev = nullptr;
	while (root != nullptr || !stk.empty()) {
		while (root != nullptr) {
			stk.emplace(root);
			root = root->left;
		}
		root = stk.top();
		stk.pop();
		if (root->right == nullptr || root->right == prev) {
			cout << root->val << " ";
			prev = root;
			root = nullptr;
		}
		else {
			stk.emplace(root);
			root = root->right;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

完整代码

头文件

#pragma once
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() :val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) :val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode * _left, TreeNode * _right) :
		val(x), left(_left), right(_right) {}
};

class Tree {
public:
	TreeNode* root;
	void createBst(vector<int>& nodes);
	void levelTraversal(TreeNode* root);
	void levelTraversalFormat(TreeNode* root);
	void preOrder(TreeNode* root);
	void inOrder(TreeNode* root);
	void postOrder(TreeNode* root);
	void nonRecurPreOrder(TreeNode* root);
	void nonRecurinOrder(TreeNode* root);
	void nonRecurinOrderMark(TreeNode* root);
	void nonRecurPostOrder(TreeNode* root);
};

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

源文件（函数体实现）

#include "Tree.h"

void Tree::createBst(vector<int>& nodes) {
	//初始化根节点
	root = new TreeNode(nodes[0]);
	for (int i = 1; i < nodes.size(); ++i) {
		//将每一个数添加到树中
		TreeNode* node = root;//从根节点查找
		int val = nodes[i];
		TreeNode* newNode = new TreeNode(val);
		while (node) {
			if (val < node->val) {
				if (node->left == nullptr) {//已经到了枝节末端
					node->left = newNode;
					break;
				}
				node = node->left;
			}
			else {
				if (node->right == nullptr) {
					node->right = newNode;
					break;
				}
				node = node->right;
			}
		}
	}
}

void Tree::levelTraversal(TreeNode* root){
	queue<TreeNode*> que;
	que.emplace(root);
	while (que.empty() == 0) {
		TreeNode* node = que.front();
		que.pop();
		cout << node->val << " ";
		if (node->left != nullptr)
			que.push(node->left);
		if (node->right != nullptr)
			que.push(node->right);
	}
}

void Tree::levelTraversalFormat(TreeNode* root){
	queue<TreeNode*> que;
	que.emplace(root);
	//用两个指针分别记录当前层最后一个节点以及下一层最右节点的位置
	TreeNode* cur = root, * next = nullptr;
	while (que.empty() == 0) {
		TreeNode* node = que.front();
		que.pop();
		cout << node->val << " ";
		if (node->left != nullptr) {
			que.push(node->left);
			next = node->left;
		}
		if (node->right != nullptr) {
			que.push(node->right);
			next = node->right;
		}
		if (node == cur) {//如果到达了该层最后一个节点，更新cur
			cout << endl << "\t";
			cur = next;
		}
	}
}

void Tree::preOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	cout << root->val << " ";
	preOrder(root->left);
	preOrder(root->right);
}

void Tree::inOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	inOrder(root->left);
	cout << root->val << " ";
	inOrder(root->right);
}

void Tree::postOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	postOrder(root->left);
	postOrder(root->right);
	cout << root->val << " ";
}

void Tree::nonRecurPreOrder(TreeNode* root) {//根左右
	stack<TreeNode*> stk;
	stk.push(root);
	while (stk.empty() == 0) {
		TreeNode* node = stk.top();
		stk.pop();
		cout << node->val << ' ';
		if (node->right)
			stk.push(node->right);
		if (node->left)
			stk.push(node->left);
	}
}

void Tree::nonRecurinOrder(TreeNode* root) {
	stack<TreeNode*> stk;
	TreeNode* cur = root;
	while (cur != nullptr || stk.empty() == 0) {
		while (cur != nullptr) {
			stk.push(cur);
			cur = cur->left;
		}
		cur = stk.top();
		cout << cur->val << " ";
		stk.pop();
		cur = cur->right;//继续查找右孩子
	}
}

void Tree::nonRecurinOrderMark(TreeNode* root) {
	//在压入根节点时多压入一个NULL: 含义是待处理节点(下一回遇上的时候可以直接输出，而不必要判断再加入它的孩子节点)
	stack<TreeNode*> stk;
	stk.push(root);
	while (stk.empty() == 0) {
		TreeNode* node = stk.top();
		stk.pop();
		if (node != nullptr) {
			if (node->right)
				stk.push(node->right);
			stk.push(node);
			stk.push(nullptr);
			if (node->left)
				stk.push(node->left);
		}
		else {
			node = stk.top();
			stk.pop();//是空节点
			cout << node->val << " ";
		}
	}
}


void Tree::nonRecurPostOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	stack<TreeNode*> stk;
	TreeNode* prev = nullptr;
	while (root != nullptr || !stk.empty()) {
		while (root != nullptr) {
			stk.emplace(root);
			root = root->left;
		}
		root = stk.top();
		stk.pop();
		if (root->right == nullptr || root->right == prev) {
			cout << root->val << " ";
			prev = root;
			root = nullptr;
		}
		else {
			stk.emplace(root);
			root = root->right;
		}
	}
}
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

源文件（主函数main.cpp）

#include "Tree.h"

int main() {
	Tree t;
	vector<int> nodes{ 3,2,1,5,4 };
	t.createBst(nodes);
	cout << endl << endl << " 层次遍历:\n\t";
	t.levelTraversal(t.root);
	cout << endl << endl << " 层次遍历(按层输出):\n\t";
	t.levelTraversalFormat(t.root);
	cout << endl << endl << " 先序递归遍历:\n\t";
	t.preOrder(t.root);
	cout << endl << endl << " 中序递归遍历:\n\t";
	t.inOrder(t.root);
	cout << endl << endl << " 后序递归遍历:\n\t";
	t.postOrder(t.root);
	cout << endl << endl << " 先序非递归遍历:\n\t";
	t.nonRecurPreOrder(t.root);
	cout << endl << endl << " 中序非递归遍历:\n\t";
	t.nonRecurinOrder(t.root);
	cout << endl << endl << " 中序非递归遍历(标记法):\n\t";
	t.nonRecurinOrderMark(t.root);
	cout << endl << endl << " 后序非递归遍历:\n\t";
	t.postOrder(t.root);
	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

运行效果图

总结

这里引用[代码随想录]中对于中序遍历的一段总结：

此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不想递归写法那样代码稍做调整，就可以实现前后中序。

「这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进vec数组中）可以同步处理，但是中序就无法做到同步！」