五、线索二叉树

1.什么是线索二叉树

遍历二叉树的结果是，求得结点的一个线性序列，结点中再添加两个标记“LTag和RTag”,来判断当前结点是否有孩子

• 若左子树不空，则，将lchild指向其左子树，且左标志域的值为“Link”;否则(空)，lchild指向前驱，且左标志的值为“Thread”
• 若右子树不空，则，将lchild指向其右子树，且右志域的值为“Link”;否则(空)，lchild指向后继，且右标志的值为“Thread”

总之，不空正常指向。空，左：指向前驱；右：指向后继(若无头针，则可能有空悬)

类型描述如下

typedef struct BiNode {
	Datatype data;//数据内容
	struct BiNode  *Lchild;//指向左孩子结点
	struct BiNode  *rchild;//指向右孩子结点
	int Ltag;//值为0，则Lchild指向该结点的左孩子；值为1.指向该结点的前驱结点
	int rtag;//值为0，则rchild指向该结点的右孩子；值为1.指向该结点的后继结点
} BiNode ;

三种遍历

先序

中序

后序

要会自己划线，实线是指针，虚线是线索

2.建立(线索化)线索二叉树

才用递归的方法，以中序为例，先处理左子，再处理当前结点，最后处理右子即可

需要添加辅助指针pre:指向当前访问的指针p的前驱（逻辑前驱）

//不带头结点
void inThreading(p){
    if(p){//p就是根结点，不空
        inThreading(p->lchild);//处理左子
        //处理当前结点
        if(左子空){
            p->LTag = Thread;
            p->lchild = pre;//前驱
        }
        if(右子空){
            p->RTag =Thread;//标记为无右孩子
        }
        if(pre&&pre->RTag == Thread){pre不空且没有右孩子(pre是当前的前驱)
            pre->rchild = p;
        }
        pre = p;//我自己就是自己的前驱
        inThreading(p->rchild);//处理右子
    }
}

3.遍历线索二叉树

中序不需要栈，先序和后序需要栈

以中序为例，先找到第一个结点，然后判断其是否有右子树，若无，则访问其线索指向的地址(当前的后继)，如果有右子树，则让p = p->rchild继续按中序遍历

//有头结点
while(树不空){
    while(左有子树){
        p = p->lchild;//一直沿着左链走，找到第一个没有左子的结点p
        访问一下p 
        while(p->rchild == Thread&& != T) p = p->rchild并访问p的后继结点
        否则(p有右子树)：p = p->rchild;//成为新的根结点
    }
}

六、树和森林的表示方法

1.双亲表示法

typedef struct PTNode{
    Elem data;
    int parent;//双亲位置域，-1则为根
}PTNode;

2.孩子链表法

在双亲链表的基础上，增加一个指针域，来依次存放该结点的孩子结点(深度为一)

3.左孩子右兄弟表示法

• firstchild:存放其左边的结点

• nextsibling：同级左结点的全部兄弟结点

typedef struct CSNode{
    Elem data;
    struct CSNode *firstchild.*nextsibling;
}CSNode.*CSTree;

4.树、森岭与二叉树的转化

a.数和二叉树

树和转化为二叉树

• 在树的每层从左至右在兄弟结点之间添加虚线
• 除左第一个结点，父结点与所有的子结点的连线去掉
• 将原来的实，线左移；将后添的虚线便实线，右移

变化之后的二叉树的根结点没有右子树，左结点还是原来的左结点，所有沿右链往下的结点均是该解结点的兄弟结点

二叉树还原回树

• 将父结点与该左结点的右链间全部添加虚线
• 将所有的右分支的连线全部去掉
• 将虚线相连的结点上移

b.森林与二叉树

森林转化为二叉树

• 先将森林中的每一棵树化为二叉树
• 从最后一颗二叉树开始，每一颗 二叉树的根作为前一颗二叉树根的右子

二叉树还原为森林

• 将二叉树的根右子依次去掉
• 在每一颗二叉树还原回树

七、树和森岭的遍历

1.树的遍历

总体分为先根、后根、和层次遍历

先根：先访问根结点，在访问叶子结点；后根：先访问叶子，再访问根

• 树的先根遍历等价于二叉树的先序遍历

• 树的后根遍历等价于二叉树的中序遍历

森林的遍历

总体分为先序、中序和后序

• 森林的先序 = 二叉的先序
• 森林的中序 = 二叉的中序
• 森林的后序 = 二叉的后序

3.应用

假设存储结构式孩子兄弟链表，来存储一般的树

typedef struct CSNode{
    Elem data;
    struct CSNode *firstchild.*nextsibling;
}CSNode.*CSTree;

a.求树的深度

int TreeDepth(CSTree T){
    if(!T) return 0;
    else{
        h1 = TreeDepth(T->firstchild);
        h2 = TreeDepth(T->nextsibling);
        return (max(h1+1,h2));
    }
}

b.输出树中所有从根到叶子的路径

基本原理：

若不空：一直沿着左链走进栈，直到左子是空。判断有没有右

左空：代表是叶子结点，打印路径，并出栈

左空，没有右子树：退回到上一结点

左空，有右子树：将右子树入栈，再判断

//使用栈
void ALLPath(Bitree T,stack &S){
    if(T){
        //进栈；
        if(!T->lchild) //打印栈的元素(栈底到栈顶)
        else{
            ALLPath(T->lchild,S);
            ALLPath(T->rchild,S);
        }
        //出栈
    }
}

八、哈夫曼树

1.相关概念

• 结点路径：树中一个结点到另一个结点之间的分支构成的路径eg:AEF
• 路径长度：结点路径上的分支树
• 树的路径长度：根结点到每一个叶子的路径长度的和
• 结点的带权路径长度：根结点到结点之间的路劲长度于结点权值的乘积
• 树的带权路径长度：根到每一个叶子的带权路径长度的和

哈夫曼(Huffman)树,一颗带权路径长度最小的二叉树(最优树)，没有度为1的结点

2.哈夫曼树的构造

简单的几个规定：权小左，权大右，权值相等浅为左

n个叶子，总结点 2n - 1(n + (n - 1))个

构造方法

• 从n个里面找最小的两个，合并成一颗二叉树，
• 其根结点的权值 = 两个小叶子权值的和
• 去除这两个小结点
• 新根作为新结点
• 直到只剩下一个结点

推荐使用静态链表来实现

静态链表

//获取两个最小值
int *Select(HuffmanTree HT,int n){
	int s1,s2;////最小值与极小值 
	int mmin =  Max_S;//先等于无穷大 
	int min = Max_S;
    for(int i = 1;i <= n;i++){
        if(HT[i].parent != 0) continue;//双亲不为零代表已经构成新树，应去除
        else{
            if(mmin >= HT[i].weight){//最小的
                min = mmin ;
                s2 = s1;
                mmin = HT[i].weight;
                s1 = i;
            }else if(min >= HT[i].weight){//次小的 
                min = HT[i].weight;
                s2 = i; 
            }
        }
    }
    //若最小值相等，则浅(先遍历的)树的序号在前 
    int S1 = qiushendu(HT,s1);
    int S2 = qiushendu(HT,s2);
    if(S1 >= S2){
    	int temp;
    	temp = s1; s1 = s2; s2 = temp;//交换顺序 
	}
	//用数组存放最小值和次小值 
    int a[3] = {0,s1,s2};
    return a;
}

//构建哈夫曼树 
void CreatHuffmanTree(HuffmanTree &HT,char *huf,int *wei,int n){
    int s1,s2;//最小值与极小值 
    if(n <= 1){
        cout << "抱歉，您输入的结点数不符合逻辑";
        return;
    }
    int m = 2*n-1;//总结点树
    HT = new HTNode[m+1];//放弃下标为零的数组
    //先遍历前n个数,初始化
    for(int i = 1;i <= m;i++){//全部初始化为零
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
  
	//赋结点、权值 
    for(int i;i <= n;i++){
    	HT[i].data = huf[i];//结点 
    	HT[i].weight = wei[(int)huf[i]];//权值 
    
	}
    //遍历后n+1个，新根
    for(int i = n+1;i <= m;i++){
        //找出最小额两个结点
        int *a;//获取s1和s2 
		a = Select(HT,i-1);//在n个数中找
		s1 = a[1]; s2 = a[2];
        //更新各个数值
        HT[s1].parent = i;
        HT[s2].parent = i;   
        HT[i].lchild = s1;
        HT[i].rchild = s2; 
        HT[i].weight =  HT[s1].weight + HT[s2].weight;  
    }

3.哈夫曼编码

1.引入

为提高传输速度，要求编码尽可能短，还要保证任意字符的编码都不是另一个字符编码的前缀，即前缀编码。Huffman树可以用来构造长度不等且不产生二义性的编码。

那该怎么解析(译码)呢？

从根结点出发走一条从跟到叶子的路径过程(遇0向左，遇1向右)，达到叶子结点就译出一个字符，直至译码完成

2.哈夫曼的构造

基本思想：概率大的字符用短码，小的用长码，构造哈夫曼树，像下图那样(权值即频率)

3.相关结论

• 哈夫曼编码是不等长的编码
• 哈夫曼树，没有度为一的结点
• 发送：根据哈夫曼树得到的编码表送出字符数据
• 接收：按左0右1的规定，从根到叶子的遍历