二叉树

| 分类于

前言

在我们日常生活中经常能见到各种类似树形的结构,我们的家谱,公司员工的等级分化,以至于我们操作系统中的磁盘文件结构都像一颗树,由一个总的根部向下蔓延拓展。在数据结构中也一样存在这样的存储结构，我们将他称为树，树是一种十分重要的存储类型，他可以实现一些特定的算法，从而完成某些特定的需求。二叉树便是树形结构中的一种，也是我们经常用到的树形结构。今天我在这里对二叉树的实现及对一颗二叉树的操作进行了总结 ~

什么是二叉树?

二叉树是一种特殊的树,具有如下特点:
①每个节点最多有两个子树,节点的度最大为2.
②左子树和右子树是有顺序的,次序不能颠倒.
③即使某节点只有一子子树,也要区分左右树
二叉树有五种基本形态,在以后功能的实现过程中,我们经常要将各种情况全部考虑全面
五种基本形态:

二叉树的一些相关概念

1.节点的度:节点所拥有的子树的个数成为该节点的度;
2.叶子节点:度为0的节点称为叶子节点,或者称为终端节点;
3.分支节点:度不为0的节点称为分支节点,或称为非终端节点.一棵树的节点除叶节点外,其余的都是分支节点.
4.左孩子、右孩子、双亲:树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
5.路径、路径长度:如果一棵树的一串结点n1,n2,…,nk 有如下关系：结点ni 是ni+1的父结点（1≤i<k）,就把n1,n2,…,nk 称为一条由n1 至nk 的路径。这条路径的长度是k-1。
6.祖先、子孙:在树中，如果有一条路径从结点M 到结点N，那么M 就称为N的祖先，而N 称为M 的子孙。
7.结点的层数:规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
8.树的深度:树中所有结点的最大层数称为树的深度。
9.树的度:树中各结点度的最大值称为该树的度。
10.满二叉树:在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子节点都在同一层上就是一颗满二叉树

11.完全二叉树:如果一颗具有n个节点的二叉树的结构与满二叉树的前n个结点的结构相同,称为完全二叉树

代码实现二叉树

前序中序后序表示一颗二叉树

在屏幕上直观的看我们知道二叉树就是一个树形的结构,他由一个根蔓延开来,但是我们如何用数据的方式来表示一颗二叉树呢?这里便需要知道二叉树的遍历方法:前序遍历,中序遍历,后序遍历以及层序遍历
举个栗子,如图所示二叉树(A):

前序遍历(根,左子树,右子树): ABCDEFHIG
中序遍历(左子树,根,右子树): DBCAFIHEG
后序遍历(左子树,右子树,根): DCBIHFGEA
层序遍历(从第一层开始按层遍历): ABECFGDHI
造成前中后序遍历结果的不一致的原因是每一种遍历方法所遵循的规则不相同,具体如下:
先序：考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)
中序：考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)
后序：考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根

二叉树的存储结构

二叉树主要有顺序存储结构和链式存储结构两种,顺序存储结构在存储完全二叉树的时候即简单又省空间但在存储一般二叉树尤其单支树的时候,存储空间的利用不高,所以我们一律采用链式存储方式来存储二叉树
链式存储方式举例,例如此树采用链式存储的方式便如下所示:

根结点的定义

1
2
3
4
5
6
7
8
typedef int DataType;

typedef struct BinTreeNode
{
	DataType data;
	struct BinTreeNode* left;   //指向左子树的指针
	struct BinTreeNode* right;   //指向右子树的指针
}BNode;

树的返回类型

我们想要最终的创建好的树返回根结点的地址以及已经用过的结点数,所以我们自定义一个结点的返回类型RESULT,它包含两部分,结点的地址和创建过程中使用掉的结点数

1
2
3
4
5
typedef struct
{
	BNode* root;
	int used;
}RESULT;

树的创建过程

此文我们都用如下这同一颗树(B)

在创建的过程中我们采用前序遍历的方法,即根,左子树,右子树。
注意:在整个二叉树的应用中我们会频繁的使用到递归函数,在使用递归函数的时候,我们一定要搞清楚两个问题:1.终止条件; 2.子问题及其递推方式

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
BNode* creatNode(DataType data)
{
	BNode* newBnode = (BNode* )malloc(sizeof(BNode));
	newBnode->data = data;
	newBnode->left = newBnode->right = NULL;
	return newBnode;
}

RESULT creatTree(DataType preorder[], int size)
{
	if (size == 0)  //size为0,树不存在
	{
		RESULT result = { NULL, 0 };
		return result;
	}

	//采用前序遍历的思想创建二叉树
	//根,左子树,右子树

	//先创建根节点
	DataType rootValue = preorder[0];
	if (rootValue == -1)  //只有一个空结点
	{
		RESULT result = { NULL, 1 };
		return result;
	}

	BNode* root = creatNode(rootValue);

	//创建左子树
	RESULT lroot = creatTree(&preorder[1], size - 1);
	root->left = lroot.root;
	//创建右树
	RESULT rroot = creatTree(&preorder[1 + lroot.used],size-1-lroot.used);
	root->right = rroot.root;

	RESULT result = { root, 1 + lroot.used + rroot.used };
	return result;
}

此时便已经创建好了一颗二叉树

二叉树的应用

二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Preorder(BNode* root)
{
	if (root == NULL)  //终止条件
	{
		return ;
	}

	//根
	printf("%d", root->data);
	//左子树,子问题用递归处理
	Preorder(root->left);
	//右子树,子问题用递归处理
	Preorder(root->right);
}

二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
void Inorder(BNode* root)
{
	if (root == NULL)
	{
		return;
	}

	Inorder(root->left);
	printf("%d", root->data);
	Inorder(root->right);
}

二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
void Postorder(BNode* root)
{
	if (root == NULL)
	{
		return;
	}

	Inorder(root->left);
	Inorder(root->right);
	printf("%d", root->data);
}

求二叉树所有结点的个数

1
2
3
4
5
6
7
8
9
int GetSize(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return GetSize(root->left) + GetSize(root->right) + 1;
}

求二叉树叶子节点的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int GetLeafSize(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return GetLeafSize(root->left) + GetLeafSize(root->right);
	}
}

求二叉树某一层的结点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
int GetLevelSize(BNode* root,int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return GetLevelSize(root->left, k - 1) + GetLevelSize(root->right, k - 1);
}

求二叉树的树高

分别求两个子树的高度,较高者加1为整个树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAX(a,b) ((a) > (b) ? (a) : (b))

int GetHight(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftHeight = GetHight(root->left);
	int rightHeight = GetHight(root->right);
	return MAX(leftHeight, rightHeight)+1;
}

在二叉树中查找某个结点,找到了则返回该结点地址,没有找到则返回NULL

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
BNode* searchNode(BNode* root,DataType dest)
{
	//树为空
	if (root == NULL)
	{
		return NULL;
	}
	//要查找的数为根节点
	if (root->data == dest)
	{
		return root;
	}
	//左子树中查找
	BNode* node = searchNode(root->left, dest);
	if (node != NULL)
	{
        return node;
	}
	//右子树中查找
	node = searchNode(root->right, dest);
	if (node != NULL)
	{
		return node;
	}
	else
	{
		return NULL;
	}
}


以下两个问题的实现需要用到队列

层序遍历

运用队列先进先出的特点从根节点开始按层遍历二叉树,每出队一个结点,便让此节点将其两个孩子结点带入队列,从而实现层序遍历二叉树

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
void LevelOrder(BNode* root)
{
	Queue queue;
	QueueInit(&queue);
	if (root == NULL)
	{
		return;
	}

	QueuePush(&queue, root);
	while (!QueueEmpty(&queue))
	{
		BNode* top = QueueFront(&queue);
		QueuePop(&queue);

		if (top->left != NULL)
		{
			QueuePush(&queue, top->left);
		}

		if (top->right != NULL)
		{
			QueuePush(&queue, top->right);
		}
	}
	QueueDestroy(&queue);
}

判断二叉树是否是完全二叉树

完全二叉树的特点:除了叶子结点以外所有的结点都有两个孩子结点
我们可以观察一下完全二叉树和不完全二叉树在表示上有什么不同,我们用带空结点前序的方式分别表示一下二叉树A和二叉树B(x表示空结点)

1
2
二叉树A: ABxCDxxxEFXHIXX
二叉树B: ABDxxExxCxx

通过观察我们可以发现完全二叉树的空结点只会出现在叶子节点的孩子位置上,而非完全二叉树的空结点却不一样,他有可能出现在某一个根结点的位置上,所以想要判断一个二叉树是不是完全二叉树我们只需要判断当遇到了空结点时,此空结点后还有没有其他的非空结点,若有则不是完全二叉树,没有则是完全二叉树

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
int IsCompleteBTree(BNode* root)
{
	Queue queue;
	QueueInit(&queue);
	if (root == NULL)
	{
		return 1;
	}
	QueuePush(&queue, root);
	while (!QueueEmpty(&queue))
	{
		BNode* top = QueueFront(&queue);
		QueuePop(&queue);

		if (top == -1)
		{
			break;
		}
		if (top->left != NULL)
		{
			QueuePush(&queue, top->left);
		}

		if (top->right != NULL)
		{
			QueuePush(&queue, top->right);
		}
	}
	while (!QueueEmpty(&queue))
	{
		BNode* node = QueueFront(&queue);
		QueuePop(&queue);

		if (node != NULL)
		{
			QueueDestroy(&queue);
			return 0;
		}
	}

	QueueDestroy(&queue);
	return 1;
}


以下几个问题的实现需要用到我们自己写的栈
本文里的代码并不是十分全面,例如使用队列和栈的时候并没有具体代码,只是以前自己写过,所以就偷懒直接用了,嘿嘿

非递归实现二叉树的遍历

在递归创建二叉树时其实我们就用到了栈,但我们使用的是系统栈,通过调用系统栈,压栈出栈的方式一层一层的创建了二叉树,所以非递归实现二叉树的遍历其实也就是模拟了这一过程.
首先我们需要一个栈(在这里就直接调用之前写过的栈了,具体代码会在文末给出),具体实现如下:

前序遍历

前序遍历顺序即:左 根 右
所以我们先将根的左树压入栈中,在每个父母节点的创建过程中也是先将其左孩子压入,当压到叶子结点时开始返回创建右结点,直到左树创建完成后同样方法创建右树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void PreorderLoop(BNode* root)
{
	Stack stack;
	StackInit(&Stack);
	BNode* pnode = root;
	BNode* top = NULL;
	
	while(pnode != NULL || !StackEmpty(&stack))
	{
		while(pnode != NULL)
		{
			printf("%d ",pnode->data);
			StackPush(%stack,pnode);
			pnode = pnode->left;
		}
	
		top = StackTop(&stack);StackPop(&stack);
		pnode = top->right;
	}
}

中序遍历

中序的遍历顺序:左 根 右,不同于前序在将结点压入栈中就打印数据,中序遍历优先打印树中最左的结点.即在一棵子树中先打印他的左子树,而后返回打印根,接下来打印右子树.所以我们每次在发现左叶子结点时进行打印,然后出栈….依次打印根,右树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void InorderLoop(BNode* root)
{
	Stack stack;
	StackInit(&stack);

	BNode* pnode = root;
	BNode* top;

	while (pnode != NULL || !StackEmpty(&stack))
	{
		while (pnode != NULL)
		{
			StackPush(&stack,pnode);
			pnode = pnode->left;
		}

		top = StackTop(&stack);
		printf("%d ", top->data);
		StackPop(&stack);
		pnode = top->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
void PostorderLoop(BNode* root)
{
	Stack stack;
	StackInit(&stack);

	BNode* pnode = root;
	BNode* top;
	BNode* last = NULL;

	while (pnode != NULL || !StackEmpty(&stack))
	{
		while (pnode != NULL)
		{
			StackPush(&stack, pnode);
			pnode = pnode->left;
		}

		top = StackTop(&stack);
		if (top->right == NULL || top->right==last)
		{
			printf("%d ", top->data);
			last = top;
			StackPop(&stack);
		}
		else
		{
			pnode = top->right;
		}
	}
}

递归法创建镜像二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
void Mirror(BNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BNode* t = root->left;
	root->left = root->right;
	root->right = t;

	Mirror(root->left);
	Mirror(root->right);
}

详细代码地址:
https://github.com/seevae/DS/tree/master/BinaryTree