第六章—树树的基本内容二叉树赫夫曼树和赫夫曼编码

树的基本内容

树的定义

树是一种非线性的数据结构，要理解树的概念及其术语的含义，用一个例子说明最好，下图是一个树，它是若干结点的集合，是由唯一的根（结点A）和若干棵互不相交的子树组成的，其中每一棵子树又是一棵树，也是由唯一的根结点和若干棵互不相交的子树组成的，要注意的是，树的结点数目可以为0，当为0时，这棵树称为空树，这是一种特殊情况。

树的基本术语

结点：A、B、C等都是结点，结点不仅包含数据元素，而且包含指向子树的分支。例如：A结点不仅包含数据元素A，而且还包含3个指向子树的指针。

结点的度：结点拥有的子树个数或者分支的个数。例如：A结点有3棵子树，所以A结点的度为3。

树的度：书中各结点度的最大值。如例子中的结点度最大为3，最小为0，所以树的度为3。

叶子结点：又叫作终端结点，指度为0的结点，如F、G、I、J、K、L、M结点都是叶子结点。

非终端结点：又叫作分支结点，指度不为0的结点，如A、B、C、D、E、H结点都是非终端结点。除了根结点之外的非终端结点，也叫做内部结点。

孩子：结点的子树的根，如A结点的孩子为B、C、D。

双亲：与孩子的定义对应，如B、C、D结点的双亲都是A。

兄弟：同一双亲的孩子之间互为兄弟。如B、C、D互为兄弟。

祖先：从根到某结点的路径上的所有结点，都是这个结点的祖先。如K的祖先是A、B、E。因为从A到K的路径为A—B—E—K。

子孙：以某结点为根的子树中的所有结点，都是该节点的子孙，如D的子孙是H、I、J、M。

层次：从根开始，根为第一层，根的孩子为第二层，根的孩子的孩子为第三层。

树的高度：树中结点的最大层次。如上例中树共4层，所以高度为4。

结点的深度和高度：

1. 结点的深度是从根节点到该结点路径上的结点个数。
2. 从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径上的结点个数即为该结点在树中的高度，如结点D的高度为3，就是从D到M的路径上的结点个数。
3. 根结点的高度为树的高度，如结点A，其高度为4，是从A到K这条路径上结点的个数，也是整棵树的高度。

堂兄弟：双亲在同一层的结点互为堂兄弟。如G和H互为堂兄弟，因为G的双亲是C，H是双亲是D，C和D在同一层上。

有序树：树中结点的子树从左到右是有次序的，不能交换，这样的树叫做有序树。

无序树：树中结点的子树没有顺序，可以任意交换，这样的树叫做无序树。

丰满树：丰满树即理想平衡树，要求除了最底层外，其它层都是满的。

森林：若干棵互不相交的树的集合，例子中如果把根A去掉，剩下的3棵互不相交，它们组成一个森林。

树的存储结构

顺序存储结构

树的顺序存储结构最简单直观的是双亲存储结构，用一维数组即可实现。下面用一个例子来说明一个数组如何表示一个树。

结点元素	0	1	2	3	4	5	6	7
双亲结点		-1	1	1	1	3	3	3

用数组下标表示树中的结点，数组元素的内容表示该结点的双亲节点，这样有了结点（下标）以及结点之间的关系（内容），就可以表示一棵树。

链式存储结构

1. 孩子存储结构：需要用到图的邻接表存储结构，树就是一种特殊的图。把图中的多对多关系删减为一对多关系即变为树。
2. 孩子兄弟存储结构

二叉树

二叉树的定义

将一般的树加上如下两个限制条件就得到了二叉树。

1. 每个结点最多只有两个子树，即二叉树中结点的度只能为0、1、2。
2. 子树有左右顺序之分，不能颠倒。

根据二叉树的定义，可以知道二叉树共有5种基本的形态.

1. 空二叉树
2. 只有根结点
3. 只有左子树
4. 只有右子树
5. 左右子树都有

在一棵二叉树中，如果所有的分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下一层，则这样的二叉树为满二叉树。

对满二叉树进行编号，约定从1开始，从上到下，自左到右进行，如果对一棵深度为k、有n个结点的二叉树进行编号后，各结点的编号与深度为k的满二叉树中相同位置上的结点的编号均相同，那么这棵二叉树就是一个完全二叉树。

在下图中，结点F用虚线画出。如果F存在于下图的二叉树结点，则F的编号为6，与上图的满二叉树同一位置上的结点G的编号7不同，此时就不是完全二叉树，如果F存在下图的二叉树中，此时就是完全二叉树。

空表示没有该结点，为了将F画到右边，才加这个。

二叉树的主要性质

性质1：非空二叉树上叶子结点数等于双分支结点数加1。

性质2：二叉树的第i层上最多有 $2^{i-1}$个结点。

性质3：高度为k的二叉树最多有$2^k-1$个结点。

性质4：有n个结点的完全二叉树，对各结点从上到下，从左到右依次编号，则结点有如下关系，若i为某结点a的编号，则

1. 如果$i\ne 1$，则a双亲结点的编号为$\lfloor i/2\rfloor$。
2. 如果$2i\le n$，则a左孩子的编号为$2i$；如果$2i>n$，则a无左孩子。
3. 如果$2i+1\le n$，则a右孩子的编号为$2i+1$；如果$2i+1>n$，则a无右孩子。

性质5：函数Catalan()：给定n个结点，能构成h(n)种不同的二叉树。$h(n)=\frac{C_{2n}^n}{n+1}$。

性质6：具有n个结点的完全二叉树的高度为$\lfloor lo{g}_{2}n\rfloor +1$。

二叉树的存储结构

顺序存储结构

顺序存储结构是用一个数组来存储一棵二叉树，这种存储方式最适合于完全二叉树，用于存储一般二叉树会浪费大量的存储空间。将完全二叉树中的结点值按编号依次存入一个一维数组中，即完成了一棵二叉树的顺序存储。例如：知道了顶点A的下标为1，要得到A的左孩子结点只需访问数组中[1*2]即可。

链式存储结构

typedef struct BTNode{
    char data;
    struct BTNode* lchild;
    struct BTNode* rchild;
}BTNode;

二叉树的遍历算法

先序遍历

先序遍历的操作过程如下：如果二叉树为空树，则什么都不做，否则：

1. 访问根结点
2. 先序遍历左子树
3. 先序遍历右子树

void preprder(BTNode* p){
    if(p!= nullptr){
        printf("%c",p->data);
        preprder(p->lchild);
        preprder(p->rchild);
    }
}

中序遍历

中序遍历的操作过程如下：如果二叉树为空树，则什么都不做，否则：

1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树

void inorder(BTNode* p){
    if(p!= nullptr){
        inorder(p->lchild);
        printf("%c",p->data);
        inorder(p->rchild);
    }
}

后序遍历

后序遍历的操作过程如下：如果二叉树为空树，则什么都不做，否则：

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根结点

void postorder(BTNode* p){
    if(p!= nullptr){
        postorder(p->lchild);
        postorder(p->rchild);
        printf("%c",p->data);
    }
}

例：表达式$a+(b+c)\ast (d/e)$存储在下图的一棵以二叉链表为存储结构的二叉树中（二叉树结点为char类型），编写程序求出该值。（表达式中的操作数是一位的整数）

左子树为表达式A，右子树为表达式B，先求左子树所表示的表达式的值，然后求右子树所表示的表达式的值，最后将两个式子想乘即可。这正好对应先遍历左子树，再遍历右子树，最后访问根结点的后序遍历，因此采用后序遍历解决此问题。

int comp(BTNode *p){
    int A,B;
    if(p!= nullptr){
        if(p->lchild!= nullptr && p->rchild!= nullptr){
            A = comp(p->lchild);
            B = comp(p->rchild);
            return op(A,p->data,B);
        } else{
            return p->data - '0';
        }
    }else{
        return 0;
    }
}

int op(int a,char Op,int b){
    if(Op == '+'){
        return a+b;
    }
    if(Op == '-'){
        return a-b;
    }
    if(Op == '*'){
        return a*b;
    }
    if(Op == '/'){
        if(b == 0){
            printf("Error");
            return 0;
        }else{
            return a/b;
        }
    }
    return 0;
}

例：写一个算法求一棵二叉树的深度，二叉树以二叉链表为存储方式。

分析：假如已知一棵二叉树的左子树和右子树的深度，如何计算整棵树的深度？这是问题的关键。如果有一个二叉树，左子树深度为LD，右子树深度为RD，则整棵树的深度就是max{LD,RD}+1，即左子树和右子树深度的最大值加1，因此这个求深度的过程实际上就是先求左子树深度，再求右子树深度，然后返回两者之中的最大值加1就是整棵树的深度。这正对应于先遍历左子树（得到左子树的深度LD），再遍历右子树（得到右子树的深度RD），最后访问根结点（得到整棵树的深度）。

int getDepth(BTNode *p){
    int LD,RD;
    if(p == nullptr){
        return 0; //如果树是空树，则返回0
    }else{
        LD = getDepth(p->lchild);
        RD = getDepth(p->rchild);
        return (LD > RD ? LD:RD) + 1;
    }
}

例：在一棵以二叉链表为存储结构的二叉树中，查找data域值等于key的结点是否存在（找到任何一个满足要求的结点），如果存在，则将q指向该结点，否则q赋值为NULL，假设data为char型。

分析：因为题中二叉树各个结点data域的值没有任何规律，所以要判断是否存在data域值等于key的结点，必须按照某种方式把所有结点访问一遍，逐一进行判断其值是否为key。

void search(BTNode *p,BTNode *&q,char key){
    if(p!= nullptr){
        if(p->data == key){
            q = p;
        }else{
            search(p->lchild,q,key);
            search(p->rchild,q,key);
        }
    }
}

例：假设二叉树采用二叉链表存储结构存储，编写一个程序，输出先序遍历序列中第k个结点的值，假设k不大于总的结点数（结点data类型为char）。

分析：题目要求输出先序遍历序列中的第k个结点的值，只需要修改先序遍历的模板即可。

int m = 0; //必须定义为全局变量,记录数量
void trave(BTNode* p,int k){
    if(p!= nullptr){
        ++m;
        if(k==m){
            printf("%c",p->data);
            return;
        }
        trave(p->lchild,k);
        trave(p->rchild,k);
    }
}

层次遍历

按照从左向右的顺序，依次对每层的树结点进行遍历。

要进行层次遍历，需要建立一个循环队列。先将二叉树头结点入队列，然后出队列，访问该结点，如果它有左子树，则将左子树的根结点入队，如果它有右子树，则将右子树的根结点入队。然后出队列，对出队结点访问，如此反复，直到队列为止。

void level(BTNode *p){
   int front,rear;
   BTNode *que[maxSize];
   front = rear = 0;
   BTNode *q;
   if(p!= nullptr){
       rear = (rear+1)%maxSize;
       que[rear] = p; //根结点入队
       while(front != rear){ //当队列不空时循环
           front = (front+1)%maxSize;
           q = que[front]; //队头结点出队
           printf("%c",q->data); //访问队头结点
           if(q->lchild != nullptr){ //如果左子树不空，则左子树根结点入队。
               rear = (rear+1)%maxSize;
               que[rear] = q->lchild;
           }
           if(q->rchild != nullptr){ //如果右子树不空，则右树根结点入队。
               rear = (rear+1)%maxSize;
               que[rear] = q->rchild;
           }
       }
   }
}

例：假设二叉树采用二叉链表存储结构存储，设计一个算法，求该二叉树的宽度（具有结点数最多的那一层结点的个数）

分析：要求含有最多结点数的层上的结点数，可以分别求出每层的结点数，然后求出最多的，要达到这个目的，必须明确两点。

1. 对于非空树，树根所在的层为第一层，并且从层次遍历算法的程序中可以发现，有一个由当前结点找到左、右孩子结点的操作。这就提示到如果知道当前结点的层号，就可以推导出左、右孩子的层号，即为当前结点层号加1，进而可以求出所有结点的层号。
2. 在层次遍历中，用到了循环队列（队列用数组描述），其出队和入队操作为front=(front+1)%maxSize;和rear=(rear+1)%maxSize;，如果用来存储队列的数组足够长，可以容纳树中所有结点。这时在整个便利操作中队头和队尾指针不会出现折回数组起始位置的情况，那么front=(front+1)%maxSize;，可以用++front;代替，rear=(rear+1)%maxSize可以用++rear;代替。出队操作只是队头指针front后移一位，但是并没有删除掉队头元素，在数组足够长的情况下，队头元素也不会被入队的元素覆盖。

typedef struct {
    BTNode *p; //结点指针
    int lno; //结点所在层次号
}St;

int maxNode(BTNode *b){
    St que[maxSize];
    int front,rear; //定义顺序非循环队列
    int Lno = 1,i,j,n,max = 0;
    front = rear = 0; //将队列置空
    BTNode *q;
    if(b != nullptr){
        ++rear;
        que[rear].p = b; //树根入队
        que[rear].lno = 1;//树根所在层次号设置为1。
        while (front != rear){
            ++front;
            q = que[front].p;
            Lno = que[front].lno; //Lno用来存取当前结点的层次号
            if(q->lchild != nullptr){
                ++rear;
                que[rear].p = q->lchild;
                que[rear].lno = Lno + 1; //根据当前结点的层次号推知其孩子结点的层次号
            }
            if(q->rchild != nullptr){
                ++rear;
                que[rear].p = q->rchild;
                que[rear].lno = Lno + 1; //根据当前结点的层次号推知其孩子结点的层次号
            }
        }
        /****根据que数组中的lno计数并求出最大值******/
        for (i = 1; i <= Lno; ++i) {
            n = 0;
            for (j = 0; j < rear; ++j) {
                if(que[j].lno == i){
                    ++n;
                }
                if(max<n){
                    max = n;
                }
            }
        }
        return max;
    }else{
        return 0; //空树直接返回0
    }
}

二叉树遍历算法的改进

二叉树的原始遍历方式都是用递归函数实现的，这是非常低效的。原因在于系统帮助调用一个栈并做了诸如保护现场和恢复现场等复杂的操作，才使得遍历可以非常简洁的代码实现。那么使用二叉树深度优先遍历的非递归实现和线索二叉树方式实现，第一种算法用用户定义的栈来接替系统栈，也就是使用非递归的方式实现，可以得到不小的效率提升。第二种算法将二叉树线索化，不需要栈来辅助完成，更进一步提升了效率。

二叉树深度优先遍历算法的非递归实现

用实例进行分析，假设二叉树如下：

先序遍历非递归算法

要写出非递归算法，首先要用自己定义的栈来代替栈的功能。栈在遍历过程中主要做的事情。

1. 初始栈空。
2. 结点1入栈。
3. 出栈，输出栈顶结点1。并且将1的左、右孩子（2和4）入栈，右孩子先入栈，左孩子后入栈，因为对左孩子的访问要先于右孩子，后入栈的会先出栈访问。
4. 出栈，输出栈顶结点2，并将2的左、右孩子结点（3和5）入栈。
5. 出栈，输出栈顶结点3，3为叶子结点，无孩子，本步无结点入栈。
6. 出栈，输出栈顶结点5。
7. 出栈，输出栈顶结点4，此时栈空，进入终态。

所以遍历顺序为1,2,3,5,4。

void preorderNonrecursion(BTNode *bt){
    if(bt != nullptr){
        BTNode *stack[maxSize];
        int top = -1;
        BTNode *p;
        stack[++top] = bt;
        while(top != -1){
            p = stack[top--]; //出栈并输出栈顶结点
            printf("%c",p->data);
            if(p->rchild != nullptr){ //栈顶结点的右孩子存在，则右孩子入栈
                stack[++top] = p->rchild;
            }
            if(p->lchild != nullptr){ //栈顶结点的左孩子存在，则左孩子入栈
                stack[++top] = p->lchild;
            }
        }
    }
}

中序遍历非递归算法

类似于先序遍历，对二叉树进行中序遍历。各个结点入栈、出栈过程如下：

1. 初始栈空。
2. 结点1入栈，1左孩子存在。
3. 结点2入栈，2左孩子存在。
4. 结点3入栈，3左孩子不存在。
5. 出栈，输出栈顶结点3，3右孩子不存在。
6. 出栈，输出栈顶结点2，2右孩子存在，右孩子5入栈，5左孩子不存在。
7. 出栈，输出栈顶结点5，5右孩子不存在。
8. 出栈，输出栈顶结点1，1右孩子存在，右孩子4入栈，4左孩子不存在。
9. 输出栈顶结点4，此时栈空，进入终态。

遍历结果：3，2，5，1，4。

由此可以看出，中序遍历过程如下：

1. 开始根结点入栈。
2. 循环执行如下操作：如果栈顶结点左孩子存在，则左孩子入栈；如果栈顶结点左孩子不存在，则出栈并输出栈顶结点，然后检查其右孩子是否存在，如果存在，则右孩子入栈。
3. 当栈空时算法结束。

void inorderNonrecursion(BTNode *bt){
    if(bt != nullptr){
        BTNode *stack[maxSize];
        int top = -1;
        BTNode *p;
        p = bt;
        while(top != -1 || p != nullptr){
            while (p != nullptr){ //左孩子存在，则左孩子入栈
                stack[++top] = p;
                p = p->lchild;
            }
            if(top != -1){ //在站不空的情况下出栈并输出栈结点
                p = stack[top--];
                printf("%c",p->data); //访问结点
                p = p->rchild;
            }
        }
    }
}

后序遍历非递归算法

例子中的二叉树的先序遍历和后序遍历。

先序遍历：1，2，3，5，4

后序遍历：3，5，2，4，1

把后序遍历逆序一次得到：1，4，2，5，3

逆序逆后序遍历：3，5，2，4，1

观察后发现，逆序遍历和先序遍历具有一定的联系。逆后序遍历序列只不过是先序遍历过程对左右子树遍历顺序交换所得到的结果。（先序遍历是先序遍历根结点，先序遍历左子树，先序遍历右子树；逆后序遍历是将先序中左右的遍历进行交换）

因此，只需要将非递归先序遍历算法对左右子树的遍历顺序交换就可以得到逆后序遍历序列，然后对逆后序遍历逆序就得到后序遍历。因此需要两个栈，一个栈stack1用来辅助做逆后序遍历，并将遍历结果序列压入另一个栈stack2，然后将stack2中的元素全部出栈，所得到的就是后序遍历序列。

void postorderNonrecursion(BTNode *bt){
    if(bt != nullptr){
        BTNode *stack1[maxSize];
        int top1 = -1;
        BTNode *stack2[maxSize];
        int top2 = -1;
        BTNode *p = nullptr;
        stack1[++top1] = bt;
        while(top1 != -1){
            p = stack1[top1--];
            stack2[++top2] = p;
            /*注意这里和先序遍历的区别。左右孩子入栈顺序相反*/
            if(p->lchild != nullptr){
                stack1[++top1] = p->lchild;
            }
            if(p->rchild != nullptr){
                stack1[++top1] = p->rchild;
            }
        }
        while (top2 != -1){
            p = stack2[top2--]; //出栈后即为后序遍历
            printf("%c",p->data);
        }
    }
}

注意：遍历的空间复杂度很高，但是不需要考虑。因为研究的是数据结构，不需要对算法空间复杂度有特别的要求。

线索二叉树

二叉树非递归遍历算法避免了系统栈的调用，提高了一定的执行能力。但是降低了空间复杂度，那么使用线索二叉树避免了创建用户栈，将二叉树的遍历过程线性化，进一步提高效率。（不一定可以降低空间复杂度，但是线性化一定可以提高效率）

对于二叉链表存储结构，n个结点有n+1个空链域，所以将这些空链域利用起来，可以让二叉树的遍历更为高效，在一般的二叉树中，只知道某个结点的左孩子、右孩子，并不能知道某个结点在某种遍历方式中的直接前驱和直接后继，如果能够知道前驱和后继，就可以把二叉树当做一个链表的结构，从而可以像遍历链表一样遍历二叉树，进而提高效率。

线索二叉树结点的构造：在二叉树线索化过程会把树中的空指针利用起来作为寻找当前结点前驱或后继的线索，这样就出现了一个问题，即线索和树中原有指向孩子的结点的指针无法区分，所以必须有2个标识域，它们的具体的意义如下：

1. 如果ltag=0，则表示lchild为指针，指向结点的左孩子；如果ltag=1，则表示lchild为线索，指向结点的直接前驱。
2. 如果rtag=0，则表示rchild为指针，指向结点的右孩子；如果rtag=1，则表示rchild为线索，指向结点的直接前驱。

typedef struct TBTNode{
    char data;
    int ltag,rtag; //线索标记
    struct TBTNode *lchild;
    struct TBTNode *rchild;
}TBTNode;

线索二叉树可以分为前序线索二叉树、中序线索二叉树和后序线索二叉树。对一棵二叉树中所有结点的空指针域按照某种遍历方式加线索的过程叫做线索化，被线索化了的二叉树称为线索二叉树。

说明：中序线索二叉树用的最多，前序次之，后序最少。因此重点介绍中序线索二叉树。

二叉树中序线索化分析：

1. 既然要对二叉树进行中序线索化，首先要有个中序遍历的框架，这里采用二叉树中序遍历算法，在遍历过程中连接上合适的线索即可。
2. 线索化的规则是，左线索指针指向当前结点在中序遍历序列中的前驱结点，右线索指针指向后继结点，因此需要一个指针p指向当前正在访问的结点，pre指向p的前驱结点，p的左线索如果存在则让其指向pre，pre的右线索如果存在则让其指向p，因为p是pre的后继结点，这样就完成了一对线索的连接。
3. 上一步中保持pre始终指向p前驱的具体过程是，当p将要离开一个访问过的结点时，pre指向p；当p来到一个新结点时，pre显然指向的是此时p所指结点的前驱结点。

空表示没有该结点，为了画出完整图才加这个。

如图：某一时刻p指向A，pre指向了中序遍历过程中A的前驱结点D，A是D的后继，D的右线索指向A。

void InThread(TBTNode *p,TBTNode *&pre){
    if(p != nullptr){
        InThread(p->lchild,pre); //递归，左子树线索化
        if(p->lchild == nullptr){ //建立当前结点的前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre!= nullptr&&pre->rchild== nullptr){ //建立前驱结点的后继结点
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p; //pre指向当前的p，作为p将要指向的下一个结点的前驱结点指示指针
        p = p->rchild; //p指向一个新结点，此时pre和p分别指向的结点形成了一个前驱后继，为下一次线索化做准备
        InThread(p,pre); //递归，右子树线索化
    }
}

上一段代码中的如下3句：

pre = p;
p = p->rchild;
InThread(p,pre);

可以这样写：

pre = p;
InThread(p->rchild,pre);

通过中序遍历创建线索二叉树的主程序如下：

void createInThread(TBTNode *root){
    TBTNode *pre = nullptr; //前驱结点指针
    if(root != nullptr){
        InThread(root,pre);
        pre->rchild = nullptr; //非空二叉树，线索化
        pre->rtag = 1; //处理中序最后一个结点
    }
}

求以p为跟的中序线索二叉树中，中序序列下的第一个结点的算法如下：

TBTNode* First(TBTNode *p){
    while (p->ltag == 0){
        p = p->lchild; //最左下结点（不一定是叶结点）
    }
    return p;
}

求在中序线索二叉树中，结点p在中序下的后继结点的算法如下：

TBTNode* Next(TBTNode *p){
    if(p->rtag == 0){
        return First(p->rchild);
    }else{
        return p->rchild; //rtag == -1,直接返回后继线索
    }
}

如果把程序中First()的ltag和lchild换成rtag和rchild，同时把函数名First()换成Last()，即可得到求中序序列下最后一个节点的函数Last()；如果把程序中Next()的rtag和rchild换成ltag和rchild，并同时把函数First()换成Last()，再把函数名Next()改成Prior()则可得到求中序序列下前驱结点的函数Prior()。

遍历中序线索二叉树：

void InThreadOrder(TBTNode* root){
    for(TBTNode *p = First(root) ; p != nullptr ; p = Next(p)){
        printf("%c",p->data);
    }
}

前序线索二叉树

void preThread(TBTNode *p,TBTNode *&pre){
    if(p != nullptr){
        if(p->lchild == nullptr){
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre != nullptr && pre->rchild == nullptr){
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        /* 注意：这里在递归入口处有限制条件，左、右指针不是线索才继续递归 */
        if(p->ltag == 0){
            preThread(p->lchild,pre);
        }
        if(p->rtag == 0){
            preThread(p->rchild,pre);
        }
    }
}

后序线索二叉树

void postThread(TBTNode* p,TBTNode *&pre){
    if(p != nullptr){
        postThread(p->lchild,pre);
        postThread(p->rchild,pre);
        if(p->lchild == nullptr){ //建立当前结点的前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre != nullptr && pre->rchild == nullptr){ //建立前驱线索的后继线索
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
    }
}

树和森林与二叉树的相互转换

树转换成二叉树

前边提到的树的孩子兄弟存储结构是基于二叉链表实现的，即以二叉链表作为树的存储结构，只是结点中的指针域表示的意义不同，对比如下：

1. 用二叉链表存储二叉树，结点中一个指针域叫做lchild，指向左孩子，另一个指针域叫做rchild，指向右孩子。
2. 用二叉链表存储树，结点中一个指针（假设为child）指向一个孩子，另一个指针（假设为sibling）指向自己的兄弟结点。

孩子兄弟存储结构实质上是一个二叉链表，用它来存储二叉树是最直接方便的，把一棵树也能方便的转换为孩子兄弟存储结构的过程如下：

1. 将同一个结点的各孩子用线串起来。
2. 将每个结点的分支从左往右除了第一个以外，其余的都减掉。
3. 调整结点使之符合二叉树的层次结构。

空表示没有该结点，为了画出完整图才加这个。

二叉树转化为树

将树转换为二叉树的步骤逆置，就可以得到二叉树转换为树的步骤：

1. 一棵二叉树，先把它从左上到右下分为若干层。
2. 找到每一层结点在其上一层的父结点。
3. 将每一层的结点和其父结点相连，然后删除每一层结点之间的连接。即可得到树。

总结：左孩子是一个子结点，右孩子是其兄弟结点。

森林转换为二叉树

将森林转换为树可以看作为树转化为二叉树的扩展，只不过是由原来的一棵树的转换扩展为多棵树的转换，要注意一点，要求是将森林转化为一棵二叉树，因此将森林中的每棵树分别转化后得到的多棵二叉树应该按照一定的规则连接成一棵二叉树，根据孩子兄弟表示的法则，由于树的根结点一定是没有右孩子的，因此转换为二叉树后，根结点一定是没有右孩子的，那么可以将根结点这个空出来的右结点指针利用起来，即将森林中第二课树转换为二叉树，当做第一棵树根的右子树即可，将森林中的第三棵树转换成的二叉树，当做第二课二叉树的右子树，依次进行，最终森林就转换成了一棵二叉树。

下面说明森林转化二叉树的过程：

1. 先将森林中所有的树转换为二叉树。
2. 然后将第2棵二叉树作为第1棵二叉树根结点的右子树，第3棵二叉树作为第2棵二叉树根结点的右子树，以此类推。

二叉树转换为森林

掌握了森林如何转换为二叉树，那么将二叉树转换为森林，只需要不停地将根结点有右孩子的二叉树的右孩子连接断开，直到不存在根结点有右孩子的二叉树为止，然后将得到的多棵二叉树按照二叉树转换为树的规则依次转化即可。

树和森林的遍历

树的遍历

树的遍历有2种方式：先序遍历和后序遍历。先序遍历是先访问根结点，再依次访问根结点的每棵子树，访问子树时仍然遵循先根再子树的规则；后序遍历是先访问根结点的每棵子树，再访问根结点，访问子树时仍然遵循先子树再根的规则。

使用下图的例子，写出其中的先序和后序遍历。

先序遍历

1. 访问根结点A。
2. 访问A的第一棵子树，访问子树时先访问根结点B。
3. 访问B的第一个孩子E。
4. 访问B的第二个孩子F。
5. 访问A的第二棵子树，访问子树时先访问根结点C。
6. 访问C的第一个孩子G。
7. 访问A的第三棵子树，访问子树时先访问根结点D。
8. 访问D的第一个孩子H。
9. 访问D的第二个孩子I。
10. 访问D的第三个孩子J。

先序遍历的结果为ABEFCGDHIJ。

后序遍历

1. 访问根结点A的第一棵子树，访问子树时先访问根B的第一个孩子E。
2. 访问B的第二个孩子F。
3. 访问B。
4. 访问A的第二棵子树，访问子树时先访问根C第一个孩子G。
5. 访问C。
6. 访问A的第三棵子树，访问子树时先访问D的第一个孩子H。
7. 访问D的第二个孩子I。
8. 访问D的第三个孩子J。
9. 访问D。
10. 最后访问根结点A。

后序遍历的结果：EFBGCHIJDA。

森林的遍历

森林的遍历方式有两种：先序遍历和后序遍历。

先序遍历的过程：先访问森林中的第一棵的根结点，然后先序遍历第一棵树中根结点的子树，最后先序遍历森林中除了第一棵树以外的其他树。

后序遍历的过程：后序遍历第一棵树中根结点的子树，然后访问第一棵树的根结点，最后后序遍历森林中出去第一棵树以后的森林。

森林转换为二叉树中，森林的先序遍历对应二叉树的先序遍历，森林的后序遍历对应二叉树的中序遍历。

赫夫曼树和赫夫曼编码

与赫夫曼树有关的概念

赫夫曼树又叫作最优二叉树，它的特点是带权路径最短。首先需要说明几点概念。

1. 路径：路径是指从树中一个结点到另一个结点的分支所构成的路线。
2. 路径长度：是指路径上的分支数目。
3. 树的路径长度：是指从根到每个结点的路径长度之和。
4. 带权路径长度：结点具有权值，从该结点到根之间的路径长度乘以结点的权值，就是该结点的带权路径的长度。
5. 树的带权路径长度（WPL）：是指树中所有叶子结点的带权路径长度之和。

空表示没有该结点，为了画出完整图才加这个。

用例子说明上述概念，4个叶子结点分别为a，b，c，d的权值分别为7、5、2、4。因为a到根结点的分支数目为2，所以a的路径长度为2，a的带权路径长度为$7\times 2=14$。同样，b、c、d的带权路径长度分别为$5\times 2=10$，$3\times 2=6$，$4\times 2=8$。于是这棵二叉树的带权路径长度为$WPL=14+10+6+8=38$

赫夫曼树的构造原理

给定n个权值，用这n个权值来构造赫夫曼树的算法描述如下：

1. 将这n个权值分别看自作只有根结点的n棵二叉树，这些二叉树构成的集合记为F。
2. 从F中选出两棵根结点的权值最小的树（假设为a、b）作为左、右子树，构造一棵新的二叉树（假设为c），新的二叉树的根结点的权值为左、右子树根结点权值之和。
3. 从F中删除a、b，加入新构造的树c。
4. 重复进行第2、3步，直到F中只剩下一棵树为止，这棵树就是赫夫曼树。

下面通过一个实例说明赫夫曼树的构造过程。a，b，c，d的权值依次为7，5，2，4。

1. 现将a、b、c、d看作只有4棵二叉树。
2. 选出权值最小的两个根c和d，即权值为5和6的两个根结点，将它们作为左、右子树。构造成一个新的二叉树，新的二叉树的根结点权值为$5+6=11$，删除根权值为5和6的两棵树，同时将新构造的二叉树加入集合中。
3. 继续选择权值最小的两个根，即权值为7和11的两个根，将它们作为左、右子树，构造出一个新的二叉树。新的二叉树的根结点权值为$7+11=18$。删除根权值为7和11的两棵树，同时将新构造的二叉树加入集合中。
4. 此时，集合中就剩下一棵二叉树，这棵树就是赫夫曼树，计算其$WPL=7\times 1+5\times 2+2\times 3+4\times 3=35$。在以a、b、c、d这4个结点为叶子结点的所有二叉树中，赫夫曼树的WPL是最小的。

赫夫曼树的特点：

1. 权值越大的结点，距离根越近。
2. 树中没有度为1的结点，这类树叫作正则二叉树。
3. 树的带权路径长度最短。

赫夫曼编码

赫夫曼编码的主要作用是压缩文件。所以用字符串压缩来对赫夫曼编码进行详细分析，假设字符串如下：S=AAABBACCCDEEA，选三位长度的二进制为各个字符编码（二进制数位数随意，只要能够编码所有不同的字符即可），编码规则如下：

A	B	C	D	E
000	001	010	011	100

T(S)=000000000001001000010010010011100100000，并将其存储在计算机中。

T(S)长度为39，可以使得串变短一些，且能准确的解码得到字符串。使用哈夫曼编码进行，首先统计一下各个字符在字符串中出现的次数。

A	B	C	D	E
5次	2次	3次	1次	2次

对A~E的赫夫曼编码规则

A	B	C	D	E
0	110	10	1110	1111

以字符为根结点，以访问次数作为权值，构造一个赫夫曼树。

这里空结点是赫夫曼树的构造结点。

扩展：C++语法—引用

引用变量是一个别名，也就是说，它是某个已存在变量的另一个名字。一旦把引用初始化为某个变量，就可以使用该引用名称或变量名称来指向变量。

C++引用和指针的对比， 引用很容易与指针混淆，它们之间有三个主要的不同：

1. 不存在空引用。引用必须连接到一块合法的内存。
2. 旦引用被初始化为一个对象，就不能被指向到另一个对象。指针可以在任何时候指向到另一个对象。
3. 引用必须在创建时被初始化。指针可以在任何时间被初始化。

试想变量名称是变量附属在内存位置中的标签，可以把引用当成是变量附属在内存位置中的第二个标签。因此，您可以通过原始变量名称或引用来访问变量的内容。例如：

int i = 17;

可以为 i 声明引用变量，如下所示：

int &r = i;
double &s = d;

在这些声明中，&是引用。因此，第一个声明为"r 是一个初始化为 i 的整型引用"，第二个声明为"s 是一个初始化为 d 的 double 型引用"。

使用引用作为函数参数

void swap(int &a,int &b){
    int temp;
    temp = a;
    a = b;
    b = temp;
}

引用作为返回值： 当函数返回一个引用时，则返回一个指向返回值的隐式指针。这样，函数就可以放在赋值语句的左边。

最后

以上就是动人小蚂蚁为你收集整理的第六章—树树的基本内容二叉树赫夫曼树和赫夫曼编码的全部内容，希望文章能够帮你解决第六章—树树的基本内容二叉树赫夫曼树和赫夫曼编码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。