2019 September 09 CPP基础

C/CPP与数据结构-第三节树（二）

二叉树的创建

中序和先序创建树

根据中序遍历的结果能确定一棵树吗？
1. 中序遍历：结果为：“12345”，但是这个树有多种情况
如何才能确定一棵树？
1. 结论：
  1. 通过中序遍历结果和先序遍历结果可以确定一个树
  2. 通过中序遍历和后续遍历可以确定一个树
  3. 通过先序遍历和后序遍历确定不了一个树。
2. 单独先序遍历：能求解根，但不能求解左子树什么时候结束、右子树什么时候开始。
根据先序和中序结果画树
1. 算法：
  1. 通过先序遍历找到根结点A，再通过A在中序遍历的位置找出左子树，右子树
  2. 在A的左子树中，找左子树的根结点（在先序中找），转步骤1
  3. 在A的右子树中，找右子树的根结点（在先序中找），转步骤1
2. 举例：
  1. 先序遍历结果：ADEBCF 中序遍历结果：DEACFB
  2. 根据算法分析：
    1. 通过线序遍历结果可知，A为整棵树的根
    2. 在中序遍历结果中找到A，则A的左边DE为左子树，A的右边CFB为右子树
    3. 左子树：DE在先序中找，D在E的前面，则D为左子树的根
    4. 在中序遍历结果中找D，发现D在E的前面，说明E不是D的左子树，一定是D的右子树，则A的左树确定完成
    5. 右子树： CFB在线序中找，B在最前面，则B为右子树的根
    6. 在中序中找到B,则B的左边CF为B的左子树，B的右子树没有
    7. CF在先序中找，C在前面，则C为B的左子树的根
    8. 在中序中找到C，F在C的右边，说明C没有左子树，F为C的右子树，则A的右树确定完成
    9. 结果：A(D(,E),B(C(,F),))

`#`法创建树

什么是#号法创建树
1. #创建树，让树的每一个节点都变成度数为2的树，子树没有就用#代替
2. 这样线序遍历就可以唯一确定一棵树
3. 特点：叶子的的左子树和右子树，一定是2个#
#号法画出树关键点
1. 要清楚的确定左子树什么结束，右子树什么时候开始。
示例分析：
1. 先序遍历：ABDH#K###E##CFI###G#J##,请画出树的形状
2. 分析：
  1. A一定是整棵树的根
  2. B一定是A的左子树的根
  3. D一定是B的左子树的根
  4. H一定是D的左子树的根
  5. H有后面是#K，说明H的左子树没有，右子树为K
  6. K的后面是##则说明，K就是叶子了
  7. 此时到D的右子树了，K后面的第3个为#，说明D的右子树没有
  8. 此时到B的右子树了，上面的#后面为E，说明B的右子树为E
  9. E后面2个##说明E是叶子了
  10. 则此时A的左子树完成
  11. C为A的右子树
  12. F为C的左子树根，I为F的左子树根
  13. I的右边有2个##说明I是叶子
  14. 此时到F的右子树，I后面的第三个#说明F的右子树没有
  15. 此时到C的右子树，则C的右子树为G
  16. G后面为#则G的左子树没有
  17. 则G的右子树为J
  18. J后面为2个##,说明J是叶子
  19. 此时A的右子树完成

代码实战

 //利用前序遍历来建树（结点值陆续从键盘输入，用DLR为宜）
 Bintree createBTpre( )
 {      
 Bintree T; 
 char ch;
         scanf(“%c”,&ch);
         if(ch==’#’) 
 T=NULL; 
         else
         {   T=( Bintree )malloc(sizeof(BinTNode));
             T->data=ch;
             T->lchild=createBTpre(); 
             T->rchild=createBTpre();
         }        
         return T;
 }
    
 //后序遍历销毁一个树
 void  BiTree_Free(BiTNode* T)
 {
 	BiTNode *tmp = NULL;
 	if (T!= NULL)
 	{
 		if (T->rchild != NULL) BiTree_Free(T->rchild);
 		if (T->lchild != NULL) BiTree_Free(T->lchild);
 		if (T != NULL)
 		{
 			free(T); 
 			T = NULL;
 		}
 	}
 }

二叉线索树

线索化概念：
1. 普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。
2. 若可将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。
3. 二叉线索树思想是干什么的？-中序遍历这棵树===》转换成链表访问
4. 二叉链表只能找到结点的左右孩子信息，而不能得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历过程中才能得到，我们可否都二叉树的链表进行改造？
5. 规定：
  1. 若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱（即线索）
  2. 若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后驱（即线索）
  3. 为了避免混淆，到底lchild指的是什么，则增加两个标志域，如：lchild LTag data RTag rchild
  4. 约定：
    1. 当Tag为0时，表示正常情况；当Tag为1时，表示线索情况；
6. 结论：
  1. 线索化过程就是在遍历过程（假设是中序遍历）中修改空指针的过程：
  2. 将空的lchild改为结点的直接前驱；
  3. 将空的rchild改为结点的直接后继
7. 线索化思想训练；
  1. 如下面的树
    1. 该树中序遍历结果为：HDIBJEAFCG
    2. 上面讲的前驱、后继指的是树按照一定的方式(先序、中序、后序)遍历后，结点的前后顺序
      1. 比如：I的前驱是D，后继是B
  2. 右空指针线索化如下：
  3. 左空指针线索化如下：
  4. 上面2图，空心箭头实线为前驱，实心箭头虚线为后继，可以看出，其实线索二叉树，等于把一棵二叉树转变成了一个双向链表，这样我们的插入删除节点，查找某个节点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。

线索化的实现：

线索化树结点

 typedef  struct BiThrNode	       /* 二叉线索存储结点结构 */
 {
 	char		data;	/* 结点数据 */
 	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
 	int			LTag;
 	int			RTag;		/* 左右标志 */
 } BiThrNode, *BiThrTree;

悬空指针的处理
1. 有了线索二叉树之后，我们对它进行遍历时发现，其实就等于是操作一个双向链表结构。
2. 那么第一个节点H没有前驱，最后一个结点G没有后继，这两个悬空指针该如何处理呢？
  1. 和双向链表结构一样，在二叉树线索链表上添加一个头结点，如下图，
    1. 令其lchild指向二叉树的根节点
    2. 其rchild指向当前树中序遍历时的最后一个结点
    3. 中序遍历第一个结点的lchild是悬空的指向这个头结点
    4. 中序遍历最后一个结点rchild是悬空的也指向这个头结点
3. 这样做的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

代码实现：

 #define  _CRT_SECURE_NO_WARNINGS 
 #include "string.h"
 #include "stdio.h"    
 #include "stdlib.h"   
        
 /* Link==0表示指向左右孩子指针, */
 /* Thread==1表示指向前驱或后继的线索 */
 #define Thread 1
 #define Link	0
        
 typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
 {
 	char		data;	/* 结点数据 */
 	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
 	int			LTag;
 	int			RTag;		/* 左右标志 */
 } BiThrNode, *BiThrTree;
        
 char Nil='#'; /* 字符型以空格符为空 */
        
 /* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
 BiThrNode* CreateBiThrTree()
 { 
 	BiThrNode *tmp = NULL;
 	char ch;
 	scanf("%c",&ch);
        
 	if (ch == '#')
 	{
 		return NULL;
 	}	
 	else
 	{
 		tmp = (BiThrNode *)malloc(sizeof(BiThrNode));
 		if (tmp == NULL)
 		{
 			return NULL;
 		}
 		memset(tmp, 0, sizeof(BiThrNode));
 		tmp->data = ch;
        
 		tmp->lchild = CreateBiThrTree(); /* 递归构造左子树 */
 		tmp->rchild = CreateBiThrTree();
 	}
 	return tmp;
 }
        
 BiThrNode  *pre; /* 全局变量,始终指向刚刚访问过的结点 */
 /* 中序遍历进行中序线索化 */
 void InThreading(BiThrNode *p)
 { 
 	if(p)
 	{
 		InThreading(p->lchild); // 递归左子树线索化 
 		if(p->lchild == NULL)	// 没有左孩子 
 		{
 			p->LTag = Thread; 	 p->lchild = pre;	//前驱线索 左孩子指针指向前驱 
 		}
 		if(pre->rchild == NULL) // 前驱没有右孩子 
 		{
 			pre->RTag = Thread;  pre->rchild = p;	// 后继线索 前驱右孩子指针指向后继(当前结点p) 
 		}
 		pre = p;				// 保持pre指向p的前驱 
 		InThreading(p->rchild); // 递归右子树线索化 
 	}
 }
        
 /* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
 BiThrNode* InOrderThreading(BiThrTree T)
 {
 	BiThrNode *Thrt = NULL;
        
 	Thrt = (BiThrNode *)malloc(sizeof(BiThrNode)); //建头结点 
 	if (Thrt == NULL)
 	{
 		return NULL;
 	}
 	memset(Thrt, 0, sizeof(BiThrNode));
        
 	Thrt->LTag = Link;  //左孩子为孩子指针
 	Thrt->RTag = Thread; //右孩子为线索化的指针
 	Thrt->rchild = Thrt; // 右指针回指 */  //步骤2和4
 	if(T == NULL) // 注意！！！！： 若二叉树空,则左指针回指 
 	{
 		Thrt->lchild  = Thrt; //步骤1和3
 	}
 	else
 	{
 		Thrt->lchild = T;	//步骤1 
 		pre = Thrt ;
 		InThreading(T);		// 中序遍历进行中序线索化 
 		pre->rchild = Thrt;	//步骤4
 		pre->RTag = Thread;	// 最后一个结点线索化 
 		Thrt->rchild = pre;	//步骤2
 	}
 	return Thrt;
 }
        
 /* 中序遍历二叉线索树T(头结点)的非递归算法 */
 int InOrderTraverse_Thr(BiThrNode* T)
 { 
 	BiThrNode* p;
 	p = T->lchild; /* p指向根结点 */
 	while (p != T)
 	{ 
 		/* 空树或遍历结束时,p==T */
 		while (p->LTag == Link)
 			p = p->lchild;
 		printf("%c ", p->data);
        
 		//如果中序遍历的最后一个结点的 右孩子 == T 说明到最后一个结点 ,遍历结束..
 		while (p->RTag==Thread && p->rchild!=T)
 		{
 			p = p->rchild;
 			printf("%c ", p->data);
 		}
 		p = p->rchild;
 	}
 	return 0;
 }
        
 /* 中序遍历二叉线索树T(头结点)的非递归算法 */
 int InOrderTraverse_Thr2(BiThrNode* T)
 { 
 	BiThrNode* p;
 	p = T->rchild; /* p指向根结点 */
 	while (p != T)
 	{ 
 		/* 空树或遍历结束时,p==T */
 		while (p->RTag == Link)
 			p = p->rchild;
 		printf("%c ", p->data);
        
 		//如果中序遍历的最后一个结点的 右孩子 == T 说明到最后一个结点 ,遍历结束..
 		while (p->LTag==Thread && p->lchild!=T)
 		{
 			p = p->lchild;
 			printf("%c ", p->data);
 		}
 		p = p->lchild;
 	}
 	return 0;
 }
        
        
 int main()
 {
 	BiThrTree T, H;
 	printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
 	T = CreateBiThrTree(); // 按前序产生二叉树 
 	H = InOrderThreading(T); // 中序遍历,并中序线索化二叉树 
 	printf("中序遍历(输出)二叉线索树:\n");
 	InOrderTraverse_Thr(H); // 中序遍历(输出)二叉线索树 
        
 	printf("\n逆序访问:");
 	InOrderTraverse_Thr2(H);
        
 	printf("\n");
 	system("pause");
 	return 0;
 }

霍夫曼树

概念：
1. 给定n个数值{ v1, v2, …, vn}
2. 根据这n个数值构造二叉树集合F
3. F = { T1, T2, …, Tn}
  1. Ti的数据域为vi，左右子树为空
4. 在F中选取两棵根结点的值最小的树作为左右子树构造一棵新的二叉树，这棵二叉树的根结点中的值为左右子树根结点中的值之和
5. 在F中删除这两棵子树，并将构造的新二叉树加入F中
6. 重复3和4，直到F中只剩下一个树为止。这棵树即霍夫曼树
举例：
1. 集合M：{A27,B8,C15,D15,E30,F5}
2. 集合M中的最小2个结点为F5,与B8，生成新的二叉树为13,此时集合M为:{A27,C15,D15,E30,13}
3. 集合M中的最小2个结点为13,与C15，生成新的二叉树为28,此时集合M为:{A27,D15,E30,28}
4. 集合M中的最小2个结点为D15,与A27，生成新的二叉树为42,此时集合M为:{42,E30,28}
5. 集合M中的最小2个结点为28,与E30，生成新的二叉树为58,此时集合M为:{42,58}
6. 集合M中的最小2个结点为42,58,之后一个结点为100
7. 最后形成的树如下：
补充
1. 霍夫曼树是一种特殊的二叉树
2. 霍夫曼树应用于信息编码和数据压缩领域
3. 霍夫曼树是现代压缩算法的基础

C/CPP与数据结构-第三节 树（二）

二叉树的创建

中序和先序创建树

#法创建树

二叉线索树

霍夫曼树

C/CPP与数据结构-第三节树（二）

`#`法创建树