【二叉树的创建】c++实现二叉树的创建_c++创建二叉树

参考：
1、数据结构图文解析之：树的简介及二叉排序树C++模板实现.
2、C语言创建二叉树过程中遇到的一些问题

二叉树的创建：

树节点的结构：

//二叉树的节点的结构
struct TreeNode
{
	char  value=0; //结束符'\0'
	TreeNode* left=NULL;
	TreeNode* right=NULL;
};
1
2
3
4
5
6
7

递归创建二叉树（先序）：

//传递节点指针的指针！！！重要
void CreateTree(TreeNode*& everyTreeNode)
{
	char val;
	cin >> val;
	//输入#表示空节点
	if (val == '#')
	{
		//该节点为空，结束此次函数调用（孩子为空，回到双亲节点）
		everyTreeNode = NULL;
	}
	else
	{
		//
		everyTreeNode = new TreeNode;//产生新的树节点
		everyTreeNode->value = val;
		CreateTree(everyTreeNode->left);//把新的树节点的左孩子视为根节点调用创建树的函数
		CreateTree(everyTreeNode->right);//把新的树节点的右孩子视为根节点调用创建树的函数
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

在这一步我纠结了很久，也找了很多代码来跑，终于在 参考2 找到了错误的原因：
我的错误代码：

 void CreateTree(TreeNode* everyTreeNode)
1

这里传递的参数是树节点的指针，传递这个参数时相当于传递了变量的形参，你对 *everyTreeNode 的操作不影响你的目标 tree 的值。

正确代码：

void CreateTree(TreeNode*& everyTreeNode)
1

参考：二叉树为什么用二级指针来构造的原因

二叉树的递归遍历

//遍历顺序：根左右
void PreOrder(TreeNode* everyTreeNode)
{
	if (everyTreeNode)
	{
		cout << everyTreeNode->value<<" " ; 
		PreOrder(everyTreeNode->left);
		PreOrder(everyTreeNode->right);
	}
}
//遍历顺序：左根右
void InOder(TreeNode* everyTreeNode)
{
	if (everyTreeNode)
	{
		
		InOder(everyTreeNode->left);
		cout << everyTreeNode->value << " ";
		InOder(everyTreeNode->right);
	}
}
//遍历顺序：左右根
void PostOrder(TreeNode* everyTreeNode)
{
	if (everyTreeNode)
	{
		PostOrder(everyTreeNode->left);
		PostOrder(everyTreeNode->right);
		cout << everyTreeNode->value << " ";
	}
}
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

二叉树的递归遍历比较简单，关键就是把节点和它的孩子看做整体
1、先输出节点的值在输出左右孩子的值就是先序
2、先输出左孩子的值，再输出节点的值，最后输出右孩子的值就是后序
3、先输出左右孩子的值在输出节点的值就是后序

小结：

二叉树的创建本质上还是指针的应用，只要理解了指针、结构体，二叉树的数据结构也不难理解。
至于遇到了传递树节点形参的坑，说明我对指针这部分内容了解的还不是特别透彻，对二级指针更是没有概念，还是得好好学。

源码

最后发个源码：

#include<iostream>
using namespace std;

//二叉树的节点的结构
struct TreeNode
{
	char  value=0;
	TreeNode* left=NULL;
	TreeNode* right=NULL;
};
//全局变量 方便查看传递的是形参还是实参
TreeNode* tree = new TreeNode;

//传递节点指针的指针！！！重要
void CreateTree(TreeNode*& everyTreeNode)
{
	char val;
	cin >> val;
	if (val == '#')
	{
		everyTreeNode = NULL;
	}
	else
	{
		everyTreeNode = new TreeNode;//产生新的子树
		everyTreeNode->value = val;
		CreateTree(everyTreeNode->left);//递归创建左子树
		CreateTree(everyTreeNode->right);//递归创建右子树
	}
}

//遍历顺序：根左右
void PreOrder(TreeNode* everyTreeNode)
{
	if (everyTreeNode)
	{
		cout << everyTreeNode->value<<" " ; 
		PreOrder(everyTreeNode->left);
		PreOrder(everyTreeNode->right);
	}
}
//遍历顺序：左根右
void InOder(TreeNode* everyTreeNode)
{
	if (everyTreeNode)
	{
		
		InOder(everyTreeNode->left);
		cout << everyTreeNode->value << " ";
		InOder(everyTreeNode->right);
	}
}
//遍历顺序：左右根
void PostOrder(TreeNode* everyTreeNode)
{
	if (everyTreeNode)
	{
		PostOrder(everyTreeNode->left);
		PostOrder(everyTreeNode->right);
		cout << everyTreeNode->value << " ";
	}
}
int main()
{
	cout << "先序输入二叉树的元素：" << endl;
	CreateTree(tree);
	cout << endl << "先序递归遍历二叉树" << endl;
	PreOrder(tree);
	cout << endl << "中序递归遍历二叉树" << endl;
	InOder(tree);
	cout << endl << "后序递归遍历二叉树" << endl;
	PostOrder(tree);
	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