第六章 树与二叉树

树与二叉树

1.树的基本概念和术语

1.1树的定义：树是（n≥0）个结点的有限集合T。

• 当n=0时称为空树；当n＞0时，该集合满足如下条件：（1）其中必有一个称为根（root）的特定结点，它没有直接前驱，但有0个或多个直接后继。（2）其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1，T2，T3，…Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，但有0个或多个直接后继。

1.2术语

• 根：即根结点（没有前驱）除根结点外的分支结点统称为内部结点。

• 结点：包括一个数据元素及若干指向其他结点的分支信息

• 结点的度：一个结点的子树个数（即分支的个数）

• 叶子结点：度为0的结点，即无后继结点，也称为终端结点

• 分支结点：度不为0的结点，也称为非终端结点

• 结点的层次：从根到该结点的层数（根结点为第一层）

• 结点的层序编号：将树中的结点按从上到下、从左到右的次序排成一个线性序列，依次给它们编以连续的自然数

• 树的度：树中所有结点的度的最大值

• 树的高度（深度）：树中所有结点的层次的最大值

• 有序树：结点各子树从左至右有序，不能互换（左为第一）

• 森林：指m（m≥0）棵不相交的树的集合，反之，给森林增加一个统一的根结点，森林就变成一棵树

  同构：对两棵树，通过对结点适当地重命名，可以使两棵树完全相等（结点对应相等，对应结点的相关关系也相等），则称这两棵树同构。

• 孩子结点：一个结点的直接后继

• 双亲结点：一个结点的直接前驱

• 兄弟结点：同一双亲结点的孩子结点之前互称

• 堂兄弟：即双亲位于同一层的结点（但并非同一双亲）

• 祖先结点：即从根到该结点所经分支的所有结点

• 子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点，即该结点下层子树中的任一结点

1.3树的两个特点

• 1.树的跟结点没有前驱结点，除根结点之外有且只有一个前驱结点
• 2.树中所有结点可以有0个或多个后继结点

1.4树的抽象数据类型

2.二叉树的定义和基本操作

特点：（1）每个结点的度都不大于2；

     （2）每个结点的孩子结点次序不能任意颠倒（有序树）。
1
2
3

满足以上两个条件的树型结构为二叉树（Binary Tree）二叉树或为空树，或由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

2.1二叉树与树（普通树、多叉树）的区别：

1.树中结点的最大度数没有限制，而二叉树结点的最大度数为2
2.树的结点无左右之分，而二叉树的结点有左右之分
3.二叉树和树都属于树形结构
4.所有树都能转化为唯一对应的二叉树
1
2
3
4

2.2二叉树的定义及基本操作

形态：5种

基本操作：

①Initiate(bt);//初始一棵空二叉树
②Destory (bt);//销毁一棵二叉树
Creat (bt)://创建一棵非空二叉树
④Empty(bt);//树为空返回TRUE
⑤Root(bt);//求根结点
⑥Parent(bt,x);//求双亲结点
⑦LeftChild(bt,x);//求左孩子
⑧RithtChild(bt,x);//求右孩子
⑨Traverse(bt);//遍历操作
⑩Clear(bt);/l将二叉树置为空树
1
2
3
4
5
6
7
8
9
10

3.二叉树的5个性质 （重点）

（1）在二叉树的第i层上至多有2的（i-1）个结点。
（2）深度为k的二叉树上至多含2的（k-1）个结点（k≥1）。
（3）对任何一棵二叉树，若它含有n0和叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1.
（4）具有n个结点的完全二叉树的深度为log2 n+1向下取整
（5）若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中  任意一个编号为i的结点:
    <1>若i=1，则序号为i的结点是根结点，无双亲结点，若i≥>1，则序号为i的结点的双亲结点的序号为Li/2]:
    <2>若2i>n，则序号为i的结点无左孩子，若2i ≤n，则序号为i的结点的左孩子结点的序号为2i ;
    <3>若2i+1>n，则序号为i的结点无右孩子，若2i +1 ≤n ,则序号为i的结点的右孩子结点的序号为2i+1。
1
2
3
4
5
6
7
8

两种特殊的二叉树

区别：

4.二叉树的存储结构

4.1 顺序存储 一维数组bt[1…n]

是用一组连续的存储单元来存放二叉树的数据元素。

对于完全二叉树来说，可以将其数据元素逐层存放到一组连续的存储单元中，例如将编号为i的结点存放在数组的第i个分量中，则i的左孩子为2i,i的右孩子为2i+1。

4.2链式存储 二叉链表

用C语言定义二叉树的二叉链表结点结构：
typedef struct Node{
  DataType data;
  struct Node * lchild;/*左右孩子指针*/
  struct Node * rchild;
}BiTNode,*BiTree;
1
2
3
4
5
6

在n个结点的二叉链表中，有n+1个空指针域。

三叉链表

有时，为了便于找到双亲结点，可以增加一个parent域，以指向该结点的双亲结点，采用这种结点结构的存放方式称为三叉链表存储结构。

typedef struct TriTNode
{ TelemType data;
  struct TriTNode *lchild, *parent,*rchild;
} TriTNode,*TriTree;
1
2
3
4

5.二叉树的遍历 （重点）

5.1遍历：分为先序、中序、后序

5.1.1先序遍历算法

5.1.2中序遍历算法

5.1.3后序遍历算法

遍历的算法分析：

时间效率:○(n)//每个结点只访问一次
空间效率:○(n)//栈占用的最大辅助空间

6.由遍历序列确定二叉树 （重点）

7.二叉树遍历算法的应用

7.1输出二叉树中的结点

遍历算法将走遍二叉树中的每一个结点，故输出二叉树中结点并无次序要求，因此可用任一种算法来完成。
void PreOrder(BiTree root)
{
   if (root!=NULL)
   {
     printf ("%c",root ->data);/*输出根结点*/
     PreOrder(root ->LChild);/*先序遍历左子树*/
     PreOrder(root ->RChild);/*先序遍历右子树*/
   }
}
1
2
3
4
5
6
7
8
9
10

7.2输出二叉树中的叶子结点

判断结点既没有左孩子，又没有右孩子时，则输出该结点。
  void PreOrderLeaf(BiTree root)
{ 
   if (root!=NULL)
   {
     if (root->LChild==NULL && root->RChild==NULL)
     printf(%c ",root ->data);/*输出叶子结点*/
     PreOrderLeaf(root ->LChild);/*先序遍历左子树*/
     PreOrderLeaf(root ->RChild);/*先序遍历右子树*/
   }
}
1
2
3
4
5
6
7
8
9
10
11

输出二叉树中的度为2的结点的条件

7.3统计叶子结点数目

方法1:（采用全局变量)

/*LeafCount保存叶子结点数目的全局变量,调用之前初始化值为0*/
void leaf(BiTree root)
  {
    if(root!=NULL)
    {
       leaf(root->LChild);
       leaf(root->RChild);
       if (root ->LChild==NULL && root ->RChild==NULL)
       LeafCount++;
    }
  }
1
2
3
4
5
6
7
8
9
10
11

方法2:采用递归算法

/*如果是空树，返回0;如果只有一个结点，返回1;否则为左右子树的叶子结点数之和*/
int leaf(BiTree root)
{
   int LeafCount;
   if(root==NULL)
      leafCount =0;
    else if((root->LChild==NULL)&&(root->RChild==NULL))
            LeafCount =1;
         else
            LeafCount =leaf(root->LChild)+leaf(root->RChild);
    return LeafCount;
}
1
2
3
4
5
6
7
8
9
10
11
12

7.4求二叉树的高度

设函数表示二叉树bt的高度，则递归定义如下:

若bt为空，则高度为0
若bt非空，其高度应为其左右子树高度的最大值加1

int PostTreeDepth(BiTree bt)
{
    int hl,hr,max;
    if(bt!=NULL)
    {
        hl=PostTreeDepth(bt->LChild);
        hr=PostTreeDepth(bt->RChild);
        max=hl>hr?hl:hr;
        return(max+1);
    }
   else return(0);
}
1
2
3
4
5
6
7
8
9
10
11
12

7.5按树状打印二叉树

算法思想:
1)二叉树的横向显示是竖向显示的90度旋转;
2)打印结点的顺序恰为二叉树中序顺序的逆序，所以横向显示算法RDL结构，为称为逆中序。
3)在访问根结点的语句中加入FOR循环语句，以控制输出结点的左、右位置，设置了一个层深参数nLayer，每当递归进层时层深参数加1;若没有这个for循环，打印出来的则是对齐的一列，不会有错位显示。

void PrintTree(BiTree bt,int nLayer)
{
   if(bt = =NULL) return;
   PrintTree(bt ->Rchild,nLayer+1);
   for(int i=0;i<nLayer;i++)
       printf("");
   printf("%c\n", bt ->data);
   PrintTree(bt -> Lchild,nLayer+1);
}
1
2
3
4
5
6
7
8
9

7.6建立二叉链表方式存储的二叉树

算法思想:
采用类似先序遍历的递归算法，首先读入当前根结点数据，如果是“.”则将当前树根置为空，否则申请一个新结点，存入当前根结点的数据，分别用当前根点点的左孩子域和右孩子域进行递归调用，创建左子树和右子树。

void CreateBiTree(BiTree *bt)
{
    char ch;
    ch = getchar();
    if(ch=='.')*bt=NULL;
    else
      {
        *bt=(BiTree)malloc(sizeof(BiTNode));
        /*生成一个新结点，完成双亲结点和子结点的相连*/
        (*bt)->data=ch;
        CreateBiTree(&((*bt)->LChild));/*创建左子树*/
        CreateBiTree(&((*bt)->RChild));/*创建右子树*/
       }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.7基于栈的递归消除

递归转换到非递归的原因:
递归的执行效率低;
运行环境没有递归机制
1
2
3

8.线索二叉树

8.1基本概念

在这种存储结构中，指向前驱和后继结点的指针叫做线索。

以这种结构组成的二叉链表作为二叉树的存储结构，叫做线索链表。

对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化

线索化了的二叉树称为线索二叉树。

线索化实质上是将二叉链表中的空指针域填上相应结点的遍历前驱或后继结点的地址，而前驱和后继的地址只能在动态的遍历过程中才能得到。因此线索化的过程是在遍历过程中修改空指针域的过程。对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树（先序线索二叉树、中序线索二叉树和后序线索二叉树)。
1
2
3
4
5
6
7
8
9

8.2建立线索链表

在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre，并始终保持指针pre指向当前访问的、指针root所指结点的前驱。
1

8.2.1中序线索化算法

算法思想:
1中序线索化采用中序递归遍历算法框架。
2加线索操作就是访问结点操作。
3加线索操作需要利用刚访问过的结点与当前结点的关系，因此设置一个指针pre,始终记录刚访问过的结点，其操作如下:
  a如果当前遍历结点root的左子域为空，则让左子域指向pre;
  b如果前驱右子域为空，则让右子域指向当前遍历结点root;
  c为下次做准备，当前访问结点root作为下一个访问结点的前驱pre;
1
2
3
4
5
6
7

8.2.2在线索二叉树中找前驱、后继结点

9.树、森林和二叉树的关系

9.1树的存储结构

9.1.1双亲表示法

9.1.2孩子表示法

9.1.3孩子兄弟表示法

9.2树、森林与二叉树的相互转换

9.2.1树转换为二叉树

树中结点的各孩子的次序是无关紧要的，而二叉树中结点的左、右孩子是有区别的。我们约定树中每一个结点的孩子结点按从左到右的次序顺序编号，也就是说，把树作为有序树看待。

1.树转换为二叉树的方法

(1)树中所有相邻兄弟之间加一条连线。

(2)对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。

(3)以树的根结点为轴心，将整棵树顺时针旋转一定的角度,使之结构层次分明。

2.结论：

从转换过程可看出:树中的任意一个结点都对应于二叉树中的一个结点。
树中某结点的第一个孩子在二叉树中是相应结点的左孩子，树中某结点的右兄弟结点在二叉树中是相应结点的右孩子。
也就是说，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必然为空。
1
2
3

9.2.2森林转换为二叉树方法

(1）将森林中的每棵树转换成相应的二叉树。

(2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二及树就是由森林转换得到的二叉树。

森林和树都可以转换为二叉树，两者的区别：

由树转换成二叉树，其根结点必然无右孩子；

由森林转换而得的二叉树，其根结点有右孩子。

9.2.3二叉树还原为树或森林

一棵二叉树还原为树或森林，具体方法为:
(1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、…都与该结点的双亲结点用线连起来。
(2)删掉原二叉树中所有双亲结点与右孩子结点的连线。
(3）整理由（1）、(2）两步所得到的树或森林使之结构层次分明。

9.3树与森林的遍历

树的遍历（树的结构特点：树根、树的子树森林）

9.3.1树的遍历方法主要有以下两种：

（1）先根遍历

若树非空，则遍历方法为：

（1）访问根结点。

（2）从左到右，依次先根遍历根结点的每一棵子树。
1
2
3
4
5

（2）后跟遍历

若树非空，则遍历方法为：

（1）从左到右，依次先根遍历根结点的每一棵子树。

（2）访问根结点。
1
2
3
4
5

注：

树的先根遍历等同于对转换所得的二叉树进行先序遍历；

树的后跟遍历等同于对转换所得的二叉树进行中序遍历。

9.3.2森林的遍历

森林的结构特点：第一棵树、其余的树

森林的遍历方法有三种：

（1）先序遍历

若森林非空，则遍历方法为
(1)访问森林中第一棵树的根结点。
(2)先序遍历第一棵树的根结点的子树森林。
(3)先序遍历除去第一棵树之后剩余的树构成的森林。
1
2
3
4

（2）中序遍历

若森林非空，则遍历方法为:
(1)中序遍历森林中第一棵树的根结点的子树森林。
(2)访问第一棵树的根结点。
(3)中序遍历除去第一棵树之后剩余的树构成的森林。
1
2
3
4

（3）后序遍历

若森林非空，则遍历方法为:
(1)后序遍历森林中第一棵树的根结点的子树森林。
(2)后序遍历除去第一棵树之后剩余的树构成的森林。
(3)访问第一棵树的根结点。
1
2
3
4

注：

森林的先序遍历等同于对转换所得的二叉树进行先序遍历；

森林的中序遍历等同于对转换所得的二叉树进行中序遍历；

森林的后序遍历等同于对转换所得的二叉树进行后序遍历；

9.3.3树、二叉树、森林遍历关系对应表：

10.哈夫曼树及其应用 （重点）

10.1基本概念

路径:从一个结点到另一个结点之间的分支序列。

路径长度:从一个结点到另一个结点所经过的分支数目。

结点的权值:树中每个结点所赋予的具有某种实际意义的实数。

结点的带权路径长度:从树根到某一结点的路径长度与该结点的权值的乘积。

树的带权路径长度:树中从根到所有叶子结点的各个带权路径长度之和。
1
2
3
4
5
6
7
8
9

10.1.1最优二叉树

在叶子个数n以及各叶子权值Wi确定的条件下，树的带权路径长度WPL值最小的二叉树。

哈夫曼依据最优二叉树的特点:权值越大，离根越近,给出了构造的方法，因此最优二叉树又称哈夫曼树。

10.1.2哈夫曼树

哈夫曼树是由n个带权叶子结点所构成的所有二义树中带权路径长度最短的二叉树，这种树最早是由哈夫曼（Huffman）研究，所以称为哈夫曼树，又称最优二义树。

10.2构建哈夫曼树（重点）

(1)根据给定的n个权值{w1，W2，…，W}，构造n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树中均只含一个带权值为w的根结点，其左、右子树为空树;

(2)在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;

(3)从F中删去这两棵树，同时加入刚生成的新树;

(4)重复(2)和(3)两步，直至F中只含一棵树为止。

10.2.1哈夫曼树的特点

1. 没有度为1的结点;
2. n个叶子结点的哈夫曼树共有2n-1个结点;
   (n个结点在构造过程中，生成n-1个非叶子结点)
3. 哈夫曼树的任意非叶子结点的左右子树交换后仍是哈夫曼树;
4. 对同一组权值{w1, w2,… … ., wn}，存在不同构的两棵哈夫曼树，但它们的带权路径长度(WPL)一定是一样的；

10.3哈夫曼树的类型定义

n个叶子结点的哈夫曼树共有2n-1个结点,因此可用有2n-1个元素的一维数组来存储哈夫曼树的各个结点，结点间的父子关系用下标来指示;在使用哈夫曼树进行编码和译码时，既要用结点的双亲信息，又要用结点的孩 信息，所以采用静态三叉链表来存储哈夫曼树。
1

10.4哈夫曼树的算法实现（难点）

初始化:先将n个元素都视为根结点,即孩子和双亲指针全置0。

建哈夫曼树的过程是:反复在数组中选双亲为0(表示它们当前是树根)且权值最小的两结点，将它们作为左右孩子挂在新的结点之下，新结点权值为左右孩仔权值之和。

10.5哈夫曼树及其应用

10.5.1哈夫曼树编码

在编码的设计中，通常遵守两个原则:

(1)编码能够唯一地被译码。
(2)编码长度要尽可能的短。

如何避免编码的二义性?
如果任何字符的编码都不是另一个字符编码的前缀，则可以无二义的解码。

前缀编码:任何一个字符的编码都不是另一个字符的编码的前缀,这种编码方式称为前缀编码。
1
2
3
4

10.5.2如何进行哈夫曼编码？

对哈夫曼树中每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的值构成该叶子结点的哈夫曼编码。

哈夫曼树是树的带权路径长度值为最小的二叉树，其特点就是:叶子结点权值越大，离根越近。

为保证信息编码长度最短，先统计各字符出现的次数，然后以此作为权值，构建哈夫曼树。

构造不等长编码的原则是:字符使用频率越高，编码越短。

用哈夫曼树设计编码的设想是:
每个待编码的字符对应一个叶子结点;
每个字符的使用频率对应叶子的权值;
每个字符的编码对应根到叶子的路径;
1
2
3
4
5
6
7
8
9
10

10.5.3结论

10.5.4哈夫曼编码的算法实现