二叉树及完全二叉树的前序遍历、中序遍历、后序遍历及层序遍历_前序遍历 中序遍历 后序遍历

---

前言

本期和大家主要分享的数据结构中的树形结构，其中主要包括二叉树（完全二叉树和满二叉树），会介绍二叉树的前序、中序以及后序遍历的实现方法；首先还是从理论入手，进而深入了解树形结构的特点；

---

一、树的特性

1.树形结构是一种一对多的数据结构；
2.节点:组成树形结构的基本数据对象;
3.前驱:每个节点只能有一个前驱;
4.后继:每个节点可以有多个后继;
5.度:后继节点的个数;
6.叶子节点:度数为0的节点;
7.根节点:最顶层的节点;
8.分支节点:度数不为0的节点;
9.层:从根节点(1)出发到该节点的步数(+1),也称为层数;
10.高度:从叶子节点出发到根节点的步数称为高度;
11.节点的高度 == 节点的层数;
12.子树:树形结构中以分支节点作为根节点的树形结构;
13.多个子树连接在一起的树形结构可称为森林;
以上是一些关于树形结构的基本概念，有助于在后续更好的描述树形结构；

二、二叉树

1.二叉树详解

(1)整个树形结构中所有节点的度数不超过2
	度数为0:叶子节点
	度数为1:只有左孩子或者右孩子的节点
	度数为2:既有左孩子又有右孩子

(2)完全二叉树:可以完全展开的一个二叉树
   满二叉树:所有叶子节点都在同一层的完全二叉树

(3)完全二叉树中所有节点都有编号:
   如果一个节点编号为n,那么左孩子编号为:2n,右孩子编号为:2n+1
1
2
3
4
5
6
7
8
9
10

(1)二叉树第k层最多有2^(k-1)个节点
(2)二叉树有k层,最多有2^k -1个节点
(3)前序遍历、中序遍历、后序遍历、层序遍历是二叉树中重要的遍历方法；

2.遍历方式

遍历顺序主要分为以下几种：
这里主要用这个例题来进行演示：

2.1 前序遍历（先序遍历）

遍历顺序：根左右
例题中的前序遍历结果为：1，2，4，8，5，9，3，6，7，10；

2.2 中序遍历

遍历顺序：左根右
例题中的中序遍历结果为：8，4，2，5，9，1，6，3，10，7；

2.3 后序遍历

遍历顺序：左右根
例题中的后序遍历结果为：8，4，9，5，2，6，10，7，3，1；

2.3 层序遍历

遍历顺序：自上而下，自左向右
例题中的后序遍历结果为：1，2，3，4，5，6，7，8，9，10；

---

三、二叉树的实现

先来看一下如何让实现一个简单的二叉树：

3.1 二叉树头文件

这里的数据类型依旧是整型，且定义了树节点结构体，其中包括树节点的编号、存放的数据以及书的左孩子和右孩子；

#ifndef __BTREE_H__
#define __BTREE_H__

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


typedef int DataType;

typedef struct tree_node
{
	int Num;						//树节点编号
	DataType Data;
	struct tree_node *pLeftChild;	//树节点的左孩子
	struct tree_node *pRightChild;	//树节点的右孩子
}TreeNode;

extern TreeNode *CreateTreeNode(int Num);							//创建树节点
extern TreeNode *CreateCompleteBinTree(int StartNum, int EndNum);	//创建完全二叉树
extern int PreOrderBinTree(TreeNode *pTmpNode);						//前序遍历
extern int InOrderBinTree(TreeNode *pTmpNode);						//中序遍历
extern int PostOrderBinTree(TreeNode *pTmpNode);					//后序遍历
extern int DestroyBinTree(TreeNode *pTmpNode);						//销毁二叉树

#endif
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

下面来看一下每个函数的具体实现：
（1）由于在创建二叉树的过程中树节点的创建是一个非常常用的基本操作，因此将其直接封装；其主要流程就是定义指针变量接收树节点的返回地址，对节点进行赋值并且左孩子和右孩子均为空；

#include "btree.h"

/* 创建一个树节点 */
TreeNode *CreateTreeNode(int Num)
{
	TreeNode *pTmpNode = NULL;

	pTmpNode = malloc(sizeof(TreeNode));
	if (NULL == pTmpNode)
	{
		perror("fail to malloc");
		return NULL;
	}

	pTmpNode->Num = Num;
	pTmpNode->pLeftChild = NULL;
	pTmpNode->pRightChild = NULL;

	return pTmpNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（2）本函数的主要作用是使用函数递归调用实现一个完全二叉树；二叉树从StartNum到EndNum，主要的逻辑顺序为：先创建根节点，接下来去创建该节点的左孩子和右孩子，紧接着再去创建左孩子的左孩子和右孩子，以此类推这样递归调用，最终的结束条件是2 * StartNum <= EndNum会将整个二叉树限制到EndNum；

/* 递归调用创建一个完全二叉树 */
TreeNode *CreateCompleteBinTree(int StartNum, int EndNum)
{
	TreeNode *pTmpNode = NULL;

	pTmpNode = CreateTreeNode(StartNum);
	if (2 * StartNum <= EndNum)			//每一层最左侧的节点为上一层最左侧的2倍
	{
		pTmpNode->pLeftChild = CreateCompleteBinTree(2 * StartNum, EndNum);
		//创建左孩子
	}
	if (2 * StartNum + 1 <= EndNum)
	{
		pTmpNode->pRightChild = CreateCompleteBinTree(2 * StartNum + 1, EndNum);
		//创建右孩子
	}

	return pTmpNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（3）二叉树的销毁过程依旧是通过函数递归调用，那个孩子不为空就去追踪它的孩子，到最后一个孩子进行依次销毁，函数递归退出，每退出一次销毁一次，直至销毁至根节点；

/* 销毁二叉树 */
int DestroyBinTree(TreeNode *pTmpNode)
{
	if (pTmpNode->pLeftChild != NULL)
	{
		DestroyBinTree(pTmpNode->pLeftChild);
	}
	if (pTmpNode->pRightChild != NULL)
	{
		DestroyBinTree(pTmpNode->pRightChild);
	}
	free(pTmpNode);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.2 二叉树的遍历

3.2.1 前序遍历

前序遍历的顺序为根左右，这里使用的遍历方式也是函数的递归调用，函数先打印根节点内容，如果左孩子不为空则输出左孩子内容，右孩子不为空则输出右孩子的内容，这样一直进行递归，结束条件为左孩子或者右孩子为空截至，递归函数再一次次退出来；

/* 前序遍历(根左右) */
int PreOrderBinTree(TreeNode *pTmpNode)
{
	printf("%d ", pTmpNode->Num);
	if (pTmpNode->pLeftChild != NULL)
	{
		PreOrderBinTree(pTmpNode->pLeftChild);
	}
	if (pTmpNode->pRightChild != NULL)
	{
		PreOrderBinTree(pTmpNode->pRightChild);
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.2.2 中序遍历

中序遍历的思想和前序遍历的思想是一样的，可以理解为只有根节点的打印顺序发生了变化；

/* 中序遍历(左根右) */
int InOrderBinTree(TreeNode *pTmpNode)
{
	if (pTmpNode->pLeftChild != NULL)
	{
		InOrderBinTree(pTmpNode->pLeftChild);
	}
	printf("%d ", pTmpNode->Num);
	if (pTmpNode->pRightChild != NULL)
	{
		InOrderBinTree(pTmpNode->pRightChild);
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.2.3 后序遍历

后序遍历的思想和前序遍历的思想是一样的，也可以理解为只有根节点的打印顺序发生了变化；

/* 后序遍历(左右根) */
int PostOrderBinTree(TreeNode *pTmpNode)
{
	if (pTmpNode->pLeftChild != NULL)
	{
		PostOrderBinTree(pTmpNode->pLeftChild);
	}
	if (pTmpNode->pRightChild != NULL)
	{
		PostOrderBinTree(pTmpNode->pRightChild);
	}
	printf("%d ", pTmpNode->Num);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.2.4 层序遍历

由于层序遍历是使用队列实现的，所以这里给出队列的数据结构如下：

typedef TreeNode *DataType;

typedef struct node 
{
	DataType Data;
	struct node *pNext;
}LinkNode;

typedef struct queue
{
	LinkNode *pHead;
	LinkNode *pTail;
	int cLen;
	int tLen;
}LinkQueue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

数据结构这里的算法可能刚开始理解是有一点难度的，希望小伙伴们多思考，一般两三遍下来理解是没有问题的;

/* 层序遍历 */
int SeqOrderBinTree(TreeNode *pRoot)
{
	int Num = 0;
	int MaxLen = 1;			//不能从0开始
	int i = 0;
	LinkQueue *pTmpQueue = NULL;
	DataType TmpData;

	Num = GetBinHeight(pRoot);
	for (i = 0; i < Num; ++i)
	{
		MaxLen *= 2;
	}
	MaxLen -= 1;

	pTmpQueue = CreateLinkQueue(MaxLen);
	EnterLinkQueue(pTmpQueue, pRoot);

	while (!IsEmptyLinkQueue(pTmpQueue))
	{
		TmpData = QuitLinkQueue(pTmpQueue);
		if ((DataType)-1 == TmpData)
		{
			break;
		}
		printf("%d ", TmpData->Num);
		if (TmpData->pLeftChild != NULL)
		{
			EnterLinkQueue(pTmpQueue, TmpData->pLeftChild);
		}
		if (TmpData->pRightChild != NULL)
		{
			EnterLinkQueue(pTmpQueue, TmpData->pRightChild);
		}
	}

	DestroyLinkQueue(&pTmpQueue);
}
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

四、结果

这里给出一个完全二叉树的程序运行结果图（完全二叉树是从1-5）：

非递归的方法比较复杂，我们留到下期分享；

总结

本期主要分享的是树形结构的基本概念，树型结构中完全二叉树的创建以及二叉树的一些基本操作，其中主要包括了二叉树的创建，销毁以及二叉树的前序遍历中序遍历及后序遍历，主要用到的思想的函数递归思想，希望小伙伴们一定要注意基础知识的重要性，不能急于求成；加油小伙伴们！
最后，各位小伙伴们如果喜欢我的分享可以点赞收藏哦，你们的认可是我创作的动力，一起加油！