二叉树操作

二叉树操作说明

二叉树的常用操作主要包括，二叉树的创建、二叉树的先序遍历、中序遍历和后续遍历等。

二叉树操作

二叉树定义

二叉树的结构如下：

struct BTreeNode
{
	int data;  //队列每个结点的数据 
    struct BTreeNode *pLChild; //左孩子
    struct BTreeNode *pRChild; //右孩子
};

我们定义了一个二叉树结点的结构 BTreeNode，其有三个成员，data 保存了当前结点的数据，pLChild 保存了左孩子结点的指针，pRChild 保存了右孩子结点的指针。

创建

我们创建一个二叉树，如下图所示：

先序遍历

先序遍历的规则就是根结点 —> 左子树 —> 右子树，因此，我们遍历上述二叉树的结果为，首先访问根节点即 A，接着访问左孩子，即结点 B，接着访问结点 C，访问结点 C，再次访问结点 C 的左孩子，即结点 D，最后访问结点 D 的右孩子，即结点 E。

因此，先序遍历的结果为：

A ---> B ---> C ---> D ---> E

中序遍历

中序遍历的规则就是左子树 —> 根结点 —> 右子树，因此，我们遍历上述二叉树的结果为，首先访问根节点 A 的左结点，即结点 B，此时左子树全部访问完毕，我们再次访问根节点 A。

此时，我们继续访问结点 A 的右孩子 C，要访问右孩子 C，首先得访问右孩子的左结点 D，要访问结点 D 首先得访问结点 D 的左孩子，结点 D 没有左孩子，因此，我们访问结点 E，即结点 D 的右孩子，此时结点 D 访问完毕。我们再次访问结点 C 即可完成整个遍历。

因此，中序遍历的结果为：

B ---> A ---> D ---> E ---> C

后序遍历

后序遍历的规则就是左子树 —> 右子树 —> 根结点，因此，我们遍历上述二叉树的结果为，首先访问根节点 A 的左结点，即结点 B，此时左子树全部访问完毕，我们再次访问根节点 A 的右子树。

要根节点 A 的右子树我们首先得访问 A 结点右子树的左子树，即结点 D，那么要访问结点 D，我们同样首先得访问结点 E。

此时，结点 D 的左右子树都访问完毕了，我们直接可以访问结点 D，结点 D 访问完毕，我们就可以访问结点 C，结点 C 访问完毕，我们直接可以访问结点 A 了。

因此，后序遍历的结果为：

B ---> E ---> D ---> C ---> A

二叉树创建

函数原型

struct BTreeNode *CreateBTreeNode(void);  //创建二叉树

返回值

返回创建成功后的二叉树的根节点。

图解

具体实现

struct BTreeNode *CreateBTreeNode(void)
{
	//动态分配五个结点 
	struct BTreeNode *pNodeA = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	struct BTreeNode *pNodeB = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	struct BTreeNode *pNodeC = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	struct BTreeNode *pNodeD = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	struct BTreeNode *pNodeE = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	//设置数据
	pNodeA->data = 'A';
	pNodeB->data = 'B';
	pNodeC->data = 'C';
	pNodeD->data = 'D';
	pNodeE->data = 'E';
	//A结点的左孩子是B结点 
	pNodeA->pLChild = pNodeB;
	//A结点的右孩子是C结点
	pNodeA->pRChild = pNodeC; 
	//B结点的左孩子和右孩子都为空
	pNodeB->pLChild = pNodeB->pRChild = NULL;
	//C结点的左孩子为D结点
	pNodeC->pLChild = pNodeD;
	//C结点的右孩子为空 
	pNodeC->pRChild = NULL;
	//D结点的左孩子为空
	pNodeD->pLChild = NULL;
	//D结点的右孩子为E结点 
	pNodeD->pRChild = pNodeE;
	//E结点的左右孩子都为空 
	pNodeE->pLChild = pNodeE->pRChild = NULL;
	//返回根节点
	return pNodeA;
}

说明

我们只需要设置每个结点的左孩子和右孩子即可。

先序遍历二叉树

函数原型

void PreTraverseBTree(struct BTreeNode *pBTree);

参数

参数	说明
pBTree	需要遍历的二叉树。

返回值

无。

具体实现

//先序遍历 
void PreTraverseBTree(struct BTreeNode *pBTree)
{
	//如果二叉树不为空，则先访问根节点 
	if (pBTree != NULL)
	{
		printf("%c\n", pBTree->data);
		//如果左孩子不为空，则再次递归遍历左孩子 
		if (pBTree->pLChild != NULL)
		{
			PreTraverseBTree(pBTree->pLChild);
		}
		//如果右孩子不为空，则再次递归遍历右孩子
		if (pBTree->pRChild != NULL)
		{
			PreTraverseBTree(pBTree->pRChild);
		}
	}
}

说明

先序遍历就是首先访问根节点，接着递归访问左子树，最后，再次递归访问右子树即可。

中序遍历二叉树

函数原型

void InTraverseBTree(struct BTreeNode *pBTree);

参数

参数	说明
pBTree	需要遍历的二叉树。

返回值

无。

具体实现

//中序遍历 
void InTraverseBTree(struct BTreeNode *pBTree)
{
	if (pBTree != NULL)
	{		
		//如果左孩子不为空，则递归遍历左孩子 
		if (pBTree->pLChild != NULL)
		{
			InTraverseBTree(pBTree->pLChild);
		}
		//访问根节点
		printf("%c\n", pBTree->data);
		//如果右孩子不为空，则再次递归遍历右孩子
		if (pBTree->pRChild != NULL)
		{
			InTraverseBTree(pBTree->pRChild);
		}
	}
}

说明

中序遍历就是首先递归访问左子树，接着访问根节点，最后，再次递归访问右子树即可。

后序遍历二叉树

函数原型

void PostTraverseBTree(struct BTreeNode *pBTree);

参数

参数	说明
pBTree	需要遍历的二叉树。

返回值

无。

具体实现

//后续遍历 
void PostTraverseBTree(struct BTreeNode *pBTree)
{
	if (pBTree != NULL)
	{
		//如果左孩子不为空，则递归遍历左孩子 
		if (pBTree->pLChild != NULL)
		{
			PostTraverseBTree(pBTree->pLChild);
		}
		//如果右孩子不为空，则再次递归遍历右孩子
		if (pBTree->pRChild != NULL)
		{
			PostTraverseBTree(pBTree->pRChild);
		}
		//访问根节点 
		printf("%c\n", pBTree->data);
	}
}

说明

后序遍历就是首先递归访问左子树，接着递归访问右子树，最后，访问根节点即可。

案例

二叉树操作的综合案例如下：

#include <stdio.h>
#include <malloc.h>
struct BTreeNode
{
	int data;  //队列每个结点的数据 
    struct BTreeNode *pLChild; //左孩子
    struct BTreeNode *pRChild; //右孩子
};
//创建二叉树 
struct BTreeNode *CreateBTreeNode(void);
//先序遍历 
void PreTraverseBTree(struct BTreeNode *);
//中序遍历 
void InTraverseBTree(struct BTreeNode *);
//后续遍历 
void PostTraverseBTree(struct BTreeNode *);
int main()
{
	printf("嗨客网（www.haicoder.net）\n\n");
	struct BTreeNode *pTree = CreateBTreeNode();
	printf("先序遍历的结果为：\n");
	PreTraverseBTree(pTree);
	printf("\n中序遍历的结果为：\n");
	InTraverseBTree(pTree);
	printf("\n后序遍历的结果为：\n");
	PostTraverseBTree(pTree);
	return 0;
}
struct BTreeNode *CreateBTreeNode(void)
{
	//动态分配五个结点 
	struct BTreeNode *pNodeA = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	struct BTreeNode *pNodeB = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	struct BTreeNode *pNodeC = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	struct BTreeNode *pNodeD = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	struct BTreeNode *pNodeE = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
	//设置数据
	pNodeA->data = 'A';
	pNodeB->data = 'B';
	pNodeC->data = 'C';
	pNodeD->data = 'D';
	pNodeE->data = 'E';
	//A结点的左孩子是B结点 
	pNodeA->pLChild = pNodeB;
	//A结点的右孩子是C结点
	pNodeA->pRChild = pNodeC; 
	//B结点的左孩子和右孩子都为空
	pNodeB->pLChild = pNodeB->pRChild = NULL;
	//C结点的左孩子为D结点
	pNodeC->pLChild = pNodeD;
	//C结点的右孩子为空 
	pNodeC->pRChild = NULL;
	//D结点的左孩子为空
	pNodeD->pLChild = NULL;
	//D结点的右孩子为E结点 
	pNodeD->pRChild = pNodeE;
	//E结点的左右孩子都为空 
	pNodeE->pLChild = pNodeE->pRChild = NULL;
	//返回根节点
	return pNodeA;
}
//先序遍历 
void PreTraverseBTree(struct BTreeNode *pBTree)
{
	//如果二叉树不为空，则先访问根节点 
	if (pBTree != NULL)
	{
		printf("%c\n", pBTree->data);
		//如果左孩子不为空，则再次递归遍历左孩子 
		if (pBTree->pLChild != NULL)
		{
			PreTraverseBTree(pBTree->pLChild);
		}
		//如果右孩子不为空，则再次递归遍历右孩子
		if (pBTree->pRChild != NULL)
		{
			PreTraverseBTree(pBTree->pRChild);
		}
	}
}
//中序遍历 
void InTraverseBTree(struct BTreeNode *pBTree)
{
	if (pBTree != NULL)
	{		
		//如果左孩子不为空，则递归遍历左孩子 
		if (pBTree->pLChild != NULL)
		{
			InTraverseBTree(pBTree->pLChild);
		}
		//访问根节点
		printf("%c\n", pBTree->data);
		//如果右孩子不为空，则再次递归遍历右孩子
		if (pBTree->pRChild != NULL)
		{
			InTraverseBTree(pBTree->pRChild);
		}
	}
}
//后续遍历 
void PostTraverseBTree(struct BTreeNode *pBTree)
{
	if (pBTree != NULL)
	{
		//如果左孩子不为空，则递归遍历左孩子 
		if (pBTree->pLChild != NULL)
		{
			PostTraverseBTree(pBTree->pLChild);
		}
		//如果右孩子不为空，则再次递归遍历右孩子
		if (pBTree->pRChild != NULL)
		{
			PostTraverseBTree(pBTree->pRChild);
		}
		//访问根节点 
		printf("%c\n", pBTree->data);
	}
} 

程序运行后，输出如下：

我们看到，整个二叉树的操作运行结果如上所示。