《大话数据结构》第六章树

骑猪看日落 2022-03-16 02:44 377阅读 0赞

### 《大话数据结构 》 ###

*  第六章 树
 *   *  树的存储结构表示法
     *  二叉树
     *   *  顺序存储二叉树
         *  顺序存储二叉树测试案例
         *  二叉链表
         *  二叉链表测试案例
         *  线索二叉树
         *  线索二叉树链测试案例
     *  郝夫曼树与郝夫曼编码

# 第六章 树 #

树的定义：树（Tree）是n(n>=0)个结点的有限集。线性表是一对一的结构，**而树则是一对多的结构**。  
  条件：(1) **有且仅有一个根结点**。(2) 子树的个数没有限制，但一定**互不相交**。  
  树的结点包含一个数据元素以及若干指向其子树的分支。**结点拥有的子树数称为结点的度**(Degree)。度为0的结点称为叶结点(Leaf)或者终端结点。度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。  
       ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]  
  点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层，**树中结点的最大层次称为树的深度**(Depth)或者高度。  
       ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]

## 树的存储结构表示法 ##

**双亲表示法**：每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，**每个结点除了知道自己是谁以外，还知道它的双亲在哪里**。结点结构：其中data是数据域，存储结点的数据信息，而parent是指针域，存储该结点的双亲在数组中的下标。由于根结点没有双亲，所以我们约定根结点的设置域为-1，这就意味者，所有的根结点都存有他双亲的位置。**双亲表示法默认了所有结点的位置标号按从上到下、从左到右依次增加，第一行是0，第二行从左到右是1、2**。

双亲表示法结点PTNode的结构：

<table> 
 <thead> 
  <tr> 
   <th>int data</th> 
   <th>int parent</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

树的结构：

<table> 
 <thead> 
  <tr> 
   <th>PTNode nodes[MAX_TREE_SIZE]</th> 
   <th>int r,n；根的位置和结点数</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

数据结构：

#define MAX_TREE_SIZE  100
    typedef int TelemType;
    typedef  struct PTNode{ 
    	TElemType data;  //结点数据
    	int parent;
    }PTNode;
    typedef struct 
    { 
    	PTNode nodes{ MAX_TREE_SIZE};//结点数组
    	int r,n; //根的位置和结点数
    }PTree;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 2]  
**孩子表示法的改进**：孩子表示法不能像双亲表示法那样，双亲表示法任何一个结点肯定是只有1个父结点，用int parent存储父亲位置即可，孩子表示法如果用这种方式int child; int child1; …你不知道每个结点到底有几个子节点，即每个结点的度是不一样的。倘若安装树的深度来确定结点最大度n，然后每个结点设置n个变量指向子节点，显然是对资源的浪费。倘若每个结点中增加一个变量int degree; degree表示该结点的度域，存储该结点的孩子结点个数，克服了空间的浪费，这样在运算上需要维护结点度的数值，运算上会带来时间上的损耗。  
  因此，对孩子表示法设计的结构进行改进，设计两种结构，**ChildPtr孩子结点和表头结点ChildTableNode**，表头数组的**表头结点p存放每放该结点的值和其第一个孩子结点指针**。第一个孩子结点会存放它的下标位置，并指向p的下一个孩子结点，若没有则为null。树的结构由所有的表头结点（ChildTableNode\[\]）与表头结点存储的值组成。每个结点的位置标号还是按从上到下、从左到右依次增加。

ChildTableNode 表头结点：

<table> 
 <thead> 
  <tr> 
   <th>int data</th> 
   <th>ChildPtr firstChild</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

孩子结点ChildPtr：

<table> 
 <thead> 
  <tr> 
   <th>int child 孩子结点的下标</th> 
   <th>ChildPtr next</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

树的结构：

<table> 
 <thead> 
  <tr> 
   <th>ChildTableNode nodes[MAX_TREE_SIZE]</th> 
   <th>int r,n；根的位置和结点数</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

主要还是要记住下面的图：  
     ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 3]  
改进的孩子表示法代码：注意struct的定义结构体用法，注意typedef将结构体取别名，用结构体指针表示，typedef 结构体取别名用法。

#define MAX_TREE_SIZE  100;
    struct 
    { 
    	int data;
    	ChildPtr firstChild;
    }ChildTableNode;
    #typedef struct Child{ 
    	int child;  //孩子结点下标位置
    	Child *next;
    } *ChildPtr;
    typedef struct 
    { 
    	ChildTableNode[MAX_SIZE_TREE];
    	int r,n;  //根结点位置 ，结点个数
    }Tree;

**孩子兄弟表示法**：任意一个结点如果它的右兄弟存在，那么右兄弟肯定是唯一的。  
Child结点结构：

<table> 
 <thead> 
  <tr> 
   <th>int data</th> 
   <th>Child *firstChild</th> 
   <th>Child *rightChild</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

树：

<table> 
 <thead> 
  <tr> 
   <th>int data</th> 
   <th>Child *firstChild</th> 
   <th>Child *rightChild</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

结构体定义代码：

typedef struct ChildNode
    { 
    	int data;
    	struct ChildNode *firstChild,*rightChild;
    }ChildNode,*Tree;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 4]  
简单使用：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 5]

## 二叉树 ##

**特点**：每个结点最多两颗子树，每个结点的子树左右是分顺序，即使只有一颗子树也要区分是左子树还是右子树。  
**特殊的二叉树**：左斜树(所有的结点只有左子树)、右斜树(所有的结点只有右左树)、满二叉树(所有的分支结点只有左右子树，并且所有的叶子都在同一层)、完全二叉树(除了最后一层每一层结点都达到最大值)。满二叉树一定是一颗完全二叉树，但是完全二叉树不一定是满的。  
**二叉树的性质**： ,

1.  在二叉树的第 i 层上最多有2i-1个结点（i>=1）.
2.  深度为k的二叉树至多有2i\-1个结点(i≥1)
3.  对任何一棵二叉树T，其叶子结点数=度为2的结点数+1
4.  具有n个结点的完全二叉树的深度不大于log2nlog2n+1的最大整数
5.  如果对一棵有n个结点的完全二叉树的结点按层序编号（每层从左到右），对任一结点i(1≤i≤n)有  
      如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点i/2  
      如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i  
      如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1  
            ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 6]

### 顺序存储二叉树 ###

**顺序存储结构**：只适用于完全二叉树。若某个结点不存在，对应标号的结点值设置为倒V。若深度为k的右斜树，只有k个结点，但是却要分配2的k次方-1个存储空间，太浪费。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 7]  
完全二叉树采用顺序存储的方式，你可以看出优势。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 8]  
        ![在这里插入图片描述][20190304203822994.png]  
**顺序存储二叉树的数据结构**：使用前提：完全二叉树。 SqBiTree T; 用一个MAX\_TREE\_SIZE大小的数组即可表示顺序二叉树。

#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */
    typedef int TElemType;  /* 树结点的数据类型，目前暂定为整型 */
    typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */
    TElemType Nil=0; /* 设整型以0为空 */
    typedef struct
    { 
    	int level,order; /* 结点的层,本层序号(按满二叉树计算) */
    }Position;

顺序存储二叉树

*  判断是否为空：判断根结点T\[0\]是否为Nil，假定Nil为0 是空。
 *  求树的深度：先遍历看T\[i\]是否出现Nil，若出现空，跳出遍历，j = 0;遍历j的2次方是否大于i。若大于，跳出遍历深度为j-1。
 *  给树T的某个位置p(树的层数，该层的序号)赋值e。先通过p获得T\[\]下标i，给叶子赋非空值但双亲为空if(value!=Nil&&T\[(i+1)/2-1\]==Nil) ，或者给双亲赋空值但有叶子（不空）if(value= =Nil&&(T\[i*2+1\]!=Nil||T\[i*2+2\]!=Nil))情形下 return ERROR;
 *  先序遍历：  
    void PreTraverse(SqBiTree T,int e)  
    \{  
       visit(T\[e\]);  
       if(T\[2*e+1\]!=Nil) /* 左子树不空 */  
          PreTraverse(T,2*e+1);  
       if(T\[2*e+2\]!=Nil) /* 右子树不空 */  
          PreTraverse(T,2*e+2);  
    \}  
    Status PreOrderTraverse(SqBiTree T)  
    \{  
       if(!BiTreeEmpty(T)) /\* 树不空 */  
         PreTraverse(T,0);  
       printf("\\n");  
       return OK;  
    \}  
    中序遍历：  
    void InTraverse(SqBiTree T,int e)  
    \{  
       if(T\[2*e+1\]!=Nil) /\* 左子树不空 */  
          InTraverse(T,2*e+1);  
       visit(T\[e\]);  
       if(T\[2*e+2\]!=Nil) /* 右子树不空 */  
          InTraverse(T,2*e+2);  
    \}  
    /\* 操作结果: 中序遍历T。 */  
    Status InOrderTraverse(SqBiTree T)  
    \{  
       if(!BiTreeEmpty(T)) /* 树不空 */  
          InTraverse(T,0);  
       printf("\\n");  
       return OK;  
    \}  
    后序遍历：  
    /* PostOrderTraverse()调用 */  
    void PostTraverse(SqBiTree T,int e)  
    \{  
       if(T\[2*e+1\]!=Nil) /\* 左子树不空 */  
          PostTraverse(T,2*e+1);  
       if(T\[2*e+2\]!=Nil) /* 右子树不空 */  
          PostTraverse(T,2*e+2);  
       visit(T\[e\]);  
    \}  
    /\* 操作结果: 后序遍历T。 */  
    Status PostOrderTraverse(SqBiTree T)  
    \{  
       if(!BiTreeEmpty(T)) /* 树不空 \*/  
          PostTraverse(T,0);  
       printf("\\n");  
       return OK;  
    \}

### 顺序存储二叉树测试案例 ###

10个结点的顺序树，第一层 根结点为1，第二层 2 、3，第三层 4、5、6 ，第四层 7、8、9、10。

#include "stdio.h"    
    	#include "stdlib.h"   
    	#include "io.h"  
    	#include "math.h"  
    	#include "time.h"
    	
    	#define OK 1
    	#define ERROR 0
    	#define TRUE 1
    	#define FALSE 0
    	
    	#define MAXSIZE 100 /* 存储空间初始分配量 */
    	#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */
    	
    	typedef int Status;		/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    	typedef int TElemType;  /* 树结点的数据类型，目前暂定为整型 */
    	typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */
    	
    	typedef struct
    	{ 
    		int level,order; /* 结点的层,本层序号(按满二叉树计算) */
    	}Position;
    	
    	TElemType Nil=0; /* 设整型以0为空 */
    	
    	Status visit(TElemType c)
    	{ 
    		printf("%d ",c);
    		return OK;
    	}
    	
    	/* 构造空二叉树T。因为T是固定数组，不会改变，故不需要& */
    	Status InitBiTree(SqBiTree T)
    	{ 
    		int i;
    		for(i=0;i<MAX_TREE_SIZE;i++)
    			T[i]=Nil; /* 初值为空 */
    		return OK;
    	}	
    	/* 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T */
    	Status CreateBiTree(SqBiTree T)
    	{  
    		int i=0;
    	 	printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n",MAX_TREE_SIZE);
    		while(i<10)
    		{ 
    			T[i]=i+1;
    			i++;
    		}
    		while(i<MAX_TREE_SIZE)  //设整型以0为空
    		{ 
    			T[i]=Nil; /* 将空赋值给T的后面的结点 */
    			i++;
    		}
    	
    		return OK;
    	}
    
    	#define ClearBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */
    	
    	/* 初始条件: 二叉树T存在 */
    	/* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
    	Status BiTreeEmpty(SqBiTree T)
    	{  
    		if(T[0]==Nil) /* 根结点为空,则树空 */
    			return TRUE;
    		else
    			return FALSE;
    	}
    	
    	/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
    	int BiTreeDepth(SqBiTree T)
    	{  
    	   int i,j=-1;
    	   for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最后一个结点 */
    	     if(T[i]!=Nil)
    	       break;
    	   i++; 
    	   do
    	     j++;
    	   while(i>=powl(2,j));/* 计算2的j次幂。 */
    	   return j;
    	}	
    	/* 初始条件: 二叉树T存在 */
    	/* 操作结果: 当T不空,用e返回T的根,返回OK;否则返回ERROR,e无定义 */
    	Status Root(SqBiTree T,TElemType *e)
    	{  
    		if(BiTreeEmpty(T)) /* T空 */
    			return ERROR;
    		else
    		{ 	
    			*e=T[0];
    			return OK;
    		}
    	}	
    	/* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
    	/* 操作结果: 返回处于位置e(层,本层序号)的结点的值 */
    	TElemType Value(SqBiTree T,Position e)
    	{  
    		 return T[(int)powl(2,e.level-1)+e.order-2];
    	}
    	
    	/* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
    	/* 操作结果: 给处于位置e(层,本层序号)的结点赋新值value */
    	Status Assign(SqBiTree T,Position e,TElemType value)
    	{  
    		int i=(int)powl(2,e.level-1)+e.order-2; /* 将层、本层序号转为矩阵的序号 */
    		if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 给叶子赋非空值但双亲为空 */
    			return ERROR;
    		else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /* 给双亲赋空值但有叶子（不空） */
    			return ERROR;
    		T[i]=value;
    		return OK;
    	}
    	
    	/* 初始条件: 二叉树T存在,e是T中某个结点 */
    	/* 操作结果: 若e是T的非根结点,则返回它的双亲,否则返回＂空＂ */
    	TElemType Parent(SqBiTree T,TElemType e)
    	{  
    		int i;
    		if(T[0]==Nil) /* 空树 */
    			return Nil;
    		for(i=1;i<=MAX_TREE_SIZE-1;i++)
    			if(T[i]==e) /* 找到e */
    				return T[(i+1)/2-1];
    		return Nil; /* 没找到e */
    	}
    	
    	/* 初始条件: 二叉树T存在,e是T中某个结点 */
    	/* 操作结果: 返回e的左孩子。若e无左孩子,则返回＂空＂ */
    	TElemType LeftChild(SqBiTree T,TElemType e)
    	{  
    		int i;
    		if(T[0]==Nil) /* 空树 */
    			return Nil;
    		for(i=0;i<=MAX_TREE_SIZE-1;i++)
    			if(T[i]==e) /* 找到e */
    				return T[i*2+1];
    		return Nil; /* 没找到e */
    	}	
    	/* 初始条件: 二叉树T存在,e是T中某个结点 */
    	/* 操作结果: 返回e的右孩子。若e无右孩子,则返回＂空＂ */
    	TElemType RightChild(SqBiTree T,TElemType e)
    	{  
    		int i;
    		if(T[0]==Nil) /* 空树 */
    			return Nil;
    		for(i=0;i<=MAX_TREE_SIZE-1;i++)
    			if(T[i]==e) /* 找到e */
    				return T[i*2+2];
    		return Nil; /* 没找到e */
    	}	
    	/* 初始条件: 二叉树T存在,e是T中某个结点 */
    	/* 操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂ */
    	TElemType LeftSibling(SqBiTree T,TElemType e)
    	{  
    		int i;
    		if(T[0]==Nil) /* 空树 */
    			return Nil;
    		for(i=1;i<=MAX_TREE_SIZE-1;i++)
    			if(T[i]==e&&i%2==0) /* 找到e且其序号为偶数(是右孩子) */
    				return T[i-1];
    		return Nil; /* 没找到e */
    	}	
    	/* 初始条件: 二叉树T存在,e是T中某个结点 */
    	/* 操作结果: 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂ */
    	TElemType RightSibling(SqBiTree T,TElemType e)
    	{  
    		int i;
    		if(T[0]==Nil) /* 空树 */
    			return Nil;
    		for(i=1;i<=MAX_TREE_SIZE-1;i++)
    			if(T[i]==e&&i%2) /* 找到e且其序号为奇数(是左孩子) */
    				return T[i+1];
    		return Nil; /* 没找到e */
    	}	
    	/* PreOrderTraverse()调用 */
    	void PreTraverse(SqBiTree T,int e)
    	{  
    		visit(T[e]);
    		if(T[2*e+1]!=Nil) /* 左子树不空 */
    			PreTraverse(T,2*e+1);
    		if(T[2*e+2]!=Nil) /* 右子树不空 */
    			PreTraverse(T,2*e+2);
    	}	
    	/* 初始条件: 二叉树存在 */
    	/* 操作结果: 先序遍历T。 */
    	Status PreOrderTraverse(SqBiTree T)
    	{  
    		if(!BiTreeEmpty(T)) /* 树不空 */
    		 PreTraverse(T,0);
    		printf("\n");
    		return OK;
    	}	
    	/* InOrderTraverse()调用 */
    	void InTraverse(SqBiTree T,int e)
    	{  
    		if(T[2*e+1]!=Nil) /* 左子树不空 */
    			InTraverse(T,2*e+1);
    		visit(T[e]);
    		if(T[2*e+2]!=Nil) /* 右子树不空 */
    			InTraverse(T,2*e+2);
    	}	
    	/* 初始条件: 二叉树存在 */
    	/* 操作结果: 中序遍历T。 */
    	Status InOrderTraverse(SqBiTree T)
    	{  
    		if(!BiTreeEmpty(T)) /* 树不空 */
    			InTraverse(T,0);
    		printf("\n");
    		return OK;
    	}	
    	/* PostOrderTraverse()调用 */
    	void PostTraverse(SqBiTree T,int e)
    	{  
    		if(T[2*e+1]!=Nil) /* 左子树不空 */
    			PostTraverse(T,2*e+1);
    		if(T[2*e+2]!=Nil) /* 右子树不空 */
    			PostTraverse(T,2*e+2);
    		visit(T[e]);
    	}	
    	/* 初始条件: 二叉树T存在 */
    	/* 操作结果: 后序遍历T。 */
    	Status PostOrderTraverse(SqBiTree T)
    	{  
    		if(!BiTreeEmpty(T)) /* 树不空 */
    			PostTraverse(T,0);
    		printf("\n");
    		return OK;
    	}	
    	/* 层序遍历二叉树 */
    	void LevelOrderTraverse(SqBiTree T)
    	{  
    		int i=MAX_TREE_SIZE-1,j;
    		while(T[i]==Nil)
    			i--; /* 找到最后一个非空结点的序号 */
    		for(j=0;j<=i;j++)  /* 从根结点起,按层序遍历二叉树 */
    			if(T[j]!=Nil)
    				visit(T[j]); /* 只遍历非空的结点 */
    		printf("\n");
    	}	
    	/* 逐层、按本层序号输出二叉树 */
    	void Print(SqBiTree T)
    	{  
    		int j,k;
    		Position p;
    		TElemType e;
    		for(j=1;j<=BiTreeDepth(T);j++)
    		{ 
    			printf("第%d层: ",j);
    			for(k=1;k<=powl(2,j-1);k++)
    			{ 
    				p.level=j;
    				p.order=k;
    				e=Value(T,p);
    				if(e!=Nil)
    					printf("%d:%d ",k,e);
    			}
    			printf("\n");
    		}
    	}
    	
    	int main()
    	{ 
    		Status i;
    		Position p;
    		TElemType e;
    		SqBiTree T;
    		InitBiTree(T);
    		CreateBiTree(T);
    		printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
    		i=Root(T,&e);
    		if(i)
    			printf("二叉树的根为：%d\n",e);
    		else
    			printf("树空，无根\n");
    		printf("层序遍历二叉树:\n");
    		LevelOrderTraverse(T);
    		printf("前序遍历二叉树:\n");
    		PreOrderTraverse(T);
    		printf("中序遍历二叉树:\n");
    		InOrderTraverse(T);
    		printf("后序遍历二叉树:\n");
    		PostOrderTraverse(T);
    		printf("修改结点的层号3本层序号2。");
    		p.level=3;
    		p.order=2;
    		e=Value(T,p);
    		printf("待修改结点的原值为%d请输入新值:50 ",e);
    		e=50;
    		Assign(T,p,e);
    		printf("前序遍历二叉树:\n");
    		PreOrderTraverse(T);
    		printf("结点%d的双亲为%d,左右孩子分别为",e,Parent(T,e));
    		printf("%d,%d,左右兄弟分别为",LeftChild(T,e),RightChild(T,e));
    		printf("%d,%d\n",LeftSibling(T,e),RightSibling(T,e));
    		ClearBiTree(T);
    		printf("清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
    		i=Root(T,&e);
    		if(i)
    			printf("二叉树的根为：%d\n",e);
    		else
    			printf("树空，无根\n");
    		
    		return 0;
    	}

运行结果：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 9]

### 二叉链表 ###

数据结构：  
BiTNode结点结构：

<table> 
 <thead> 
  <tr> 
   <th>int data</th> 
   <th>BiTNode *lchild</th> 
   <th>BiTNode *rchild</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

结点代码：

typedef struct BiTNode  /* 结点结构 */
    { 
       TElemType data;		/* 结点数据 */
       struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
    }BiTNode,*BiTree;

初始化并创建树：通过递归创建树，简直无敌。先设计一条str字符串 ABDH\#K\#\#\#E\#\#CFI\#\#\#G\#J\#\#，递归对字符串str进行判断，若遇到\#字符就返回，否则CreateBiTree(&((\*T)->lchild)); 或者 CreateBiTree(&((*T)->rchild)); /* 构造右子树 \*/，将树的左结点或者右结点当做递归函数的参数。

/* 用于构造二叉树********************************** */
    int index=1;
    typedef char String[24]; /* 0号单元存放串的长度 */
    String str;
    Status StrAssign(String T,char *chars)
    {  
    	int i;
    	if(strlen(chars)>MAXSIZE)
    		return ERROR;
    	else
    	{ 
    		T[0]=strlen(chars);
    		for(i=1;i<=T[0];i++)
    			T[i]=*(chars+i-1);
    		return OK;
    	}
    }
    /* 按前序输入二叉树中结点的值（一个字符） */
    /* #表示空树，构造二叉链表表示二叉树T。 */
    void CreateBiTree(BiTree *T)
    {  
    	TElemType ch;
    	ch=str[index++];
    
    	if(ch=='#') 
    		*T=NULL;
    	else
    	{ 
    		*T=(BiTree)malloc(sizeof(BiTNode));
    		if(!*T)
    			exit(OVERFLOW);
    		(*T)->data=ch; /* 生成根结点 */
    
    		CreateBiTree(&((*T)->lchild)); /* 构造左子树 */
    		CreateBiTree(&((*T)->rchild)); /* 构造右子树 */
    	}
     }
     void main{ 
    	BiTree T;
    	*T = NULL;		
    	StrAssign(str,"ABDH##I##EJ###CF##G##");
    	CreateBiTree(&T);
    }

字是真的丑啊  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 10]  
前序遍历、中序遍历：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 11]

### 二叉链表测试案例 ###

#include "string.h"
    	#include "stdio.h"    
    	#include "stdlib.h"   
    	#include "io.h"  
    	#include "math.h"  
    	#include "time.h"
    	
    	#define OK 1
    	#define ERROR 0
    	#define TRUE 1
    	#define FALSE 0
    	
    	#define MAXSIZE 100 /* 存储空间初始分配量 */
    	
    	typedef int Status;		/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    	
    	/* 用于构造二叉树********************************** */
    	int index=1;
    	typedef char String[24]; /* 0号单元存放串的长度 */
    	String str;
    	
    	Status StrAssign(String T,char *chars)
    	{  
    		int i;
    		if(strlen(chars)>MAXSIZE)
    			return ERROR;
    		else
    		{ 
    			T[0]=strlen(chars);
    			for(i=1;i<=T[0];i++)
    				T[i]=*(chars+i-1);
    			return OK;
    		}
    	}
    	/* ************************************************ */	
    	typedef char TElemType;
    	TElemType Nil=' '; /* 字符型以空格符为空 */
    	
    	Status visit(TElemType e)
    	{ 
    		printf("%c ",e);
    		return OK;
    	}	
    	typedef struct BiTNode  /* 结点结构 */
    	{ 
    	   TElemType data;		/* 结点数据 */
    	   struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
    	}BiTNode,*BiTree;
    		
    	/* 构造空二叉树T */
    	Status InitBiTree(BiTree *T)
    	{  
    		*T=NULL;
    		return OK;
    	}
    	
    	/* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
    	void DestroyBiTree(BiTree *T)
    	{  
    		if(*T) 
    		{ 
    			if((*T)->lchild) /* 有左孩子 */
    				DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
    			if((*T)->rchild) /* 有右孩子 */
    				DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
    			free(*T); /* 释放根结点 */
    			*T=NULL; /* 空指针赋0 */
    		}
    	}	
    	/* 按前序输入二叉树中结点的值（一个字符） */
    	/* #表示空树，构造二叉链表表示二叉树T。 */
    	void CreateBiTree(BiTree *T)
    	{  
    		TElemType ch;
    		ch=str[index++];
    	
    		if(ch=='#') 
    			*T=NULL;
    		else
    		{ 
    			*T=(BiTree)malloc(sizeof(BiTNode));
    			if(!*T)
    				exit(OVERFLOW);
    			(*T)->data=ch; /* 生成根结点 */
    	
    			CreateBiTree(&((*T)->lchild)); /* 构造左子树 */
    			CreateBiTree(&((*T)->rchild)); /* 构造右子树 */
    		}
    	 }	
    	/* 初始条件: 二叉树T存在 */
    	/* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
    	Status BiTreeEmpty(BiTree T)
    	{  
    		if(T)
    			return FALSE;
    		else
    			return TRUE;
    	}
    	
    	#define ClearBiTree DestroyBiTree
    	
    	/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
    	int BiTreeDepth(BiTree T)
    	{ 
    		int i,j;
    		if(!T)
    			return 0;
    		if(T->lchild)
    			i=BiTreeDepth(T->lchild);
    		else
    			i=0;
    		if(T->rchild)
    			j=BiTreeDepth(T->rchild);
    		else
    			j=0;
    		return i>j?i+1:j+1;
    	}	
    	/* 初始条件: 二叉树T存在。操作结果: 返回T的根 */
    	TElemType Root(BiTree T)
    	{  
    		if(BiTreeEmpty(T))
    			return Nil;
    		else
    			return T->data;
    	}	
    	/* 初始条件: 二叉树T存在，p指向T中某个结点 */
    	/* 操作结果: 返回p所指结点的值 */
    	TElemType Value(BiTree p)
    	{ 
    		return p->data;
    	}	
    	/* 给p所指结点赋值为value */
    	void Assign(BiTree p,TElemType value)
    	{ 
    		p->data=value;
    	}	
    	/* 初始条件: 二叉树T存在 */
    	/* 操作结果: 前序递归遍历T */
    	void PreOrderTraverse(BiTree T)
    	{  
    		if(T==NULL)
    			return;
    		printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    		PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
    		PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
    	}	
    	/* 初始条件: 二叉树T存在 */
    	/* 操作结果: 中序递归遍历T */
    	void InOrderTraverse(BiTree T)
    	{  
    		if(T==NULL)
    			return;
    		InOrderTraverse(T->lchild); /* 中序遍历左子树 */
    		printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    		InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
    	}	
    	/* 初始条件: 二叉树T存在 */
    	/* 操作结果: 后序递归遍历T */
    	void PostOrderTraverse(BiTree T)
    	{ 
    		if(T==NULL)
    			return;
    		PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
    		PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
    		printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    	}
    	
    	int main()
    	{ 
    		int i;
    		BiTree T;
    		TElemType e1;
    		InitBiTree(&T);		
    		StrAssign(str,"ABDH##I##EJ###CF##G##");	
    		CreateBiTree(&T);
    	
    		printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
    		e1=Root(T);
    		printf("二叉树的根为: %c\n",e1);
    	
    		printf("\n前序遍历二叉树:");
    		PreOrderTraverse(T);
    		printf("\n中序遍历二叉树:");
    		InOrderTraverse(T);
    		printf("\n后序遍历二叉树:");
    		PostOrderTraverse(T);
    		ClearBiTree(&T);
    		printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
    		i=Root(T);
    		if(!i)
    			printf("树空，无根\n");
    		
    		return 0;
    	}

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

### 线索二叉树 ###

在二叉树链的例子中，我们前序遍历一遍二叉树后得到ABDHKECFIGJ，此时我们才知道I的前驱是F，后继是G，但是必须要先遍历一遍才知道。二叉树链优点在于可以知道左右子树是谁，但是无法直接知道前驱后继。因此我们在二叉树链中加入指向前驱和后继的指针，加上的指针也称为线索，相应的二叉树链表称为线索二叉树。每个结点都只有一个直接前驱和一个直接后继。（除区头尾两个结点）  
结点的数据结构：

typedef enum { Link,Thread} PointerTag;	/* Link==0表示指向左右孩子指针, */
    										/* Thread==1表示指向前驱或后继的线索 */
    typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
    { 
    	TElemType data;	/* 结点数据 */
    	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
    	PointerTag LTag;
    	PointerTag RTag;		/* 左右标志 */
    } BiThrNode, *BiThrTree;

树的创建：

typedef char TElemType;
    typedef enum { Link,Thread} PointerTag;	/* Link==0表示指向左右孩子指针, */
    										/* Thread==1表示指向前驱或后继的线索 */
    typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
    { 
    	TElemType data;	/* 结点数据 */
    	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
    	PointerTag LTag;
    	PointerTag RTag;		/* 左右标志 */
    } BiThrNode, *BiThrTree;
    TElemType Nil='#'; /* 字符型以空格符为空 */
    /* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
    /* 0(整型)/空格(字符型)表示空结点 */
    Status CreateBiThrTree(BiThrTree *T)
    {  
    	TElemType h;
    	scanf("%c",&h);
    	if(h==Nil)
    		*T=NULL;
    	else
    	{ 
    		*T=(BiThrTree)malloc(sizeof(BiThrNode));
    		if(!*T)
    			exit(OVERFLOW);
    		(*T)->data=h; /* 生成根结点(前序) */
    		CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
    		if((*T)->lchild) /* 有左孩子 */
    			(*T)->LTag=Link;
    		CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
    		if((*T)->rchild) /* 有右孩子 */
    			(*T)->RTag=Link;
    	}
    	return OK;
    }
    int main()
    { 
    	BiThrTree H,T;
    	printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
     	CreateBiThrTree(&T); /* 按前序产生二叉树 */
    }

通常规定：对某一结点p，若无左子树，将p->lchild指向前驱结点；若无右子树，将p->rchild指向后继结点，不过由于此时p的后继还没访问到，因此只能对p的前驱结点pre进行右指针判断，如果pre的右指针为空，则p就是pre的后继pre->rchild = p。

核心的遍历代码：

/* 中序遍历进行中序线索化 */
    void InThreading(BiThrTree p)
    {  
    	if(p)
    	{ 
    		InThreading(p->lchild); /* 递归左子树线索化 */
    		if(!p->lchild) /* 没有左孩子 */
    		{ 
    			p->LTag=Thread; /* 前驱线索 */
    			p->lchild=pre; /* 左孩子指针指向前驱 */
    		}
    		if(!pre->rchild) /* 前驱没有右孩子 */
    		{ 
    			pre->RTag=Thread; /* 后继线索 */
    			pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
    		}
    		pre=p; /* 保持pre指向p的前驱 */
    		InThreading(p->rchild); /* 递归右子树线索化 */
    	}
    }

中序遍历解析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 12]

### 线索二叉树链测试案例 ###

#include "string.h"
    	#include "stdio.h"    
    	#include "stdlib.h"   
    	#include "io.h"  
    	#include "math.h"  
    	#include "time.h"
    	
    	#define OK 1
    	#define ERROR 0
    	#define TRUE 1
    	#define FALSE 0
    	
    	#define MAXSIZE 100 /* 存储空间初始分配量 */
    	
    	typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    	typedef char TElemType;
    	typedef enum { Link,Thread} PointerTag;	/* Link==0表示指向左右孩子指针, */
    											/* Thread==1表示指向前驱或后继的线索 */
    	typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
    	{ 
    		TElemType data;	/* 结点数据 */
    		struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
    		PointerTag LTag;
    		PointerTag RTag;		/* 左右标志 */
    	} BiThrNode, *BiThrTree;
    	
    	TElemType Nil='#'; /* 字符型以空格符为空 */
    	
    	Status visit(TElemType e)
    	{ 
    		printf("%c ",e);
    		return OK;
    	}
    	
    	/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
    	/* 0(整型)/空格(字符型)表示空结点 */
    	Status CreateBiThrTree(BiThrTree *T)
    	{  
    		TElemType h;
    		scanf("%c",&h);
    	
    		if(h==Nil)
    			*T=NULL;
    		else
    		{ 
    			*T=(BiThrTree)malloc(sizeof(BiThrNode));
    			if(!*T)
    				exit(OVERFLOW);
    			(*T)->data=h; /* 生成根结点(前序) */
    			CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
    			if((*T)->lchild) /* 有左孩子 */
    				(*T)->LTag=Link;
    			CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
    			if((*T)->rchild) /* 有右孩子 */
    				(*T)->RTag=Link;
    		}
    		return OK;
    	}
    	
    	BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
    	/* 中序遍历进行中序线索化 */
    	void InThreading(BiThrTree p)
    	{  
    		if(p)
    		{ 
    			InThreading(p->lchild); /* 递归左子树线索化 */
    			if(!p->lchild) /* 没有左孩子 */
    			{ 
    				p->LTag=Thread; /* 前驱线索 */
    				p->lchild=pre; /* 左孩子指针指向前驱 */
    			}
    			if(!pre->rchild) /* 前驱没有右孩子 */
    			{ 
    				pre->RTag=Thread; /* 后继线索 */
    				pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
    			}
    			pre=p; /* 保持pre指向p的前驱 */
    			InThreading(p->rchild); /* 递归右子树线索化 */
    		}
    	}
    	
    	/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
    	Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
    	{  
    		*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    		if(!*Thrt)
    			exit(OVERFLOW);
    		(*Thrt)->LTag=Link; /* 建头结点 */
    		(*Thrt)->RTag=Thread;
    		(*Thrt)->rchild=(*Thrt); /* 右指针回指 */
    		if(!T) /* 若二叉树空,则左指针回指 */
    			(*Thrt)->lchild=*Thrt;
    		else
    		{ 
    			(*Thrt)->lchild=T;
    			pre=(*Thrt);
    			InThreading(T); /* 中序遍历进行中序线索化 */
    			pre->rchild=*Thrt;
    			pre->RTag=Thread; /* 最后一个结点线索化 */
    			(*Thrt)->rchild=pre;
    		}
    		return OK;
    	}
    	
    	/* 中序遍历二叉线索树T(头结点)的非递归算法 */
    	Status InOrderTraverse_Thr(BiThrTree T)
    	{  
    		BiThrTree p;
    		p=T->lchild; /* p指向根结点 */
    		while(p!=T)
    		{  /* 空树或遍历结束时,p==T */
    			while(p->LTag==Link)
    				p=p->lchild;
    			if(!visit(p->data)) /* 访问其左子树为空的结点 */
    				return ERROR;
    			while(p->RTag==Thread&&p->rchild!=T)
    			{ 
    				p=p->rchild;
    				visit(p->data); /* 访问后继结点 */
    			}
    			p=p->rchild;
    		}
    		return OK;
    	}
    	
    	int main()
    	{ 
    		BiThrTree H,T;
    		printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
    	 	CreateBiThrTree(&T); /* 按前序产生二叉树 */
    		InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
    		printf("中序遍历(输出)二叉线索树:\n");
    		InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
    		printf("\n");
    		
    		return 0;
    	}

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

## 郝夫曼树与郝夫曼编码 ##

哈夫曼树（霍夫曼树）又称为最优树。  
**路径和路径长度**：例如下图左图，二叉树a的树路径长度为1+1+2+2+3+3+4+4 = 20，树b的路径长度1+2+3+3+2+1+2+2 = 16。  
**结点的权及带权路径长度**：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 13]  
**树的带权路径长度**：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。  
**郝夫曼编码**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 15]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 16]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]: /images/20220316/e6a841d26d5a4af1b7d5df5aa8fbb483.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]: /images/20220316/dc05910d3828433e9d1752c26d3f1fd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 2]: /images/20220316/5593aba4d94b42a39e70c914e11f970e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 3]: /images/20220316/086f56e1caf149baa46c69389fd05126.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 4]: /images/20220316/e544637f2d8343e8a2c3ce57a1d55776.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 5]: /images/20220316/78ef1d7daa7148e0ba296af527732584.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 6]: /images/20220316/dd032ac8de504862830d12d8e969daab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 7]: /images/20220316/23da848bee2f4298a7787a3b5aab1633.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 8]: /images/20220316/a3539c1e3d2f4bc785a4cf8ec3ae451e.png
[20190304203822994.png]: /images/20220316/30639909fb0947148dce75e384a4d2a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 9]: /images/20220316/f513c443566842a3ab08a613edc96dc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 10]: /images/20220316/cc78c119ae8c45d9b95a447cc880082c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 11]: /images/20220316/2f2474b2e45447a0aa500962f7368e15.png
[20190305104915577.png]: /images/20220316/761b03c2e0924c7ab1ccaaeb47e1b453.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 12]: /images/20220316/7d19a53f7deb473985ed1013ed92ce56.png
[20190305135544996.png]: /images/20220316/17b1ef26f0304c09adf5caef2dac300b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 13]: /images/20220316/f087c9a93ffd484dafdbb707e52192b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 14]: /images/20220316/ae9e050697a14762a578f3151d78bdc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 15]: /images/20220316/85db46f35c3846feafd0fc52a1920790.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 16]: /images/20220316/bd87cb430c9f45cd9f3bbb9cf910f0fd.png