一文读懂较复杂的数据结构——树，二叉树_一棵较为复杂的二叉树

专栏目录（数据结构与算法解析）：https://blog.csdn.net/qq_40344524/article/details/107785323

树

树是n（n>=0）个结点构成的有限集，n=0时称为空树，在任意一棵非空树中有且仅有一个结点称为根结点，其余结点可分为m（m>0）个互不相交的有限集，每个有限集又是一棵树，它们称为根结点的子树。

术语解释

结点的度

当前结点向下直接连接的结点的个数
1

树的度

树中所有结点的度的最大值
1

子结点

一个结点含有的子树的根结点称为该结点的子结点
1

父结点

若一个结点含有子结点，则这个结点称为其子结点的父结点
1

兄弟结点

拥有同一父结点的结点互为兄弟结点
1

叶结点

没有子树的结点叫做叶结点
1

祖先结点

从根到该结点所经分支上的所有结点
1

子孙结点

以某结点为根的子树中任一结点都称为该结点的子孙
1

结点层次

从根开始定义起，根为第1层，根的子结点为第2层，以此类推
1

树的深度

树中所有结点的最大层次
1

路径

从结点n1到结点nk所经过的结点序列叫做n1到nk的路径
1

路径长度

一条路径中所有边的条数称为路径长度
1

森林

多棵互不相交的树组成的集合叫做森林
1

树的类型

无序树

树中任意节点的子结点之间没有顺序关系
1

有序树

树中任意节点的子结点之间有顺序关系
1

二叉树

每个节点最多含有两个子树的树称为二叉树
1

满二叉树

除了叶节点外的所有节点均含有两个子树的树被称为满二叉树
1

完全二叉树

一棵深度为k且有2^k-1 个结点的二叉树称为完全二叉树
1

哈夫曼树

带权路径最短的二叉树称为哈夫曼树
1

树的表示方法

图像表示法

用图像进行表示，如下图所示为一棵树
1

符号表示法

用括号先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；
同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。
前文的树用符号表示法可以表示为：(A(B(D,E(G)),C(F(H))))
1
2
3

遍历表示法

遍历表达法有4种方法：先序遍历、中序遍历、后序遍历、层次遍历
以上图中树为例：
	先序遍历为ABDEGCFH（根-左-右），
	其中序遍历为DBEGACHF（左-根-右），
	其后序遍历为DGEBHFCA（左-右-根），
	其层次遍历为ABCDEFGH
1
2
3
4
5
6

通常在使用中我们用链表来对树进行实现，在开发中最常用的就是二叉树，接下来我们通过代码对上述图示的二叉树的实现和操作进行介绍：

结点结构体

typedef struct TreeNode
{
	int data;					//结点存放的数据，类型可变，此处以整型为例进行讲解
	struct TreeNode* LSonNode;	//存放左子孩子结点地址
	struct TreeNode* RSonNode;	//存放右子孩子结点地址
};
1
2
3
4
5
6

创建树

//创建树，返回根结点,刚创建好的树是一棵只包含根结点的树，根结点存放的数据为Fdata
TreeNode* CreateTree(int Fdata)
{
	TreeNode * TreeHead=(TreeNode *)malloc(sizeof(TreeNode));
	TreeHead->data = Fdata;
	TreeHead->LSonNode = NULL;
	TreeHead->RSonNode = NULL;
	return TreeHead;
}
1
2
3
4
5
6
7
8
9

插入结点

//data表示要插入的值，FatherTree表示父结点，pos表示插入位置（1表示插入右边，0表示插入左边，-1表示任意位置）
bool insertNodeToTree(int data,TreeNode* FatherTree,int pos) 
{
	TreeNode *Node = (TreeNode *)malloc(sizeof(TreeNode));
	Node->data = data;
	Node->LSonNode = NULL;
	Node->RSonNode = NULL;

	if (-1 == pos)
	{
		if (FatherTree->LSonNode == NULL)
		{
			FatherTree->LSonNode = Node;
		}
		else if (FatherTree->RSonNode == NULL)
		{
			FatherTree->RSonNode = Node;
		}
		else
		{
			return false;
		}
	}
	else if (0 == pos)
	{
		if (FatherTree->LSonNode == NULL)
		{
			FatherTree->LSonNode = Node;
		}
		else
		{
			return false;
		}
	}
	else if (1 == pos)
	{
		if (FatherTree->RSonNode == NULL)
		{
			FatherTree->RSonNode = Node;
		}
		else
		{
			return false;
		}
	}
	else
	{
		return false;
	}
	return true;
}
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

获取结点

//根据存储数据值查找结点并返回
TreeNode * findNode(int value,TreeNode *fNode)
{
	TreeNode *ret = NULL;
	if (fNode != NULL)
	{
		if (fNode->data == value)
		{
			ret = fNode;								//查找到结点后将该结点赋值给返回值
		}
		else
		{
			if (ret == NULL)
			{
				ret = findNode(value,fNode->LSonNode);	//递归查找左孩子结点
			}
			if (ret == NULL)
			{
				ret = findNode(value,fNode->RSonNode);	//递归查找右孩子结点
			}
		}
	}
	return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

判断结点是存在

//判断给定结点是否在树中，fNode传入树的根结点，node是要判断的结点
bool isHasNode(TreeNode * fNode,TreeNode *node)
{
	bool ret = false;
	if (fNode!=NULL)
	{
		if (fNode == node)
		{
			ret = true;
		}
		else
		{
			if (ret == false)
			{
				isHasNode(fNode->LSonNode,node);
			}
			if (ret ==false)
			{
				isHasNode(fNode->RSonNode,node);
			}
		}
	}
	return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

获取树的结点数

//获取树的结点个数
int GetNumberNode(TreeNode * fNode) 
{
	int num = 0;
	if (fNode != NULL)
	{
		num++;
		num = num + GetNumberNode(fNode->LSonNode);
		num = num + GetNumberNode(fNode->RSonNode);
	}
	return num;
}
1
2
3
4
5
6
7
8
9
10
11
12

获取树的高度

//通过递归向下查找的方式获取树的高度
int GetTreeHeight(TreeNode *fnode)
{
	int ret = 0;
	
	if (fnode!=NULL)
	{
		if (GetTreeHeight(fnode->LSonNode)>GetTreeHeight(fnode->RSonNode))
		{
			ret = GetTreeHeight(fnode->LSonNode);
		}
		else
		{
			ret = GetTreeHeight(fnode->RSonNode);
		}
		ret++;
	}
	return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

遍历树

//先序遍历二叉树
void PreOrderBiTree(TreeNode *tNode)
{
	if (tNode == NULL)
	{
		return;
	}
	else
	{
		printf("%d ", tNode->data);
		PreOrderBiTree(tNode->LSonNode);
		PreOrderBiTree(tNode->RSonNode);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//中序遍历二叉树
void MiddleOrderBiTree(TreeNode *tNode)
{
	if (tNode == NULL)
	{
		return;
	}
	else
	{
		MiddleOrderBiTree(tNode->LSonNode);
		printf("%d ", tNode->data);
		MiddleOrderBiTree(tNode->RSonNode);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//后序遍历二叉树
void PostOrderBiTree(TreeNode *tNode)
{
	if (tNode == NULL)
	{
		return;
	}
	else
	{
		PostOrderBiTree(tNode->LSonNode);
		PostOrderBiTree(tNode->RSonNode);
		printf("%d ", tNode->data);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

删除结点

bool deleteNode(TreeNode *fNode,TreeNode *node)
{
	if (fNode!=NULL)
	{
		if (node->LSonNode==NULL && node->RSonNode==NULL)
		{
			node = NULL;
			return true;
		}
		else
		{
			deleteNode(fNode,node->LSonNode);
			deleteNode(fNode,node->RSonNode);
		}
	}
	else
	{
		return false;
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

清空树

void clearTree(TreeNode *rNode)
{
	deleteNode(rNode,rNode);
}
1
2
3
4

销毁树

void DestroyTree(TreeNode* treeNode)
{
	clearTree(treeNode);
	free(treeNode);
}
1
2
3
4
5

总结

通过上述介绍可以了解到树的特殊性，它是一个非线性的数据结构，树的实现和操作较之前的几种数据结构复杂很多，在实际生活中也多有用到这样得到结构，本节只对树和二叉树进行了简单的介绍，后续我将针对具体的几种树进行单独介绍。


下一节开始讲解特殊的树——哈夫曼树。


以上是我的一些粗浅的见解，有表述不当的地方欢迎指正，谢谢！

表述能力有限，部分内容讲解的不到位，有需要可评论或私信，看到必回…