【数据结构】二叉树链式结构

分手后的思念是犯贱 2024-04-26 10:58 77阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏：[初阶数据结构][Link 1]  
> ?️博客主页：[睿睿的博客主页][Link 2]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  一.二叉树的理解：
 *  二.二叉树的遍历：
 *   *  创建二叉树：
     *  1.前序遍历：
     *  2.中序遍历：
     *  3.后序遍历：
     *  4.层序遍历：
 *  三.判断二叉树是否为完全二叉树：
 *  四.二叉树结点数量：
 *   *   *  分治和遍历的区别：
 *  五.二叉树的高度（深度）：
 *  六.二叉树第k层节点个数
 *  总结

## 前言 ##

在之前的二叉树的顺序结构中我们发现，该二叉树对于堆（一种完全二叉树）非常实用，但是对于非完全二叉树就会出现以下的结构，造成空间浪费：  
![在这里插入图片描述][a6f85b7b919149058289a3e3c7741cbb.png]  
  所以这里我们还是要通过链式结构来实现二叉树。但是其实普通二叉树是没有什么意义的，增删查改没有多大的意义。真正有意义的是搜索二叉树：  
![在这里插入图片描述][7b551911732347a1bb1fbacab3ebb150.png]  
  搜索二叉树的特点是左子树比根大/小，右子树比根小/大。这里的二叉树可以用来搜索，也可以用来进行插入，删除等操作，拥有实际的意义。所以对于普通二叉树，我们不用学习他的增删查改，只用学习他的遍历等操作，并且复习一下递归的相关知识。

## 一.二叉树的理解： ##

我们先回顾一下回顾下二叉树的概念，**二叉树**是：

1.  **空树**
2.  **非空**：根节点，根节点的左子树、根节点的右子树组成的。

对于一颗二叉树，我们看到它就要把他分为：**根，左子树，右子树**。对于**左子树**，在把他分为：**根，左子树，右子树**。对于**右子树**，在把他分为：**根，左子树，右子树**……以此类推直到左右子树都为空才停止。  
![在这里插入图片描述][b0e22861f861484d9b0f35a1cfd025a9.png]  
  从概念中可以看出，**二叉树定义是递归式**的，因此**后序基本操作中基本都是按照该概念实现的。**

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

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

按照规则，二叉树的遍历有：**前序/中序/后序**的**递归结构遍历**。我们以这颗二叉树为例：  
![在这里插入图片描述][1244137c0473401f8ac8fe54faa250b0.png]

### 创建二叉树： ###

typedef int BTDataType;
    typedef struct BinaryTreeNode
    {
        
    	BTDataType data;
    	struct BinaryTreeNode* left;
    	struct BinaryTreeNode* right;
    }BTNode;
    
    BTNode* BuyNode(BTDataType x)
    {
        
    	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    	if (node == NULL)
    	{
        
    		perror("malloc::fail");
    		return;
    	}
    
    	node->left = NULL;
    	node->right = NULL;
    	node->data = x;
    
    	return node;
    }
    
    
    BTNode* CreatTree()
    {
        
    	BTNode* node1 = BuyNode(1);
    	BTNode* node2 = BuyNode(2);
    	BTNode* node3 = BuyNode(3);
    	BTNode* node4 = BuyNode(4);
    	BTNode* node5 = BuyNode(5);
    	BTNode* node6 = BuyNode(6);
    	BTNode* node7 = BuyNode(7);
    
    
    	node1->left = node2;
    	node1->right = node4;
    	node2->left = node3;
    	node4->left = node5;
    	node4->right = node6;
    	node3->right = node7;
    
    
    	return node1;
    }

![在这里插入图片描述][1244137c0473401f8ac8fe54faa250b0.png]

### 1.前序遍历： ###

前序遍历的顺序是：**根，左子树，右子树**。

![在这里插入图片描述][1854663bc3c049a8a7439e929e0a9647.png]  
**代码实现：**

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

结果：  
![在这里插入图片描述][b77b3ee0652c40869148c49992c044de.png]  
![在这里插入图片描述][c56fe4ad56e4480db1c8be038d06edae.jpeg]

### 2.中序遍历： ###

中序遍历的顺序是：**左子树，根，右子树**。  
![在这里插入图片描述][1244137c0473401f8ac8fe54faa250b0.png]  
![在这里插入图片描述][265b33b4aff142b1b63979ccb18fa75f.png]  
**代码实现：**

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

结果：  
![在这里插入图片描述][cfc50d1e8b4e4ee89aa7310731effd77.png]

### 3.后序遍历： ###

后序遍历的顺序是：**左子树，右子树，根**。  
![在这里插入图片描述][0e8f661640f3437b847538ca3f342fd5.png]  
**代码实现：**

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

**结果：**  
![在这里插入图片描述][eb05e7c256e74218bf3d70c752d1e9e1.png]  
  其实上面的三种遍历就是通过s三句代码的顺序导致结果的不同，当然他们的递归过程都能用下面这张图来代表：  
![在这里插入图片描述][9e89ed30265b4287afcb1cd3590cad29.png]

### 4.层序遍历： ###

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行**层序遍历**。设二叉树的根节点所在层数为1，层序遍历就是从**所在二叉树的根节点出发**，首先访问**第一层的树根节点**，然后**从左到右访问第2层上的节点**，接着是**第三层的节点**，以此类推，**自上而下**，**自左至右****逐层**访问树的结点的过程就是层序遍历

![在这里插入图片描述][70c4e6ae2cd54d57abead19a8bc472c6.png]  
  那么如何实现层序遍历呢？这里我们就要用到我们之前所学的队列了！  
  在这里，我们将二叉树的根先进队列，然后将其出队列，每出一次，就让其左右子结点进入队列，随后在出一个队列，将其左右子节点加入队列……这样**通过队列的push和pop就能实现层序遍历**

![在这里插入图片描述][5a3f89d8e37145c0a7f203f7b7331213.png]

我们首先将队列的代码导入即可，就可以创建队列了：  
![在这里插入图片描述][7ff4e8aca3d3400db28b12c567bc3975.png]  
**代码实现：**

void LevelOrder(BTNode* root)
    {
        
    	Queue q;
    	QueueInit(&q);
    	if (root)
    	{
        
    		QueuePush(&q, root);
    	}
    	
    	while (!QueueEmpty(&q))
    	{
        
    		BTNode* front= QueueFront(&q);
    		QueuePop(&q);
    		printf("%d ", front->data);
    		if (front->left)
    		{
        
    			QueuePush(&q, front->left);
    		}
    		if (front->right)
    		{
        
    			QueuePush(&q, front->right);
    		}
    	}
    	QueueDestroy(&q);
    }

**注意：**  
  这里我们放入队列的不是要打印的数据，而是树结点的指针，为什么呢？如果我们存入的是要打印的数据（整形数据），那么我们无法找到他们的子节点!所以我们每次pop出一个指针，然后push这个指针（结点）的子节点即可。图解如下：  
![在这里插入图片描述][ad2b710d76f6486d9656b6d94bdbb42e.png]

## 三.判断二叉树是否为完全二叉树： ##

我们先来看看这张图：  
![在这里插入图片描述][911a6b00be9347179e301c8b35ac16cb.png]  
  我们会发现，通过层序遍历的方法，**满二叉树在层序遍历时的非空结点一定是连续的**，**空结点也是连续的**，所以我们只要在层序遍历的基础上把空结点存入，然后判断空结点是否连续即可。

**代码实现：**

// 判断二叉树是否是完全二叉树
    bool TreeComplete(BTNode* root)
    {
        
    	Queue q;
    	QueueInit(&q);
    	if (root)
    		QueuePush(&q, root);
    
    	while (!QueueEmpty(&q))
    	{
        
    		BTNode* front = QueueFront(&q);
    		QueuePop(&q);
    
    		if (front == NULL)
    		{
        
    			break;
    		}
    		else
    		{
        
    			QueuePush(&q, front->left);
    			QueuePush(&q, front->right);
    		}
    	}
    
    	// 判断是不是完全二叉树
    	while (!QueueEmpty(&q))
    	{
        
    		BTNode* front = QueueFront(&q);
    		QueuePop(&q);
    
    		// 后面有非空，说明非空节点不是完全连续
    		if (front)
    		{
        
    			QueueDestroy(&q);
    			return false;
    		}
    	}

## 四.二叉树结点数量： ##

如果我们要计算结点的数量，通过上面所学的**遍历的方式**当然可以计算出结点数量。  
![在这里插入图片描述][8b62bf8791254127b02912d7e52e76ca.png]  
这就是遍历的方法，但是事实上我们用分治的方法更多一些：

#### 分治和遍历的区别： ####

拿学校人口统计作为例子，遍历法与分治法的区别如下：

**遍历法**，做法如下：  
校长自己一个人带着一个本子，跑遍全校查人数

**分治法**，做法如下：  
校长想知道人数，就找来院长统计每个院的人数相加，院长找来系主任统计每个系的人数相加……这样校长就不用亲自动手了。其实递归就是把任务交给打工人（呜呜）。  
![在这里插入图片描述][f298fa7e22664988989b2c46d2dd5ffe.png]  
那么我们如何实现分治法呢？  
总体思路就是 返回：**左子树数量+右子树数量+1**  
代码实现：

int TreeSize(BTNode* root)
    {
        
    	return root == NULL ? 0 : 
    	TreeSize(root->left) 
    	+ TreeSize(root->right) + 1;
    }

## 五.二叉树的高度（深度）： ##

在这里要求二叉树的高度，我们也是用分治的思想：

int TreeHeight(BTNode* root)
    {
        
    	if (root == NULL)
    	{
        
    		return 0;
    	}
    	int leftHeight = TreeHeight(root->left);
    	int rightHeight = TreeHeight(root->right);
    
    	return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

其实对于递归内容，我们只需要考虑：

*  将问题分为子问题，子问题的解决方式和总问题的解决方式的方式一样
 *  有中止的条件

## 六.二叉树第k层节点个数 ##

现在我们把他分为子问题：

**当前树的第k层个数=左子树的第k-1层个数+右子树的第k-1层个数**  
代码如下：

int TreeKLevel(BTNode* root, int k)
    {
        
    	if (root == NULL)
    	{
        
    		return 0;
    	}
    	if (k == 1)
    	{
        
    		return 1;
    	}
    	int leftklevel = TreeKLevel(root->left, k - 1);
    	int rightklevel = TreeKLevel(root->right, k - 1);
    
    	return leftklevel + rightklevel;
    }

## 总结 ##

更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 3]  
> [c语言学习][c]  
> [算法][Link 4]  
> [智力题][Link 5]  
> [初阶数据结构][Link 1]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/ed0d9addf4c541e094bcb216c73a9742.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/83c6abc7a06549c18c124755c5e9d6f1.gif
[a6f85b7b919149058289a3e3c7741cbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/76c3570dba4c4b4fb498207d7126b0b0.png
[7b551911732347a1bb1fbacab3ebb150.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/507402216f674dac96321372979dacd3.png
[b0e22861f861484d9b0f35a1cfd025a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5dcf6c8e8c5647b98debb0a0b34f65d3.png
[1244137c0473401f8ac8fe54faa250b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/6bc71cdee49b4d21aa13a402bc3011d5.png
[1854663bc3c049a8a7439e929e0a9647.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/efbe60e6541948828b74f6487433f3b9.png
[b77b3ee0652c40869148c49992c044de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/4f6295e8836e47cfa65df4b018eeacdf.png
[c56fe4ad56e4480db1c8be038d06edae.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e4050fd3d6e141cda8ff17b35e5dc158.jpeg
[265b33b4aff142b1b63979ccb18fa75f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/c5e49fc596d0457ebf8491321b129995.png
[cfc50d1e8b4e4ee89aa7310731effd77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e65ddbe0821041268d9c3fb72751f9dc.png
[0e8f661640f3437b847538ca3f342fd5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2ddc911344ec41f4b5ca8ac2359968bf.png
[eb05e7c256e74218bf3d70c752d1e9e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/cd74f67657e64e3fa7ed7d1b4570bf7f.png
[9e89ed30265b4287afcb1cd3590cad29.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/b19c763832254bb0b8023a9342934913.png
[70c4e6ae2cd54d57abead19a8bc472c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/99693b06485d4b679b914f7648868071.png
[5a3f89d8e37145c0a7f203f7b7331213.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/1b72221e942a447fb8afc6286b4032be.png
[7ff4e8aca3d3400db28b12c567bc3975.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/3698138e0ded426ba702d2f5de4c51af.png
[ad2b710d76f6486d9656b6d94bdbb42e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/214a432b62f74753b6f92bd3a295462c.png
[911a6b00be9347179e301c8b35ac16cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e5e93b4bb8b041c58b70a83bdf2059b0.png
[8b62bf8791254127b02912d7e52e76ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/efd1729bea4b4884944fedf564bafffd.png
[f298fa7e22664988989b2c46d2dd5ffe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/0424c1c2a6174b63af29375321df5dbc.png
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12166402.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/3bd812404f3644578c19d348780d5f80.gif