一文解决数据结构——树（一）二叉树

数据结构——树

定义

树是一个n个节点的有限集，如果n=0时，则称之为空树。

树的三大性质

1. 树的定义是递归的，树的定义中又用到自身
2. 树的根节点没有前驱，除根节点以外，其他所有节点有且只有一个前驱
3. 树中的所有接待你可以有0个或者多个后继

二叉树

概念

• 一种特殊的树形结构
• 每个节点至多只有两个子树

二叉树的遍历

二叉树的遍历分为三种：

• 前序（根->左->右）
• 中序（左->根->右）
• 后序（左->右->根）

以下二叉树为例，讲述二叉树的遍历方式

前序

前序遍历： 是从树的根节点出发，先遍历树的左侧子树，然后到了左侧子树的根节点，再遍历左侧又到了下一个子树的根节点，依此递归进行，遍历完左侧再遍历右侧。最后，整棵树就会 被遍历完。

上图的遍历顺序：G->D->A->F->E->M->H->Z

中序

中序遍历： 是从左子树出发，由于左子树也有左子树，递归到最左的子树，然后再遍历其根节点，再遍历其右子树，一棵一棵子树的向上递归（左根右）遍历，回到原根节点后，再向下一棵一棵子树的向下递归（左根右）遍历。

上图的遍历顺序：A->D->E->F->G->H->M->Z

后序

后序遍历： 同理上面的过程，只是将顺序换为：左右根。先通过遍历左侧然后右侧最后遍历根部的顺序，先从左一棵一棵子树的递归（左右根）遍历到原根节点，再从右边一棵一棵子树的递归遍（左右根）历到原根节点，最后，再遍历原根节点。

上图的遍历顺序：A->E->F->D->H->Z->M->G

代码实现

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

// 构造树的节点
typedef struct node {
	// 树节点的存储域
	ElemType data;
	// 指向树的左枝指针域
	struct node * left;
	// 指向树的右枝指针域
	struct node * right;
}Node;

// 构造树的根节点
typedef struct tree {
	// 定义根（整个树）的指针域
	// 是整个树的最初始点
	Node * root;
}Tree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 先创建一个空树
Tree tree;
tree.root = NULL;
1
2
3

其实，这幅图其实并不是十分对应上述代码，上述的创建空树的部分其实只是创建一个地址而已，而这幅图既有左右枝脉指针，以及节点的存储空间，其实是在后面的步骤中开辟了节点空间时，才会所具备的结构，这里就大致说道一二耳。

// 向节点中插入数据
void insert(Tree * tree, int value){
	// 为节点开辟存储空间，这里就会形成上图的结构
	Node* node = (Node*)malloc(size(Node));
	// 将值插入
	node->data = value;
	// 左右指针设置为空
	node->left = NULL;
	node->right = NULL;
	// 若树的根节点为空，则将刚刚创建的节点设置为根节点
	if(tree->root == NULL){
		tree->root = node;
	} else{
		// 从树根开始遍历比较
		// 小于根的放置于左枝脉，大于根的放置于右枝脉
		Node* temp = tree->root;
		while(temp != NULL){
			// 如果插入值小于根节点的值
			if(value < temp->data){
				// 小于插入值将其接入左脉
				// 这里的插入是直接插到整个树的最左边
				if(temp->left == NULL){
					// 移到最左边接上上面新建的节点
					temp->left = node;
					return;
				}else{
					// 由于直接插入到了树的最外处
					// 还要继续比对树根节点的左枝脉的其他子树的根节点
					// 找到一个合适的位置放置新建的节点
					// 所以这里就要将根节点向左移动继续递归排序
					// 这里就所谓的二叉树排序的原理
					temp = temp->left;
				}
			} else{
				// 若插入值大于树的根节点,则放入右枝脉
				if(temp->right == NULL){
					temp->right = node;
					return;
				}else{
					// 同理上面的，继续递归比较
					temp = temp->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

下面就可以实现几个有关树的API

// 这里是使用中序遍历二叉树：左根右。其他的遍历方式大家可以一一实现
void traverse(Node* node){
	if(node != NULL){
		traverse(node->left);
		printf("%d",node->data);
		traverse(node->right);
	}
}
// 销毁树
void distroy(Node* node){
	if(node != NULL){
		// 销毁左支脉
		distroy(node->left);
		// 销毁右支脉
		destroy(node->right);
		free(node);
		node = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这就是树以及对其性质的介绍，和普通二叉树的构造。下一节我们将探寻有关哈夫曼树及红黑树的构造。