强烈推荐，超详细实现二叉树的建立（附实现源码）_构建二叉树

1.如何创建一棵二叉树

创建一棵二叉树需要什么
其实答案很简单，无非就是从根节点开始，逐步实现子节点的创建，从而实现树的整体框架
由于树是一种特殊的线性表，所以对于生成后的树，我们应该可以对它进行查找，修改，插入等功能
最后，我们将进行对树的遍历，这里将讨论常用的先序，中序，后序以及层序等四种遍历方式

关于二叉查找树结点的删除，可以查看后续文章
强烈推荐！超详细实现二叉查找树结点的删除（附实现源码）

1.二叉树的存储结构定义

• 一般来说，二叉树使用链表来定义，不同的是，由于二叉树每个结点都存在两条出边，因此指针域变为两个，分别指向左子树和右子树的跟结点地址，因此又把这种链表叫做二叉链表

struct node
{
	int data; //数据域
	node * lchild; //指向左子树根节点的指针
	node * rchild; //指向右子树根节点的指针
};
1
2
3
4
5
6

2.实现二叉树结点的新建、查找、修改

• 如果需要新建结点（例如往二叉树里面插入结点时，可使用下面的函数（返回类型是一个指向node的指针）

node* newNode(int v) { 
	node*Node = new node; //申请一个node类型变量的地址空间
	Node->data = v; //结点权值为v
	Node->lchild = Node->rchild = NULL; //初始状态下无左右孩子
	return Node; //返回新节点的地址
}
1
2
3
4
5
6

• 查找操作是指在给定的数据域内，在二叉树里面找到所有数据域（对多个结点实行操作）为给定数据域的结点，并且对查找到的结点修改为给定的数据域

void search(node*root,int x, int newdata){
	if (root == NULL) return; //考虑为空节点的可能性
	if (root->data == x) {
		root->data = newdata; //找到数据域为x的结点，把它修改为newdata
	}
	search(root->lchild, x, newdata);//往左子树搜索
	search(root->rchild, x, newdata);//往右子树搜索
}
1
2
3
4
5
6
7
8

3.实现二叉树结点的插入

• 关于二叉树结点的插入，由于在没有给出插入条件的问题中，很难给出插入的具体方法。因此这里以在一棵二叉搜索树中插入为例。
• 插入过程的核心思想，是按照给定的插入条件（例中为二叉查找树）找到树里面的边界（死胡同），此处就是查找失败的地方，也是结点需要插入的地方

void insert(node*& root, int x) {  //注意 传入的是结点指针的引用
	if (root == NULL) { //空树，即查找失败，插入结点（递归边界）
		root = newNode(x);
		return;
	}
	if (root->data > x) { //往左子树搜索
		insert(root->lchild, x);
	}
	else insert(root->rchild, x); //往右子树搜索
}
1
2
3
4
5
6
7
8
9
10

• 在上述代码中，一个关键的点就是根节点指针root使用了引用&，这样在函数中可以直接修改原变量。这么做的原因是，在insert函数中新建了一个新结点，并且把新节点的地址赋给了当层的root。如果不采用引用，root = new node 这个语句对root 的修改就无法作用到原变量，也就无法将节点加到二叉树上面。
• 那为什么前面的search 函数不需要加引用呢？因为search 函数修改的是指针root指向的内容，而不是root本身，对结点指向的内容的修改是不需要加引用的

4.二叉树创建过程

• 二叉树的创建，其实就是二叉树结点的插入过程，比较常用的写法是把需要插入的数据域存储在数组中，并且最终返回插入结点后树的根结点

node*create(int data[], int n) {
	node* root = NULL;     //新建空根结点
	for (int i = 0; i < n; i++) {
		insert(root, data[i]); //将data[0]到data[n-1]插入二叉树
	}
	return root; //返回根节点
}
1
2
3
4
5
6
7

2.二叉树的遍历

• 在下文提到的四种遍历方式中，像先、中、后三种遍历方式，都是基于深度优先搜索（DFS)，而层序遍历则是基于广度搜索（BFS）
• 由于树本质上是一种递归结构，因此可以抽象的把树看成root， 左子树 ，右子树 三部分，且对左右子树也进行同样的划分
• 前三种遍历中无论哪一种，都是先开始左子树的遍历，再到右子树。所谓先、中、后则是代表根节点在访问过程中的位置

1.先序遍历

• 由定义知，先序遍历的遍历顺序是根节点->左子树->右子树，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界

所以核心问题是处理好 递归式与递归边界

• 实现效果图如下：
  
• 代码实现如下：

void preorder(node* root) { //先序遍历
	if (root == NULL) return; //到达空树，即递归边界
	cout << root->data << endl;; //访问根节点数据域
	preorder(root->lchild); //访问左子树
	preorder(root->rchild); //访问右子树
}
1
2
3
4
5
6

2.中序遍历

• 中序遍历也是一样的思想，中序遍历的遍历顺序是左子树->根节点->右子树，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界
• 实现效果图如下：
  
• 代码实现如下：

void inorder(node* root) { //中序遍历
	if (root == NULL) return; //到达空树，即递归边界
	inorder(root->lchild); //访问左子树
	cout << root->data << endl;; //访问根节点数据域
	inorder(root->rchild); //访问右子树
}
1
2
3
4
5
6

3.后序遍历

• 后序遍历同上，中序遍历的遍历顺序是左子树->右子树->根节点，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界
• 实现效果图如下：
  
• 代码实现如下：

void postorder(node* root) { //后序遍历
	if (root == NULL) return; //到达空树，即递归边界
	preorder(root->lchild); //访问左子树
	preorder(root->rchild); //访问右子树
	cout << root->data << endl;; //访问根节点数据域
}
1
2
3
4
5
6

4.层序遍历

• 层序遍历是按照层次顺序从根节点向下逐层进行遍历，且对同一层的结点由左往右进行遍历，由于存在回溯问题，因此需要用到队列这种数据结构

• 具体实现思路如下

  • ①将根节点root 加入队列q
  • ②取出队首结点，访问它
  • ③若该结点有左孩子，则将左孩子入队
  • ④该结点有有孩子，则将右孩子入队
  • 重复进行步骤②，直到队列为空

• 实现效果图如下：
  

• 实现代码如下：

void LayerOrder(node* root) { //层序遍历
	queue<node*> q; //队列里面存的是地址 记得导入头文件<quene>
	q.push(root);  //将根节点入队
	while (!q.empty())  //退出条件为队列为空
	{
		node* now = q.front(); //取出队首元素
		cout << now->data << endl;
		q.pop();        //弹出队首元素
		if (now->lchild != NULL) q.push(now->lchild);//左子树非空则压入队列
		if (now->rchild != NULL) q.push(now->rchild);//右子树非空则压入队列
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

3.源码实现

#include <iostream>
#include <queue>
using namespace std;

struct node
{
	int data;
	node * lchild;
	node * rchild;
};

node* newNode(int v) { 
	node*Node = new node; //申请一个node类型变量的地址空间
	Node->data = v; //结点权值为v
	Node->lchild = Node->rchild = NULL; //初始状态下无左右孩子
	return Node; //返回新节点的地址
}

void search(node*root,int x, int newdata){
	if (root == NULL) return; //考虑为空节点的可能性
	if (root->data == x) {
		root->data = newdata; //找到数据域为x的结点，把它修改为newdata
	}
	search(root->lchild, x, newdata);//往左子树搜索
	search(root->rchild, x, newdata);//往右子树搜索
}

void insert(node*& root, int x) {
	if (root == NULL) { //空树，即查找失败，插入结点（递归边界）
		root = newNode(x);
		return;
	}
	if (root->data > x) { //往左子树搜索
		insert(root->lchild, x);
	}
	else insert(root->rchild, x); //往右子树搜索
}

node*create(int data[], int n) {
	node* root = NULL;     //新建空根结点
	for (int i = 0; i < n; i++) {
		insert(root, data[i]); //将data[0]到data[n-1]插入二叉树
	}
	return root; //返回根节点
}

void preorder(node*root) { //先序遍历
	if (root == NULL) return; //到达空树，即递归边界
	cout << root->data << endl;; //访问根节点数据域
	preorder(root->lchild); //访问左子树
	preorder(root->rchild); //访问右子树
}

void inorder(node*root) { //中序遍历
	if (root == NULL) return; //到达空树，即递归边界
	inorder(root->lchild); //访问左子树
	cout << root->data << endl;; //访问根节点数据域
	inorder(root->rchild); //访问右子树
}
void postorder(node* root) { //后序遍历
	if (root == NULL) return; //到达空树，即递归边界
	preorder(root->lchild); //访问左子树
	preorder(root->rchild); //访问右子树
	cout << root->data << endl;; //访问根节点数据域
}

void LayerOrder(node* root) { //层序遍历
	queue<node*> q; //队列里面存的是地址 记得导入头文件<quene>
	q.push(root);  //将根节点入队
	while (!q.empty())  //退出条件为队列为空
	{
		node* now = q.front(); //取出队首元素
		cout << now->data << endl;
		q.pop();        //弹出队首元素
		if (now->lchild != NULL) q.push(now->lchild);//左子树非空则压入队列
		if (now->rchild != NULL) q.push(now->rchild);//右子树非空则压入队列
	}
}
int main() {
	int n = 10;
	int nums[10] = { 5,3,8,2,4,1,6,7,9,0 };
	node* root = create(nums, 10);
	//search(root, 7, 11); //查找替换
	preorder(root);//前序遍历
	//inorder(root);    //中序遍历
	//postorder(root);  //后序遍历
	//LayerOrder(root);  //层序遍历
	system("pause");
	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