数据结构 | 第六章树

古城微笑少年丶 2022-10-18 10:00 159阅读 0赞

### 文章目录 ###

*   *   *  一、树
         *   *  1、树的基本概念
             *   *  1.1 树的定义
                 *  1.2 结构特点
                 *  1.3 常见术语
             *  2、树的表示法
             *   *  2.1 图形表示法
                 *  2.2 广义表示法
                 *  2.3 左孩子右兄弟表示法
         *  二、二叉树
         *   *  1、基本概念
             *   *  1.1 定义
                 *  1.2 基本特征
                 *  1.3 各个形态
                 *  1.4 二叉树性质
             *  2、顺序存储
             *  3、链式存储
         *  三、遍历二叉树
         *   *  1、基本概念
             *   *  1.1 代码实现
             *  2、二叉树的其他操作
             *   *  2.1 深度的计算
                 *  2.2 计算高度
                 *  2.3 二叉树的复制
                 *  2.4 二叉树遍历
             *  4、树和森林与二叉树的转换
             *   *  4.1 树的存储结构
                 *  4.2 树和森林转换为二叉树
                 *  4.3 森林转换为二叉树
                 *  4.4 二叉树还原树
                 *  4.5 二叉树还原森林
             *  5、哈夫曼树【最优树】
             *   *  5.1 基本概念
                 *  5.2 构造方法
                 *  5.3 哈夫曼编码
                 *   *  代码演示

### 一、树 ###

#### 1、树的基本概念 ####

##### 1.1 树的定义 #####

> 出一个或多个(n≥0)结点组成的有限集合`T` ,有且仅有一个结点称为根(`root`)，当n>1  
> 时，其余的结点分为m(`m>=0`)个互不相交的有限集合`T1,T2，... Tm`。每个集合本身  
> 又是棵`树`，被称作这个`根的子树`。

##### 1.2 结构特点 #####

>  *  非线性结构， 有`一个`直接`前驱`，但可能有`多个`直接`后继`；
>  *  树的定义具有`递归性`，树中还有树；
>  *  树可以`为空`，即`节点`个数为`0`。

##### 1.3 常见术语 #####

>  *  根：结点，没有前驱；
>  *  叶子：终端结点，没有后继；
>  *  森林：指删除根后的所有的子树的集合；
>  *  有序树：从左往右不能互换，左为第一；
>  *  无序树：子树各结点可互换；
>  *  双亲：直接前驱`parent`；
>  *  孩子：直接后继`child`；
>  *  兄弟：同一双亲下的同层结点`sibling`；
>  *  堂兄弟：不为同一个双亲，但双亲位于同一个结点`cousin`；
>  *  祖先：根结点；
>  *  子孙：即该下层子树中的任意结点；
>  *  结点：树的数据元素；
>  *  结点的度：结点挂接的子树数(`度等于直接后继个数`)；
>  *  结点的层次：从根到该结点的层数(`根我第一层`)；
>  *  终端结点：度为0的结点(`叶子`)；
>  *  分支结点：除树根以外的结点(`内部结点`)；
>  *  树的度：所有结点度中的最大值；
>  *  树的深度：所有结点中最大的层数；

#### 2、树的表示法 ####

##### 2.1 图形表示法 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70]

##### 2.2 广义表示法 #####

> 使用括号进行嵌套：
> 
>  *  `A(B(E),C(F(I,G)))`

##### 2.3 左孩子右兄弟表示法 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 1]

> 转变成左孩子右兄弟=>

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 2]

### 二、二叉树 ###

#### 1、基本概念 ####

##### 1.1 定义 #####

> n `( n≥0 )`个结点的`有限`集合，由一个根结点以及`两棵`互不相交的、分别称为左子树和  
> 右子树的二叉树组成。

##### 1.2 基本特征 #####

>  *  每个结点最多`俩颗树`；
>  *  左孩子和右子树次序不能颠倒的`有序树`。

##### 1.3 各个形态 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 3]

>  *  `(a)`：左、右子树非空；
>  *  `(b)`：右子树为空；
>  *  `(c)`：左子树非空；
>  *  `(d)`：只有一个根结点；
>  *  `(e)`：空二叉树。

##### 1.4 二叉树性质 #####

>  *  在二叉树的第i层(深度)上至多右`2^i-1`个结点；
>  *  对任意二叉树T，若叶子结点数为`n0`，度为2的节点数为`n2`，则有`n0=n2+1`；

>  *  满二叉树：`每一层`的结点都是`满`的；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 4]

>  *  完全二叉树：除了最后一层`其他都是满`的；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 5]

>  *  具有n个结点的完全二叉树的深度为

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

>  *  若一颗有n个结点的完全二叉树的结点，每层从左往右：
>     
>      *  若`i=1`，结点i是根结点，无双亲，若`i>1`，则其双亲结点是结点`i/2`；
>      *  若`2i>n`，则结点i无左孩子，该结点为叶子结点；否则其左孩子是结点`2i`；
>      *  若`2i+1>n`，则结点i无右孩子，该结点为叶子结点；否则其右孩子是结点`2i+1`；

#### 2、顺序存储 ####

> 将根结点编为1，在一次`从上往下`，`从左往右`依次编号。若该结点不存在，则该编号跳过。
> 
>  *  若为左孩子，则编号为`2i`；
>  *  若为右孩子，则编号为`2i+1`；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 6]

> 由此可见，该存储结构会造成大量的`空间浪费`。

#### 3、链式存储 ####

> 该链表的结点分为三个域：
> 
>  *  左指针域；
>  *  数据域；
>  *  右指针域；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 7]

> 该结构便于`查找左右结点，以及查找双亲结点`【可以在以上的基础上添加一个双亲指针域】，缺点在于会增加`存储空间`的开销。

### 三、遍历二叉树 ###

#### 1、基本概念 ####

> 按某种`顺序`访问二叉树中的`所有结点`【不重复】，使得遍历的结点成了序列之间有`一对一`的关系。
> 
>  *  用途：是插入、删除、修改、排序的前提，是二叉树一切运算的基础和核心。

>  *  二叉树中，只需遍历`根节点(D)`、`左子树(L)`、`右子树(R)`即可遍历一颗二叉树。
>  *  遍历方法：`(DLR)、(LDR)、(LRD)、(DRL)、(RDL)、(RLD)`。
>  *  若限定先左后右：`DLR`、`KDR`、`LRD`。
>     
>      *  `DLR`：先序遍历，先根再左再右；
>      *  `LDR`：中序遍历，先左再根再右；
>      *  `LRD`：后序遍历，先左再右再根；

>  *  **注意：**【`先、中、后`】意思是访问结点D是先于子树还是后于子树。对于递归来看三种算法是相同的，或者说三种遍历的访问路径相同，只是访问结点时机不同。

> 例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 8]

>  *  先序遍历：`ABCDEFGH`；
>  *  中序遍历：`BDCEAFHG`；
>  *  后序遍历：`DECBHGFA`。  
>     使用方法：先看成一个整体的树，在按顺序一直衍生，直到该树衍生不下去，在切换。

##### 1.1 代码实现 #####

#include<stdio.h>
    #include<stdlib.h>
    
    
    typedef struct treeNode
    { 
    	char data;
    	struct treeNode* lchild;
    	struct treeNode* rchild;
    }TreeNode;
    
    // 先根再左再右
    void DLR(TreeNode *root)
    { 
    	if (root == NULL)
    	{ 
    		return;
    	}
    
    	printf("%2c", root->data);
    	DLR(root->lchild);
    	DLR(root->rchild);
    }
    
    // 先左再根再右
    void LDR(TreeNode* root)
    { 
    	if (root == NULL)
    	{ 
    		return;
    	}
    
    	LDR(root->lchild);
    	printf("%2c", root->data);
    	LDR(root->rchild);
    }
    
    // 先左再右再根
    void LRD(TreeNode* root)
    { 
    	if (root == NULL)
    	{ 
    		return;
    	}
    
    	LRD(root->lchild);
    	LRD(root->rchild);
    	printf("%2c", root->data);
    }
    
    
    int main()
    { 
    	// 创建各个结点
    	TreeNode nodeA = {  'A', NULL, NULL };
    	TreeNode nodeB = {  'B', NULL, NULL };
    	TreeNode nodeC = {  'C', NULL, NULL };
    	TreeNode nodeD = {  'D', NULL, NULL };
    	TreeNode nodeE = {  'E', NULL, NULL };
    	TreeNode nodeF = {  'F', NULL, NULL };
    	TreeNode nodeG = {  'G', NULL, NULL };
    	TreeNode nodeH = {  'H', NULL, NULL };
    
    	// 将各个结点指向
    	nodeA.lchild = &nodeB;
    	nodeA.rchild = &nodeF;
    	nodeB.rchild = &nodeC;
    	nodeC.lchild = &nodeD;
    	nodeC.rchild = &nodeE;
    	nodeF.rchild = &nodeG;
    	nodeG.lchild = &nodeH;
    
    	printf("\nDLR\n");
    	DLR(&nodeA);
    	printf("\nLDR\n");
    	LDR(&nodeA);
    	printf("\nLRD\n");
    	LRD(&nodeA);
    
    	return 0;
    }

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

#### 2、二叉树的其他操作 ####

##### 2.1 深度的计算 #####

/* * 二叉树求叶子结点数 */
    #include<stdio.h>
    
    int num=0;
    
    void get_LeafNum(TreeNode *root)
    { 
    
    	if (root == NULL)
    		return;
    
    	if (root->rchild == NULL && root->lchild == NULL)// 当该结点的左右子树都为空时为叶子结点
    		num++;
    
    	get_LeafNum(root->lchild);
    	get_LeafNum(root->rchild);
    }
    
    int main()
    { 
    	TreeNode nodeA = {  'A', NULL, NULL };
    	TreeNode nodeB = {  'B', NULL, NULL };
    	TreeNode nodeC = {  'C', NULL, NULL };
    	TreeNode nodeD = {  'D', NULL, NULL };
    	TreeNode nodeE = {  'E', NULL, NULL };
    	TreeNode nodeF = {  'F', NULL, NULL };
    	TreeNode nodeG = {  'G', NULL, NULL };
    	TreeNode nodeH = {  'H', NULL, NULL };
    
    	nodeA.lchild = &nodeB;
    	nodeA.rchild = &nodeF;
    	nodeB.rchild = &nodeC;
    	nodeC.lchild = &nodeD;
    	nodeC.rchild = &nodeE;
    	nodeF.rchild = &nodeG;
    	nodeG.lchild = &nodeH;
    	
    	get_LeafNum(&nodeA);
    	printf("叶子结点数：%d", num);
    
    	return 0;
    }

##### 2.2 计算高度 #####

#include<stdio.h>
    
    int get_High(TreeNode *root)
    { 
    	if (root == NULL)
    	{ 
    		return NULL;
    	}
    	int l = get_High(root->lchild);	
    	int r = get_High(root->rchild);
    
    	int h = l > r ? l + 1: r + 1;// 递归到最后一个结点再往回计算
    
    	return h;
    }
    
    int main()
    { 
    	TreeNode nodeA = {  'A', NULL, NULL };
    	TreeNode nodeB = {  'B', NULL, NULL };
    	TreeNode nodeC = {  'C', NULL, NULL };
    	TreeNode nodeD = {  'D', NULL, NULL };
    	TreeNode nodeE = {  'E', NULL, NULL };
    	TreeNode nodeF = {  'F', NULL, NULL };
    	TreeNode nodeG = {  'G', NULL, NULL };
    	TreeNode nodeH = {  'H', NULL, NULL };
    
    	nodeA.lchild = &nodeB;
    	nodeA.rchild = &nodeF;
    	nodeB.rchild = &nodeC;
    	nodeC.lchild = &nodeD;
    	nodeC.rchild = &nodeE;
    	nodeF.rchild = &nodeG;
    	nodeG.lchild = &nodeH;
    
    	int h = get_High(&nodeA);
    	printf("深度：%d\n", h);
    	return 0;
    }

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

##### 2.3 二叉树的复制 #####

/* * 遍历二叉树：先根再左再右 */
    void DLR(TreeNode *root)
    { 
    	if (root == NULL)
    	{ 
    		return;
    	}
    
    	printf("%2c", root->data);
    	DLR(root->lchild);
    	DLR(root->rchild);
    }
    
    
    /* * 二叉树的复制 */
    TreeNode* copyTree(TreeNode* root)
    { 
    	if (NULL == root)
    		return NULL;
    
    	TreeNode* lrchid = copyTree(root->lchild);
    	TreeNode* rchild = copyTree(root->rchild);
    
    	TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode*)*10);
    	newNode->lchild = lrchid;
    	newNode->rchild = rchild;
    	newNode->data = root->data;
    
    	return newNode;
    }
    
    
    int main()
    { 
    	TreeNode nodeA = {  'A', NULL, NULL };
    	TreeNode nodeB = {  'B', NULL, NULL };
    	TreeNode nodeC = {  'C', NULL, NULL };
    	TreeNode nodeD = {  'D', NULL, NULL };
    	TreeNode nodeE = {  'E', NULL, NULL };
    	TreeNode nodeF = {  'F', NULL, NULL };
    	TreeNode nodeG = {  'G', NULL, NULL };
    	TreeNode nodeH = {  'H', NULL, NULL };
    
    	nodeA.lchild = &nodeB;
    	nodeA.rchild = &nodeF;
    	nodeB.rchild = &nodeC;
    	nodeC.lchild = &nodeD;
    	nodeC.rchild = &nodeE;
    	nodeF.rchild = &nodeG;
    	nodeG.lchild = &nodeH;
    
    	TreeNode *root =  copyTree(&nodeA);
    	printf("复制前：\n");
    	DLR(&nodeA);
    	printf("\n复制后：\n");
    	DLR(root);
    	return 0;
    }

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

##### 2.4 二叉树遍历 #####

> 若不适用`递归`遍历二叉树，则需要借助`栈`。

**`main.c`**

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include "stackList.h"
    #include "treeNode.h"
    
    int main()
    { 
    	TreeNode node = Create_Tree();	// 创建树
    
    	ForeachTree(&node);	// 将树排序
    	return 0;
    }

**stackList.c**

#include "stackList.h"
    
    /* 功能：初始化栈 */
    SeqStack* Init_SeqStack()
    { 
    	SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack*)*MAXLEN);
    
    	if (stack == NULL)
    		return NULL;
    
    	memset(stack, 0, sizeof(SeqStack*)*MAXLEN);
    	stack->size = -1;
    
    	return stack;
    }
    
    /* 功能：判断栈空 返回值： · NULL：该栈不存在； · 0：为空栈； · 1：不为空。 */
    int Judge_SeqStackNull(SeqStack* Stack)
    { 
    	if (Stack == NULL)
    		return NULL;
    
    	if (Stack->size == -1)
    		return 0;
    
    	return 1;
    }
    /* 功能：判断栈满 返回值： · NULL：该栈不存在； · 0：为满栈； · 1：栈不为满栈。 */
    int Judge_SeqStackFull(SeqStack* Stack)
    { 
    	if (Stack == NULL)
    		return NULL;
    
    	if (Stack->size == MAXLEN - 1)
    		return 1;
    
    	return 0;
    }
    
    /* 功能：进栈 */
    void Push_SeqStack(SeqStack* Stack, void* data)
    { 
    	if (Judge_SeqStackFull(Stack))
    	{ 
    		printf("满栈，不能进栈！");
    		return;
    	}
    	Stack->size++;
    	Stack->data[Stack->size] = data;
    
    }
    
    /* 功能：出栈 */
    void Pop_SeqStack(SeqStack* Stack)
    { 
    	if (Stack == NULL)
    		return;
    
    	if (!Judge_SeqStackNull(Stack))
    	{ 
    		printf("空栈，不能出栈！");
    		return;
    	}
    
    	Stack->data[Stack->size] = NULL;
    	Stack->size--;
    }
    
    /* 功能：去栈顶 */
    void* Get_SeqStack(SeqStack* Stack)
    { 
    
    	if (Stack == NULL)
    		return NULL;
    
    	if (Stack->size == -1)
    		return NULL;
    
    	void* x = Stack->data[Stack->size];
    	
    	return x;
    }
    
    /* 功能：显示函数 */
    void Display(SeqStack* Stack)
    { 
    	int i;
    	for (i = 0; i < Stack->size+1; i++)
    	{ 
    		printf("%5d", *(int *)Stack->data[i]);
    	}
    
    	printf("\n");
    }
    
    /* 功能：释放空间 */
    void Destroy_SeqStack(SeqStack *Stack)
    { 
    	if (Stack != NULL)
    	{ 
    		free(Stack);
    	}
    }

**treeForeach.c**

#include "stackList.h"
    #include "treeNode.h"
    
    
    /* * 创建树 */
    TreeNode Create_Tree()
    { 
    	TreeNode nodeA = {  'A', NULL, NULL };
    	TreeNode nodeB = {  'B', NULL, NULL };
    	TreeNode nodeC = {  'C', NULL, NULL };
    	TreeNode nodeD = {  'D', NULL, NULL };
    	TreeNode nodeE = {  'E', NULL, NULL };
    	TreeNode nodeF = {  'F', NULL, NULL };
    	TreeNode nodeG = {  'G', NULL, NULL };
    	TreeNode nodeH = {  'H', NULL, NULL };
    
    	nodeA.lchild = &nodeB;
    	nodeA.rchild = &nodeF;
    	nodeB.rchild = &nodeC;
    	nodeC.lchild = &nodeD;
    	nodeC.rchild = &nodeE;
    	nodeF.rchild = &nodeG;
    	nodeG.lchild = &nodeH;
    
    	return nodeA;
    }
    
    /* * 创建新结点，赋标志 */
    Info* Create_Info(TreeNode* root, bool flag)
    { 
    	Info* info = (Info*)malloc(sizeof(Info*) * 10);
    	info->flag = flag;
    	info->node = root;
    
    	return info;
    }
    
    
    /* * 遍历排序二叉树 */
    void ForeachTree(TreeNode* root)
    { 
    	SeqStack* stack = Init_SeqStack();// 初始化栈
    	Push_SeqStack(stack, Create_Info(root, false));// 入栈
    
    	while (stack->size >= 0)
    	{ 
    
    		Info* info = (Info*)Get_SeqStack(stack);// 获取栈顶元素
    		Pop_SeqStack(stack);// 出栈
    
    		if (info->flag)// 判断标志，true则打印，flase则继续执行
    		{ 
    			printf("%3c", info->node->data);
    			free(info); // 当打印后，后续就不需要用到此结点，所以将其释放
    			continue; // 后续不再有其他结点，则直接跳回循环
    		}
    		// 右结点入栈
    		if (info->node->rchild != NULL)
    		{ 
    			Push_SeqStack(stack, Create_Info(info->node->rchild, false));
    		}
    
    		// 左结点入栈
    		if (info->node->lchild != NULL)
    		{ 
    			Push_SeqStack(stack, Create_Info(info->node->lchild, false));
    		}
    
    		// 根节点入栈
    		info->flag = true;
    		Push_SeqStack(stack, info);
    	}
    }
    
    /* * 先根再左再右 * 由于栈的先进后出则进栈顺序与正常的二叉树排序相反 */
    void DLR(SeqStack* stack, Info* info)
    { 
    	// 右结点入栈
    	if (info->node->rchild != NULL)
    	{ 
    		Push_SeqStack(stack, Create_Info(info->node->rchild, false));
    	}
    
    	// 左结点入栈
    	if (info->node->lchild != NULL)
    	{ 
    		Push_SeqStack(stack, Create_Info(info->node->lchild, false));
    	}
    
    	// 根节点入栈
    	info->flag = true;
    	Push_SeqStack(stack, info);
    }
    
    /* * 先左再根再右 */
    void LDR(SeqStack* stack, Info* info)
    { 
    	// 右结点入栈
    	if (info->node->rchild != NULL)
    	{ 
    		Push_SeqStack(stack, Create_Info(info->node->rchild, false));
    	}
    
    	// 根节点入栈
    	info->flag = true;
    	Push_SeqStack(stack, info);
    
    	// 左结点入栈
    	if (info->node->lchild != NULL)
    	{ 
    		Push_SeqStack(stack, Create_Info(info->node->lchild, false));
    	}
    
    
    }
    
    /* * 先左再右在根 */
    void LRD(SeqStack* stack, Info* info)
    { 
    	// 根节点入栈
    	info->flag = true;
    	Push_SeqStack(stack, info);
    
    	// 右结点入栈
    	if (info->node->rchild != NULL)
    	{ 
    		Push_SeqStack(stack, Create_Info(info->node->rchild, false));
    	}
    
    	// 左结点入栈
    	if (info->node->lchild != NULL)
    	{ 
    		Push_SeqStack(stack, Create_Info(info->node->lchild, false));
    	}
    }

**stackList.h**

#pragma once
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #ifdef __cplusplus
    extern "C" { 
    #endif 
    
    #define MAXLEN 1024
    
    	typedef struct SeqStack
    	{ 
    		void* data[MAXLEN];	// 存储数据
    		int size;		// 存储数据个数
    	}SeqStack;
    	// 初始化栈
    	SeqStack* Init_SeqStack();
    	// 判断栈空
    	int Judge_SeqStackNull(SeqStack*);
    	// 判断栈满
    	int Judge_SeqStackFull(SeqStack*);
    	// 进栈
    	void Push_SeqStack(SeqStack*, void*);
    	// 出栈
    	void Pop_SeqStack(SeqStack*);
    	// 取栈顶
    	void* Get_SeqStack(SeqStack*);
    	// 打印栈
    	void Display(SeqStack*);
    	// 销毁释放内存
    	void Destroy_SeqStack(SeqStack*);
    #ifdef __cplusplus
    }
    #endif

**treeNode.h**

#pragma once
    
    #include<stdio.h>
    #include<stdlib.h>
    #include "stackList.h"
    
    // 树的结点
    typedef struct treeNode
    { 
    	char data;
    	struct treeNode* lchild;
    	struct treeNode* rchild;
    }TreeNode;
    
    // 将树拓展，给每个结点赋标记
    typedef struct
    { 
    	TreeNode* node;
    	bool flag;
    }Info;
    
    #ifdef __cplusplus
    extern "C" { 
    #endif 
    
    	// 创建树
    	TreeNode Create_Tree();
    
    	// 创建新结点，赋标志
    	Info* Create_Info(TreeNode*, bool);
    
    	// 遍历排序二叉树
    	void ForeachTree(TreeNode*);
    
    	// 先根再左再右 
    	void DLR(SeqStack*, TreeNode*);
    
    	// 先左再根再右
    	void LDR(SeqStack*, TreeNode*);
    
    	// 先左再右在根
    	void LRD(SeqStack*, TreeNode*);
    
    #ifdef __cplusplus
    }
    #endif

#### 4、树和森林与二叉树的转换 ####

##### 4.1 树的存储结构 #####

**双亲表示法**

> 使用结构体数组：
> 
>  *  数据域用来`保存数据`；
>  *  结点存储`双亲`的数组`下标`。

> **优缺点**：查找`双亲和祖先`容易，但查找`孩子结点或兄弟结点`较为繁琐。

**孩子链表示法**

> 将每个结点的孩子结点构成一个单链表；
> 
>  *  顺序表：存储该结点的`数据值`以及该结点`第一个`孩子的`地址`；
>  *  孩子结点：存放该孩子结点再顺序表的`位置`以及存放`下一个`孩子的`地址`。

> **优缺点**：找到某个`孩子结点容易`，找结点的`双亲困难`。

**孩子兄弟法**

> 是一种二叉链表。
> 
>  *  数据域：存放结点的`数据`；
>  *  指针1：指向`最左边`的第一个孩子；
>  *  指针2：指向`下一个兄弟`结点。

##### 4.2 树和森林转换为二叉树 #####

> 在实际应用中，一般先将树结构转换为二叉树，再以二叉树的方式存储。

**树转换成二叉树**

> **加线**：树种`所有相邻的兄弟`都连上线；

> **抹线**：对树中的每个结点，只保留它与`左边第一个孩子结点`之间的连线，删除它与其他孩子结点之间的连线；

> **旋转**：以树的根结点为轴心，将整棵树`顺`时针旋转`45°`。

> 例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 9]

> 加线

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 10]

> 抹线

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 11]

##### 4.3 森林转换为二叉树 #####

> 当用树转化成的二叉树的根节点没有右子树。

> 方法：
> 
>  *  将森林中的每一棵树转换成相应的二叉树；
>  *  第一颗二叉树保持不动，从第二课二叉树开始，依次把后一颗二叉树作为前一棵二叉树根节点的右子树，直到把最后一棵二叉树作为前一棵二叉树的右子树为止。

> 例：该图为森林

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 12]

> 相邻兄弟相连

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 13]

> 删除与双亲结点的连线

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 14]

> 每棵树转换成二叉树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 15]

> 所有二叉树转化成一棵树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 16]

##### 4.4 二叉树还原树 #####

> 若该二叉树能还原成一棵树，则该二叉树一定满足：
> 
>  *  根节点无`右子树`。

> 二叉树还原过程：
> 
>  *  **加线**：若某结点的左孩子有右子树，在该结点和其左孩子的右子树的右分支上个结点之间加线；
>  *  **抹线**：抹掉各结点的右子树的右分支与上面结点的连线；
>  *  **旋转**：将树旋转。

> 例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 17]

> 连线

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 18]

> 加连线

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 19]

> 删除与右孩子的连线

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 20]

> 还原树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 21]

##### 4.5 二叉树还原森林 #####

> 二叉树的还原方法，即将上面的方法还原回来即可。

#### 5、哈夫曼树【最优树】 ####

##### 5.1 基本概念 #####

>  *  是一种`特殊`的二叉树，树的所有的叶子结点都是有`权值`，从而构造出带`权值`路径`长度最短`的二叉树。  
>     **路径**：树种一个`结点`与`另一个结点`之间的分支构成这俩个结点之间的路径。【注】：兄弟结点之间无路径；  
>     **路径长度**：树中路径上的`分支数目`；  
>     **树的路径长度**：根结点到树种每个结点的`路径长度之和`；  
>     **叶子结点的权值**：`人为`给每个叶子结点`赋值`；  
>     **叶子结点的带权路径长度**：从树`根`到该叶子`结点`之间的路径`长度`与该结点的`权值`的`乘积`；  
>     **树的带权路径长度**：树种所`有叶子`结点的`权值`乘以该结点的`路径长度之和`。【`WPL=k=1Σ到n*Wk*Lk`】  
>     `Wk`：第k个的叶子结点取值；  
>     `Lk`：从根到第k个叶子结点的路径长度。

##### 5.2 构造方法 #####

>  *  权值为一个列表，取出最小的，生成新的权值要添入。
>  *  从前往后选择小的。

> 例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 22]

##### 5.3 哈夫曼编码 #####

> 用于构造使电文的`编码总长最短`的编码方案。
> 
>  *  左为0，右为1，
>  *  编码从上往下。

> 例如：上图中4的结点编码为：`100`。

###### 代码演示 ######

**`main.c`**

#define _CRT_SECURE_NO_WARNINGS；
    #include<stdio.h>
    #include<stdlib.h>
    #include"HuffmanTree.h"
    
    
    int main()
    { 
    	HT HT;
    	int n;
    	printf("\n请输入共有多少个权值：");
    	scanf("%d", &n);
    	CreatHFMT(HT, n);
    	ShowHFMT(HT, n);
    	Get_HFMTnode(HT, n);
    	return 0;
    }

**HuffmanTree.c**

#include"HuffmanTree.h"
    
    // 初始化
    void Init_HFMT(HT T, int n)
    { 
    	int i;
    
    	for (i = 0; i < 2 * n - 1; i++)
    	{ 
    		T[i].weight = 0;
    		T[i].lchild = -1;
    		T[i].rchild = -1;
    		T[i].parent = -1;
    	}
    }
    
    // 输入权值
    void InputWight(HT T, int n)
    { 
    	int w, i;
    	for (i = 0; i < n; i++)
    	{ 
    		printf("请输入第%d个权值：", i + 1);
    		scanf("%d", &w);
    		getchar();
    		T[i].weight = w;
    	}
    }
    
    // 选择最小结点
    void SelectMin(HT T, int i, int *p1, int *p2)
    { 
    	long min1 = 888888, min2 = 888888;
    	int j;
    	for (j = 0; j <= i; j++)
    	{ 
    		if (T[j].parent == -1)
    		{ 
    			if (min1 > T[j].weight && j!=*p1)
    			{ 
    				min2 = T[j].weight;
    				*p2 = j;
    			}
    		}
    	}
    }
    
    // 创建哈夫曼树
    void CreatHFMT(HT T, int n)
    { 
    	int i, p1, p2;
    
    	Init_HFMT(T, n);
    	InputWight(T, n);
    	for (i = n; i < 2 * n - 1; i++)
    	{ 
    		SelectMin(T, i - 1, &p1, &p2);
    		T[p1].parent = T[p2].parent = i;
    		T[i].lchild = T[p1].weight;
    		T[i].rchild = T[p2].weight;
    		T[i].weight = T[p1].weight + T[p2].weight;
    	}
    }
    
    // 输出向量状态表
    void ShowHFMT(HT T, int n)
    { 
    	int i;
    	printf("\n哈夫曼树的各边显示：");
    	for (i = 0; i < 2 * n - 1; i++)
    		while (T[i].lchild != -1)
    		{ 
    			printf("(%d, %d),(%d, %d)\n", T[i].weight, T[i].lchild, T[i].weight, T[i].rchild);
    			break;
    		}
    }
    
    // 哈夫曼编码
    void HFnode(HT T, int i, int j)
    { 
    	j = T[i].parent;
    	if (T[j].rchild == T[i].weight)
    		printf("l");
    	else
    	{ 
    		printf("0");
    	}
    
    	if (T[j].parent != -1)
    	{ 
    		i = j;
    		HFnode(T, i, j);
    	}
    }
    
    // 获取编码
    void Get_HFMTnode(HT T, int n)
    { 
    	int i, j, a;
    	printf("\n输入的权值的对应哈夫曼编码：");
    	for (i = 0; i < n; i++)
    	{ 
    		j = 0;
    		a = i;
    		printf("\n%id编码为：", T[i].weight);
    		HFnode(T, i, j);
    		i = a;
    	}
    }

**HuffmanTree.h**

#pragma once
    
    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAXLEN 100
    
    typedef struct
    { 
    	int weight;
    	int lchild, rchild, parent;
    }HTnode;
    
    typedef HTnode HT[MAXLEN];
    
    
    #ifdef __cplusplus
    extern "C" { 
    #endif 
    
    	// 初始化
    	void Init_HFMT(HT, int);
    
    	// 输入权值
    	void InputWight(HT, int);
    
    	// 选择最小结点
    	void SelectMin(HT, int, int, int);
    
    	// 创建哈夫曼树
    	void CreatHFMT(HT, int);
    
    	// 输出向量状态表
    	void ShowHFMT(HT, int n);
    
    	// 哈夫曼编码
    	void HFnode(HT, int, int);
    
    	// 获取编码
    	void Get_HFMTnode(HT, int);
    
    #ifdef __cplusplus
    }
    #endif

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70]: /images/20221014/e672422ada274ee18d9287a9f7811976.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 1]: /images/20221014/2b50d6a20932434aad6adbe2903fe712.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 2]: /images/20221014/dc51065d586249ba92ddafb8e1ed19d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 3]: /images/20221014/4544caab8f1a495b95f221f06aa15042.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 4]: /images/20221014/7b7b2b533d0a44c79d42f1896a21fc98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 5]: /images/20221014/71801ce3ac0b4f05b42978cd4c4c13c4.png
[20210605114956669.png]: /images/20221014/570183f7d9b746b3bfafe09556382130.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 6]: /images/20221014/b60a8b57a5254201a4bc0fe0f9439946.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 7]: /images/20221014/33c39a30e9a543f798d1c63640d9c205.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 8]: /images/20221014/5969a4e6eeec42d9b467bf1129bc91bf.png
[20210606101615250.png]: /images/20221014/ca9733f862a447988ee8306a572b810e.png
[20210606101543843.png]: /images/20221014/f831fc1d9eb545299d405629f07f5980.png
[20210606101521557.png]: /images/20221014/d2b8fb44f8d84b39860b20b906dde5e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 9]: /images/20221014/4366101a8d404593be99110db19c84a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 10]: /images/20221014/6c41d3804e1f41e597c547d22d193549.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 11]: /images/20221014/99fbcae72d834104a07ae93ff6790241.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 12]: /images/20221014/20b0c97c9fd84d968ae14827f94b215e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 13]: /images/20221014/72849a4707a341aeb69e88cb38b6f49b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 14]: /images/20221014/848c929939974646921f9d5b364c986a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 15]: /images/20221014/338f7c040664460f95704cfed6cc6cda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 16]: /images/20221014/14cd3e2b4d6242ae9c3a34b5a11d16a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 17]: /images/20221014/0ef6ab786cd04d2e96447892b048306f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 18]: /images/20221014/b4876756cdf14e07822a72bb5d7197cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 19]: /images/20221014/2bb1f98f037542499a282c8d49f1d1c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 20]: /images/20221014/f3c53b8624714b10b1c0f43a263e53b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 21]: /images/20221014/ad9197e1353e43788066cfd637fd54d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 22]: /images/20221014/e38a4945f03b4930aab707c69f26ad7b.png