【数据结构】二叉树链式结构的实现及其常见操作

妖狐艹你老母 2023-10-14 20:02 47阅读 0赞

## ![6f0d9d754f1449b18f6ebeb40a8c6698.gif][] ##

**目录**

1.手搓二叉树

2.二叉树的遍历

2.1前序、中序以及后序遍历

2.2二叉树的层序遍历

3.二叉树的常见操作

3.1求二叉树节点数量

3.2求二叉树叶子节点数量

3.3求二叉树第k层节点个数

3.3求二叉树的深度

3.4二叉树查找值为x的节点

4.二叉树的销毁

--------------------

## 1.手搓二叉树 ##

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在我们对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

![76f8b916bc704d22b8623842f4aa8edf.png][]

定义二叉树的节点：

typedef int BTDataType;
    typedef struct BinaryTreeNode
    {
    	struct BinaryTreeNode* left;
    	struct BinaryTreeNode* right;
    	BTDataType data;
    }BTNode;

根据上图的二叉树结构手写二叉树：

BTNode* BuyNode(BTDataType data)
    {
    	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    	assert(node);
    	node->data = data;
    	node->left = node->right = NULL;
    	return node;
    }
    
    BTNode* CreatBinaryTree()
    {
    	BTNode* node1 = BuyNode(1);
    	BTNode* node2 = BuyNode(2);
    	BTNode* node3 = BuyNode(3);
    	BTNode* node4 = BuyNode(4);
    	BTNode* node5 = BuyNode(5);
    	BTNode* node6 = BuyNode(6);
    
    	node1->left = node2;
    	node1->right = node4;
    	node2->left = node3;
    	node4->left = node5;
    	node4->right = node6;
    
    	return node1;
    }

这样我们就写出了一个简单的二叉树。

## 2.二叉树的遍历 ##

### 2.1前序、中序以及后序遍历 ###

学习二叉树结构，最简单的方式就是遍历。所谓**二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。**访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

![58cec1ebb4c34917a453043eefdd21f9.png][]

按照规则，二叉树的遍历有：**前序/中序/后序**的递归结构遍历：

1.  前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2.  中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3.  后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以**N(Node）、L(Left subtree）和R(Right subtree）又可解释为 根、根的左子树和根的右子树**。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

![ed3803658b7b4ce5806b46c17c1fa06b.png][]

对于二叉树的遍历，代码写起来很简单，但是对于初学者来说，要理解起来就有点难了，这里先给出三种遍历的代码，大家可以先看看：

**前序遍历**

void PreOrder(BTNode* root)
    {
    	if (root == NULL)
    	{
    		printf("# ");
    		return;
    	}
    	printf("%d ", root->data);
    	PreOrder(root->left);
    	PreOrder(root->right);
    }

**中序遍历**

void InOrder(BTNode* root)
    {
    	if (root == NULL)
    	{
    		printf("# ");
    		return;
    	}
    	InOrder(root->left);
    	printf("%d ", root->data);
    	InOrder(root->right);
    }

**后序遍历**

void PostOrder(BTNode* root)
    {
    	if (root == NULL)
    	{
    		printf("# ");
    		return;
    	}
    	PostOrder(root->left);
    	PostOrder(root->right);
    	printf("%d ", root->data);
    }

看完代码后，是不是觉得这三种遍历都非常的相似呢?我们在编译器上运行一下三种遍历的代码：

int main()
    {
    	BTNode* root = CreatBinaryTree();
    	PreOrder(root);
    	printf("\n");
    	InOrder(root);
    	printf("\n");
    	PostOrder(root);
    	return 0;
    }

运行结果：

![4e966d792fa844788848dd33d022eda6.png][]

前序遍历的递归展开图：

![983187236b5b4c018a4c1db6d3ac97ac.png][]

中序遍历和后续遍历和这图也差不多。

### 2.2二叉树的层序遍历 ###

二叉树的层序遍历是一种广度优先搜索（BFS）的方法。**它按层级顺序逐层遍历二叉树，即从根节点开始，先遍历第一层节点，然后遍历第二层节点，依次类推，直到遍历完所有层级。**

实现层序遍历的一种常见方法是使用队列。具体思路如下：

> 1.  创建一个空队列，并将根节点入队。
> 2.  循环执行以下步骤，直到队列为空：
> 
>  *  出队一个节点，将其值存储到结果列表中。
>  *  若该节点有左孩子，则将左孩子入队。
>  *  若该节点有右孩子，则将右孩子入队。

这样，当队列为空时，遍历过程就完成了，结果列表中存储着层序遍历的结果。

![e02bec3884904c7aab7bed20ecc125ba.png][]

下面代码的使用了C++STL中的队列来完成，避免了手写队列的麻烦：

void LevelOrder(BTNode* root)
    {
    	assert(root);
    	queue<BTNode*> a;
    	a.push(root);
    	while (!a.empty())
    	{
    		BTNode* front = a.front();
    		a.pop();
    		printf("%d ", front->data);
    		if (front->left)
    		{
    			a.push(front->left);
    		}
    		if (front->right)
    		{
    			a.push(front->right);
    		}
    	}
    }
    
    int main()
    {
    	BTNode* root = CreatBinaryTree();
    	LevelOrder(root);
    	return 0;
    }

输出结果：

![29995935bcc047b181b90518f0838470.png][]

## 3.二叉树的常见操作 ##

### **3.1求二叉树节点数量** ###

**方法一：**

定义一个全局变量count，然后遍历每一个节点，每遍历一个节点，count就自加1

代码：

int count = 0;
    void TreeSize1(BTNode* root)
    {
    	if (root == NULL)
    	{
    		return;
    	}
    	count++;
    	TreeSize1(root->left);
    	TreeSize1(root->right);
    }
    int main()
    {
    	BTNode* root = CreatBinaryTree();
    	count = 0;
    	TreeSize1(root);
    	printf("%d\n", count);
    	return 0;
    }

**方法二：**

int TreeSize2(BTNode* root)
    {
    	if (root == NULL)
    	{
    		return 0;
    	}
    	return TreeSize2(root->left) + TreeSize2(root->right) + 1;
    }
    int main()
    {
    	BTNode* root = CreatBinaryTree();
    	printf("TreeSize2: %d\n", TreeSize2(root));
    	return 0;
    }

首先检查根节点是否为空，如果为空，说明这是一个空树，直接返回0。如果根节点不为空，则递归调用自身来计算左子树和右子树的节点数，然后将左子树节点数、右子树节点数以及根节点本身（1个节点）的数量相加，最后返回结果。

通过这种递归的方式，函数可以计算出二叉树中所有节点的总数。

### **3.2求二叉树叶子节点数量** ###

**具体思路：**

首先检查根节点是否为空，如果为空，说明这是一个空树，直接返回 0。接着，通过**判断根节点的左子树和右子树是否都为空来确定当前节点是否为叶子节点**。如果是叶子节点，返回 1。如果不是叶子节点，递归调用自身来计算左子树和右子树的叶子节点数，并将其相加作为结果返回。

int TreeLeafSize(BTNode* root)
    {
    	if (root == NULL) return 0;
    	if (root->left == NULL && root->right == NULL) return 1;
    	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
    }
    int main()
    {
    	BTNode* root = CreatBinaryTree();
    	printf("TreeLeafSize: %d\n", TreeLeafSize(root));
    	return 0;
    }

### 3.3求二叉树第k层节点个数 ###

**思路：**

首先检查根节点是否为空，如果为空，说明这是一个空树，直接返回0。如果k等于1，说明当前层即为目标层，返回1。如果k大于1，则递归调用自身来计算左子树和右子树中第k-1层节点的数量，并将其相加作为结果返回。

通过这种递归的方式，函数可以计算出二叉树中第k层节点的总数。

int TreeKLevel(BTNode* root, int k)
    {
    	assert(k >= 1);
    	if (root == NULL) return 0;
    	if (k == 1) return 1;
    	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
    }
    int main()
    {
    	BTNode* root = CreatBinaryTree();
    	printf("TreeKLevel: %d\n", TreeKLevel(root, 2));//第2层节点数量
    	printf("TreeKLevel: %d\n", TreeKLevel(root, 3));//第3层节点数量
    	printf("TreeKLevel: %d\n", TreeKLevel(root, 4));//第4层节点数量
    	return 0;
    }

函数的递归展开图：

![1301474ad4e243899a6846122c16a1d5.png][]

### 3.3求二叉树的深度 ###

int TreeDepth(BTNode* root)
    {
    	if (root == NULL) return 0;
    	int l = TreeDepth(root->left); //左子树的深度
    	int r = TreeDepth(root->right); //右子树的深度
    	return (l > r ? l : r) + 1; //返回左右子树深度的较大值加自身的深度1
    }
    int main()
    {
    	BTNode* root = CreatBinaryTree();
    	printf("TreeDepth: %d\n", TreeDepth(root));
    	return 0;
    }

首先检查根节点是否为空，如果为空，说明这是一个空树，直接返回深度0。接着，函数通过递归调用自身来计算左子树和右子树的深度，分别将结果存储在变量l和r中。然后，通过比较l和r的大小，选择较大的值，并将其加1（代表当前节点的深度），作为整棵二叉树的深度。

通过这种递归的方式，函数可以计算出二叉树的深度（高度）。

### 3.4二叉树查找值为x的节点 ###

在二叉树查找值为x的节点时，尽量使用前序遍历，可以提高效率。

BTNode* TreeFind(BTNode* root, BTDataType x)
    {
    	if (root == NULL) return NULL;
    	if (root->data == x) return root;
    	BTNode* ret1 = TreeFind(root->left, x);
    	if (ret1)
    	{
    		return ret1;
    	}
    	BTNode* ret2 = TreeFind(root->right, x);
    	if (ret2)
    	{
    		return ret2;
    	}
    	return NULL;
    }
    
    int main()
    {
    	BTNode* root = CreatBinaryTree();
    	BTNode* ret = TreeFind(root, 3);
    	if (ret)
    	{
    		printf("找到了：%d\n", ret->data);
    	}
    	else
    	{
    		printf("找不到\n");
    	}
    	return 0;
    }

首先检查根节点是否为空，如果为空，说明这是一个空树，直接返回NULL。接着，函数检查当前节点的数据是否等于目标值x，如果等于，说明找到了目标节点，返回指向当前节点的指针。如果不等于，递归调用函数分别在左子树和右子树中查找目标值x，如果返回的指针非空，说明在子树中找到了目标节点，直接返回该指针。如果左右子树都没有找到目标节点，则返回NULL。

通过这种递归的方式，函数可以在二叉树中查找特定值的节点，并返回指向该节点的指针。如果找不到目标值，则返回NULL。

## 4.二叉树的销毁 ##

对于二叉树的销毁，我们不能使用先序遍历，因为如果使用先序遍历，会将二叉树的根节点先销毁掉，这样就无法找到根节点的左子树和右子树了，如果一定要使用先序遍历，那就得先把节点的左子树和右子树先保存下来。但如果使用后序遍历，就可以轻松解决了。

采用后序遍历销毁，按照左孩子，右孩子，根节点的顺序销毁一颗二叉树。

void TreeDestory(BTNode* root)
    {
    	if (root == NULL)
    	{
    		return;
    	}
    	TreeDestory(root->left);
    	TreeDestory(root->right);
    	free(root);
    }
    int main()
    {
    	BTNode* root = CreatBinaryTree();
    	PreOrder(root);
    	TreeDestory(root);
    	root = NULL;
    }

![9a2875ff80ad413493e2858ac44bf21e.gif][]

[6f0d9d754f1449b18f6ebeb40a8c6698.gif]: https://img-blog.csdnimg.cn/6f0d9d754f1449b18f6ebeb40a8c6698.gif
[76f8b916bc704d22b8623842f4aa8edf.png]: https://img-blog.csdnimg.cn/76f8b916bc704d22b8623842f4aa8edf.png
[58cec1ebb4c34917a453043eefdd21f9.png]: https://img-blog.csdnimg.cn/58cec1ebb4c34917a453043eefdd21f9.png
[ed3803658b7b4ce5806b46c17c1fa06b.png]: https://img-blog.csdnimg.cn/ed3803658b7b4ce5806b46c17c1fa06b.png
[4e966d792fa844788848dd33d022eda6.png]: https://img-blog.csdnimg.cn/4e966d792fa844788848dd33d022eda6.png
[983187236b5b4c018a4c1db6d3ac97ac.png]: https://img-blog.csdnimg.cn/983187236b5b4c018a4c1db6d3ac97ac.png
[e02bec3884904c7aab7bed20ecc125ba.png]: https://img-blog.csdnimg.cn/e02bec3884904c7aab7bed20ecc125ba.png
[29995935bcc047b181b90518f0838470.png]: https://img-blog.csdnimg.cn/29995935bcc047b181b90518f0838470.png
[1301474ad4e243899a6846122c16a1d5.png]: https://img-blog.csdnimg.cn/1301474ad4e243899a6846122c16a1d5.png
[9a2875ff80ad413493e2858ac44bf21e.gif]: https://img-blog.csdnimg.cn/9a2875ff80ad413493e2858ac44bf21e.gif