6.1 树

6.1.1 树的定义

树(tree)是n(n≥0)个结点的有限集T。如果n=0，则称空树；如果n>0(非空树)，则：

  • 有且仅有一个特定的结点，称为根(root) ；

  • 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。

6.1.2 树的特点

在非空树中至少有一个结点——根，树中各子树是互不相交的集合。

树的特点

6.1.3 相关术语

术语 解释
结点 表示树中的元素，包括数据项及若干指向其子树的分支
结点的度 分支个数 ( 结点拥有的子树个数 )
树的度 树中所有结点的度的最大值
叶子结点 度为零的结点，即无后继的结点，也称为终端结点
分支结点 度大于零的结点，也称为非终端结点
从根到结点的路径 由从根到该结点所经分支和结点构成
结点的层次 一个结点在第n 层，则其子树的根结点在 n+1
树的深度（高度） 树中所有结点的层次的最大值
森林 是 m ( m≥0 ) 棵互不相交的树的集合
有序树 子树之间存在确定的次序关系
无序树 子树之间不存在确定的次序关系
孩子结点 一个结点的直接后继
双亲结点 一个结点的直接前驱
兄弟结点 同一双亲结点的孩子结点之间互称兄弟结点
堂兄弟结点 父亲是兄弟关系或堂兄关系的结点
祖先结点 从根节点到该结点路径上所有结点
子孙结点 一个结点的直接后继和间接后继

树的相关术语

6.2 二叉树

6.2.1 二叉树的定义

二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。

每个结点至多有二棵子树(即不存在度大于2的结点)。二叉树的子树有左、右之分，且其次序不能任意颠倒。

二叉树的基本形态

6.2.2 二叉树的性质

（1）在二叉树的第 i 层上至多有 2i−12^{i-1} 个结点(i≥1i \ge 1) 。

（2）深度为 k 的二叉树上至多含 2k−12^{k-1} (k≥1k \ge 1)个结点。

（3）任何一棵二叉树，若叶子结点个数为 n0 ，度为 2 的结点数为 n2 ，则必存在关系式：n0=n2+1n_0=n_2+1。

（4）具有 n 个结点的完全二叉树的深度为 log2n+1log_2n+1。

（5）若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：有

  • 若 i=1i = 1，则该结点i是二叉树的根，无双亲；如果 i>1i > 1，编号为 i/2i/2 的结点为其双亲结点。
  • 若 2i>n2i > n，则该结点无左孩子，如果 2i<n2i < n，编号为 2i2i 的结点为其左孩子结点。
  • 若 2i+1>n2i+1>n，则该结点无右孩子，如果 2i+1<n2i+1 < n，编号为 2i+12i+1 的结点为其右孩子结点。
  • 若 ii 为奇数且不为 1，则结点i的左兄弟是 i - 1；否则无左兄弟。
  • 若 ii 为偶数且小于 n，则结点i的右兄弟是 i + 1；否则无右兄弟。

6.2.3 满二叉树和完全二叉树

（1）满二叉树

定义：指的是深度为 k 且含有 2k−12^{k-1} 个结点的二叉树。

特点：每一层上的结点数都是最大结点数。

（2）完全二叉树

定义：深度为 k，有 n 个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从 1 至 n 的结点一一对应时，称为完全二叉树。

特点：

  • 叶子结点只可能在层次最大的两层上出现。
  • 对任一结点，若其右分支下子孙的最大层次为 L，则其左分支下子孙的最大层次必为 L 或 L+1。

满二叉树和完全二叉树

6.3 二叉树的存储

6.3.1 顺序存储

按满二叉树的结点层次编号，依次存放二叉树中的数据元素。结点间关系蕴含在其存储位置中，但是浪费空间，适于存满二叉树和完全二叉树。

二叉树顺序存储

6.3.2 链式存储

对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子域。

1
2
3
4
5
typedef struct node{    
    datatype data;
    struct node *lchild, *rchild;
}bitree;

二叉树链式存储

若一个二叉树含有 n 个结点，则它的二叉链表中必含有 2n个指针域，其中必有 n＋1 个空的链域。 有时，为了便于找到双亲结点，可以增加一个Parent域，以指向该结点的双亲结点。采用这种结点结构的存放方式称做二叉树的三叉链表存储结构。

6.4 遍历二叉树

遍历一棵非空二叉树，可分解为：

  1. 访问根结点 D；
  2. 遍历左子树 L；
  3. 遍历右子树 R。

因此有三种遍历方法，分别是：

  1. DLR：先序（根）遍历
  2. LDR：中序（根）遍历
  3. LRD：后序（根）遍历

设二叉树有 nn 个结点，对每个结点都要进行一次入栈和出栈的操作，即入栈和出栈各执行 nn 次，对结点的访问也是 nn 次。这些二叉树递归遍历算法的时间复杂度为 O(n)O(n)。

两种遍历序列的组合 是否能唯一确定二叉树
先序+中序 True
中序+后序 True
先序+后序 False

6.4.1 先序遍历

若二叉树为空，则空操作，否则依次执行如下 3 个操作：

  1. 访问根结点；
  2. 按先序遍历左子树；
  3. 按先序遍历右子树。
1
2
3
4
5
6
7
8
void preorder(bitree *t) {  
    if(t!=NULL) { 
        printf("%d\t",t->data);
        preorder(t->lchild);
        preorder(t->rchild);
    }
}

先序遍历

6.4.2 中序遍历

若二叉树为空，则空操作，否则依次执行如下 3 个操作：

  1. 按中序遍历左子树；
  2. 访问根结点；
  3. 按中序遍历右子树。
1
2
3
4
5
6
7
8
void preorder(bitree *t) {  
    if(t!=NULL) { 
        preorder(t->lchild);
        printf("%d\t",t->data); 
        preorder(t->rchild);
    }
}

中序遍历

6.4.3 后序遍历

若二叉树为空，则空操作，否则依次执行如下 3 个操作：

  1. 按后序遍历左子树；
  2. 按后序遍历右子树；
  3. 访问根结点。
1
2
3
4
5
6
7
void preorder(bitree *t) {  
    if(t!=NULL) { 
          preorder(t->lchild);
        preorder(t->rchild); 
        printf("%d\t",t->data); 
    }
}

后序遍历

6.4.4 示例

遍历示例

6.5 线索二叉树

二叉树的遍历运算是将二叉树中结点按一定规律线性化的过程。当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前驱和后继信息。

要得到这些信息可采用以下两种方法：

  • 将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时间。

  • 充分利用二叉链表中的空链域，将遍历过程中结点的前驱、后继信息保存下来。

这里介绍第二种，也就是线索二叉树。

我们发现，在含有n个结点的二叉树中有n-1条边指向其左、右孩子，意味着n个结点的二叉链表中，2n个链域只用了n-1个，另外还有n+1个指针域是空的。可充分利用这些空指针来存放结点的线性前驱和后继信息。

6.5.1 相关术语

  • 前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱与后继。

  • 线索：指向前驱或后继结点的指针称为线索。

  • 线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。

  • 线索二叉树：线索化后的二叉树叫线索二叉树。

6.5.2 定义

  1. 若结点有左子树，则其lchild域指向其左孩子，否则令lchild域指向其直接前驱；

  2. 若结点有右子树，则其rchild域指向其右孩子，否则令rchild域指向其直接后继。

通过给结点增加两个标志域来确定是指向孩子还是前驱或后继：

线索二叉树

1
2
3
4
5
typedef struct node {
    datatype data;
    int ltag, rtag;
    struct node *lchild, *rchild;
}birthptr;

6.5.3 二叉树的线索化

线索化实质上是将二叉链表中的空指针域填上相应结点的遍历前驱或后继结点的地址，而前驱和后继的地址只能在动态的遍历过程中才能得到。因此线索化的过程即为在遍历过程中修改空指针域的过程。

对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树。这里介绍中序线索化的算法。

6.5.3.1 算法思想

（1）中序线索化采用中序递归遍历算法框架。

（2）加线索操作就是访问结点操作。

（3）加线索操作需要利用刚访问过结点与当前结点的关系，因此设置一个指针 pre，始终记录刚访问过的结点，其操作如下：

  1. 如果当前遍历结点 root 的左子域为空，则让左子域指向 pre ；

  2. 如果前驱 pre 的右子域为空，则让右子域指向当前遍历结点 root；

  3. 为下次做准备，当前访问结点 root 作为下一个访问结点的前驱 pre。

6.5.3.2 算法描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 对 root 所指的二叉树进行中序线索化，其中 pre 始终指向刚访问过的结点，其初值为 NULL */
void Inthread(BiTree root) { 
    if (root != NULL) { 
        Inthread(root->LChild); /* 线索化左子树 */
        
        //置前驱线索
        if (root->LChild == NULL) {
            root->Ltag = 1;
            root->LChild = pre;
        }

        //置后继线索
        if (pre != NULL && pre->RChild == NULL) {
            pre->Rtag = 1;
            pre->RChild = root;
        }

        pre = root; /* 当前访问结点作为下一个访问结点的前驱 */

        Inthread(root->RChild); /*线索化右子树*/
    }
}

对于同一棵二叉树，遍历的方法不同，得到的线索二叉树也不同。下图所示为一棵二叉树的先序、中序和后序线索树：

二叉树的线索化

6.5.4 遍历线索树

遍历线索树的问题可以分解成两步，第一步是求出某种遍历次序下第一个被访问结点；然后连续求出刚访问结点的后继结点，直至所有的结点均被访问。以遍历中序线索树为例：

（1）在中序线索树上求中序遍历的第一个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
BiTNode * InFirst(BiTree Bt) {
    BiTNode *p=Bt;

    if(!p){
        return (NULL);
    }

    while(p->LTag==0) {
        p=p->Lchild;
    }

    return p;
}

（2）遍历中序二叉线索树：通过调用 InFirst 和 InNext ,可以实现对中序线索树的中序遍历，且不需要使用递归栈。

1
2
3
4
5
6
7
8
9
void TInOrder(BiTree Bt) {
    BITNode *p;
    P=InFirst(Bt);
 
    while(p) {
        Visit(p);
        p = InNext(p);
    }
}

6.6 树的存储

6.6.1 双亲表示法

定义结构数组存放树的结点，每个结点含两个域：

  • 数据域：存放结点本身信息。

  • 双亲域：指示本结点的双亲结点在数组中位置。

特点：找双亲容易，找孩子难。定义如下：

1
2
3
4
5
6
7
8
9
10
typedef  struct {   
    datatype   data;
    int  parent;
}pNode;

typedef struct {  
    pNode tnode[MAXSIZE];
    int n;
}ptree;

双亲表示法

6.6.2 孩子链表示法

其主体是一个与结点个数一样大小的一维数组和孩子结点单链表。

数组的每个元素由两个域组成：结点信息和指针。

单链表也由两个域组成：孩子结点在一维数组中的序号和指向下一个孩子的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
//孩子结点
typedef struct node { 
    int child; //孩子结点序号
    struct node *next; //孩子链表结点
}link;

//表头结点
typedef struct tnode { 
    datatype data; //树结点数据域
    link * headptr; //孩子链表头指针
}ctree;

ctree T[MAXSIZE];

孩子链表示法

6.6.3 孩子兄弟链表示法

实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

特点：操作容易，破坏了树的层次。

1
2
3
4
5
typedef struct node {   
    datatype data;
    struct node *fson, *next;
}JD;

孩子兄弟链表示法

6.7 树、森林与二叉树的转换

6.7.1 树转换成二叉树

树转换成二叉树

6.7.2 二叉树转换成树

二叉树转换成树

6.7.3 森林转换成二叉树

森林转换成二叉树

6.7.4 二叉树转换成森林

二叉树转换成森林

6.8 树和森林的遍历

6.8.1 树的遍历

  • 先根(序)遍历：先访问树的根结点，然后依次先根遍历根的每棵子树
  • 后根(序)遍历：先依次后根遍历每棵子树，然后访问根结点

树的遍历

1
2
3
4
5
6
7
8
/* 树的先根遍历 */
void RootFirst(CSTree root) {
    if (root!=NULL) {
        Visit(root ->data); /*访问根结点*/
        RootFirst(root->FirstChild); /*先根遍历首子树*/
        RootFirst(root->Nextsibling); /*先根遍历兄弟树*/
    }
}

6.8.2 森林的遍历

(1) 先序遍历

  • 若森林为空，返回；

  • 访问森林中第一棵树的根结点；

  • 先序遍历第一棵树中根结点的子树；

  • 先序遍历除去第一棵树之后剩余的树构成的森林。

(2) 后序遍历

  • 若森林为空，返回；

  • 后序遍历森林中第一棵树的根结点的子树森林；

  • 访问第一棵树的根结点；

  • 后序遍历除去第一棵树之后剩余的树构成的森林。

森林遍历

6.8.3 二叉树与树、森林遍历对比

树 森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序

树有先根和后根遍历；森林有先序和中序遍历；二叉树则有先序、中序和后序遍历。 其中，

  • 树的先根遍历，森林的先序遍历和二叉树的先序遍历相互对应。

  • 树的后根遍历，森林的中序遍历和二叉树的中序遍历相互对应。

6.9 哈夫曼树及哈夫曼编码

6.9.1 相关名词

（1）路径： 从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

（2）路径长度： 路径上的分支数。若规定根结点的层数为 1 ，则从根结点到第L层结点的路径长度为L-1。

（3）结点的路径长度： 从根结点到该结点的路径上分支的数目。

（4）树的路径长度： 树中每个结点的路径长度之和。

（5）结点的带权路径长度： 从该结点到树根的路径长度与结点上权的乘积。

（6）树的带权路径长度： 树中所有叶子结点的带权路径长度之和（其中 WkW_k 为权值，LkL_k 为结点到根的路径长度）。

WPL=∑k=1nWkLkWPL = \sum_{k=1}^n W_k L_k

6.9.2 哈夫曼树

有n个叶子结点且其权值分别为 W1,W2,...,WnW_1, W_2, ..., W_n 的二叉树中，带权路径长度 WPL 最小的二叉树叫哈夫曼树（最优二叉树）。例如下图：

WPL=7×1+5×2+2×3+4×3=35

哈夫曼树

6.9.3 哈夫曼树的构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 W1,W2,...,WnW_1, W_2, ..., W_n ，则哈夫曼树的构造规则为：

(1) 将 W1,W2,...,WnW_1, W_2, ..., W_n 看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。

假设给定的叶子结点的权分别为1, 5, 7, 3，则构造哈夫曼树过程如下所示：

哈夫曼树构造

从图可知，n 个权值构造哈夫曼树需 n-1 次合并，每次合并森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。

6.9.4 哈夫曼编码

规定：左分支用“0”表示；右分支用“1”表示。

哈夫曼编码

若哈夫曼树如上图所示：

因此编码为：A—0，B—110，C—10，D—111。因此序列ABACCDA的哈夫曼编码为0110010101110。

译码过程：分解接收字符串：遇“0”向左，遇“1”向右。一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。

注：哈夫曼树不是唯一的，但其WPL唯一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef char * HuffmanCode[N+1]; /* 存储哈夫曼编码串的头指针数组 */

/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/
void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n) {
    char *cd;
    cd=(char * )malloc(n* sizeof(char )); /*分配求当前编码的工作空间*/
    cd[n-1]＝’\0’； /*从右向左逐位存放编码，首先存放编码结束符*/
    
    /*求 n 个叶子结点对应的哈夫曼编码*/
    for(i=1;i<=n;i++) {
        start=n-1; /*初始化编码起始指针*/
        c=i; p=ht[i].parent; /* 从叶子结点开始向上倒推 */
        
        while(p!=0) { 
            --start;
            if(ht[p].LChild==c)
                 cd[start]=’0’; /*左分支标 0*/
            else 
                    cd[start]=’1’; /*右分支标 1*/
            c=p; p=ht[p].parent; /* 向上倒推 */
        }
        
        hc[i]=(char *)malloc((n-start)*sizeof(char)); /*为第 i 个编码分配空间*/
        strcpy(hc[i], &cd[start]); /*把编码复制到 hc[i]中*/
    }

    free(cd);
}

6.10 例题

6.10.1 例1

问： 二叉树与度为2的树有何区别？

①度为2的树是不区分左子树和右子树.而二叉树是要分左子树和右子树的。
②度为2的数不包含空树，而二叉树是可以有空树的。

6.10.2 例2

问： n个结点的二叉树中如果有m个叶结点，则一定有【 m-1 】个度为2的结点。

注：二叉树中度为2结点数 = 结点数-1

6.10.3 例3

问： 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为【 6 】个。

注：结点数 = 度数之和 + 1

6.10.4 例4

问： 将一棵有100个结点的完全二叉树从根这一层开始，开始进行层次遍历编号，那么编号最小的叶节点的编号为（根节点为1）【 51 】。

注：完全二叉树中，对于编号为i的父结点，左孩子编号为2i，右孩子编号为2i+1；编号为100的节点对应的父节点编号为50，故最小叶子节点编号为51。

6.10.5 例5

问： 若一棵二叉树高度为H，其上只有度为0和度为2的结点，则此二叉树中包含结点数至少为多少【 2H-1 】。

6.10.6 例6

问： 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

DLR：A B D F J G K C E H I L M
LDR: B F J D G K A C H E L I M
LRD：J F K G D B H L M I E C A

6.10.7 例7

问： 某二叉树前序遍历是A B D E G C F H，中序遍历是D B G E A C H F，求其后序遍历。

首先从前序的第一个确定二叉树的根A，回到中序切割，将二叉树分为三部分：
左子树的中序DBGE，根A，右子树的中序CHF
再由左子树的前序可知左子树的根为B，于是左子树的中序被再次切分为三部分：
左子树的左子树中序D，左子树的根B，左子树的右子树的中序GE
类似地，由右子树的前序可知右子树的根为C，于是右子树的中序也被切分为三部分：
右子树的左子树为空，右子树的根C，右子树的左子树的中序HF
继续切分下去：GE的根为E、HF的根为F，直到每棵子树只有一个结点为止，最终得到的完整二叉树，因此其后序遍历为： D G E B H F C A

6.10.8 例8

问： 画出下列二叉树相应的森林：

注：首先将二叉树分割为孤立的二叉树，再将每个孤立的二叉树转换为树

6.10.9 例9

问： 把下图所示的树转化为二叉树：

注：所有兄弟之间连线，然后删除除左孩子之间的连线以外的所有其他连线

6.10.10 例10

问： 已知一棵二叉树的中序遍历序列为 CBEDAHGIJF，后序遍历序列为 CEDBHJIGFA，给出该二叉树树形表示，并写出其前序遍历的结点序列。画出二叉树 bt 的前序线索树。

注：线索树：如果存在左孩子，则指向左孩子，否则指向直接前驱；如果存在右孩子，则指向右孩子，否则指向直接后继。线索用虚线表示。

6.10.11 例11

问： 设给定权集 W={2,3,4,6,8,11}W=\{2,3,4,6,8,11\} ，试构造关于W的一棵哈夫曼树，写出各数据的哈夫曼编码，并求其带权路径长度 WPLWPL。