目录

5.1树的基本概念

5.1.1树的定义

5.1.2 基本术语 

5.1.3树的性质

5.2二叉树的概念

5.2.1二叉树的定义及其主要特性

1.二叉树的定义

2.几个特珠的二叉树

1)满二又树。

 2)完全二叉树

 3)二叉排序树

4)平衡二叉树

3.二叉树的性质

 5.2.2二叉树的存储结构

1.顺序存储结构

 2.链式存储结构

5.3二叉树的遍历和线索二叉树

5.3.1二叉树的遍历

1.先序遍历

 2.中序遍历

 3.后序遍历

 4.递归

5.层次遍历

 6.由遍历序列构造二叉树

     5.3.2线索二叉树

 1.线索二叉树的基本棍念

 2.中序线索二叉树的构造

 3.中序线索二叉树的遍历.....

4.先序线索二叉树和后序线索二叉树....

 5.4树、森林

5.4.1树的存储结构

1.双亲表示法

2，孩子表示法

3.孩子兄弟表示法

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

5.4.3树和森林的遍历

 5.5树与二叉树的应用

5.5.1哈夫曼树和哈夫曼编码

 1.哈夫曼树的定义

 2.哈夫曼树的构造

 3.哈夫曼编码

5.1树的基本概念

5.1.1树的定义

树是n (n>_0)个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足:
(1)有且仅有一个特定的称为根的结点。

     显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树
作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点:
    1)树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
    2)树中所有结点可以有零个或多个后继。
    树适合于表示具有层次结构的数据。树中的某个结点(除根结点外)最多只和上一层的一个
结点(即其父结点)有直接关系，根结点没有直接上层结点，因此在n个结点的树中有n-1条边。
而树中每个结点与其下一层的零个或多个结点(即其子女结点)有直接关系。

5.1.2 基本术语 

(l) 结点：树中的一个独立单元。包含一个数据元素及若于指向其子树的分支，如图 5.1 (b) 中的 A 、 B 、 C 、 D 等。（下面术语中均以图 5.1 (b) 为例来说明）

(2)结点的度：结点拥有的子树数称为结点的度。例如，A的度为 3, C的度为l, F的度 为0。

(3)树的度：树的度是树内各结点度的最大值。图 5.1 (b) 所示的树的度为3。

(4) 叶子： 度为 0 的结点称为叶子或终端结点。结点 K 、 L 、 F 、 G 、 M 、 I 、 J都是树的 叶子。

(5) 非终端结点：度不为 0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点 也称为内部结点。

(6)双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例 如，B的双亲为A, B的孩子有E和F。

(7) 兄弟：同一个双亲的孩子之间互称兄弟。例如，H 、 I 和J互为兄弟。

(8) 祖先：从根到该结点所经分支上的所有结点。例如， M 的祖先为 A 、 D 和H。

(9) 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如 B 的子孙为E 、 K 、 L 和F。

(10) 层次：结点的层次从根开始定义起，根为 第一层，根的孩子为第二层。树中任一结点的 层次等千其双亲结点的层次加 1。

(11)堂兄弟：双亲在同 一层的结点互为堂兄弟。例如，结点 G 与E 、 F、 H 、 I 、 J互为 堂兄弟。
(12)树的深度：树中结点的最大层次称为树的深度或高度。图5.1 (b)所示的树的深度 为4。

(13)有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换）， 则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的 称为最后一个孩子。

(14)森林：是m (m=>0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即 为森林。由此，也可以用森林和树相互递归的定义来描述树。

(15)路径和路径长度:树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
注意:由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径.

5.1.3树的性质

5.2二叉树的概念

5.2.1二叉树的定义及其主要特性

   1.二叉树的定义

    二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于
2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。
    与树相似，二叉树也以递归的形式定义。二叉树是n (n>=0)个结点的有限集合:
    ①或者为空二叉树，即n = 0
    ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树
        又分别是一棵二叉树。
    二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有
一棵子树，也要区分它是左子树还是右子树。二叉树的5种基本形态如图5.2所示。

 二叉树与度为2的有序树的区别:
①度为2的树至少有3个结点，而二叉树可以为空。
②度为2的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，
  则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次
  序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。

2.几个特珠的二叉树

1)满二又树。

 2)完全二叉树

 3)二叉排序树

        左子树上所有结点的关键字均小于根结点的关键字;

        右子树上的所有结点的关键字均大于根结点的关键字;

左子树和右子树又各是一棵二叉排序树。

4)平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1

3.二叉树的性质

 5.2.2二叉树的存储结构

1.顺序存储结构

        二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树
上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中。

 二叉树的顺序存储结构如图所示，其中0表示并不存在的空结点。

 

 2.链式存储结构

 在含有n个结点的二叉链表中,含有n+1个空链域

5.3二叉树的遍历和线索二叉树

5.3.1二叉树的遍历

    二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅
被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规
律，以便使二叉树上的结点能排列在一个线性队列上，进而便于遍历。

1.先序遍历

先序遍历(PreOrder)的操作过程如下。
若二叉树为空，则什么也不做;否则，
1)访问根结点;
2)先序遍历左子树;
3)先序遍历右子树。

 2.中序遍历

中序遍历(InOrder)的操作过程如下。
若二叉树为空，则什么也不做;否则，
1)中序遍历左子树;
2)访问根结点:
3)中序遍历右子树。

 3.后序遍历

后序遍历(PostOrder)的操作过程如下。
若二叉树为空，则什么也不做;否则，
1)后序遍历左子树;
2)后序遍历右子树;
3)访问根结点。

 

 4.递归

5.层次遍历

     6.由遍历序列构造二叉树

    由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
    在先序遍历序列中，第一个结点一定是二叉树的根结点:而在中序遍历中，根结点必然将中
序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点
的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先
序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。
如此递归地进行下去，便能唯一地确定这棵二叉树。

  由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子
序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。
由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树.

     5.3.2线索二叉树

      1.线索二叉树的基本棍念

    遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序
列，使得该序列中的每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。

规定:若无左子树，令lchild指向其前驱结点;若无右子树，令rchild指向其后继结点。
如图5.10所示，还需增加两个标志域标识指针域是指向左(右)孩子还是指向前驱(后继)。

 以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱
和后继的指针称为线索。加上线索的二叉树称为线索二又树。

    n个结点共有链域指针2n个，其中，除根结点外，每个结点都被一个指针指向。剩余的链域建立线索，共2n-1(n-1)=n+1个线索。
 

    2.中序线索二叉树的构造

    二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息
只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。
    以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点，指针p指向正在访
问的结点，即pre指向P的前驱。在中序遍历的过程中，检查P的左指针是否为空，若为空就
将它指向pre;检查pre的右指针是否为空，若为空就将它指向P，如图5.11所示。

 3.中序线索二叉树的遍历.....

4.先序线索二叉树和后序线索二叉树....

同用于计算二叉树结点顺序个数 

 5.4树、森林

5.4.1树的存储结构

树的存储方式有多种，既可采用顺序存储结构，又可采用链式存储结构

    1.双亲表示法

    这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示
其双亲结点在数组中的位置。如图5.14所示，根结点下标为0，其伪指针域为-1

     该存储结构利用了每个结点(根结点除外)只有唯一双亲的性质，可以很快得到每个结点的
双亲结点，但求结点的孩子时需要遍历整个结构。

    注意:区别树的顺序存储结构与二叉树的顺序存储结构。在树的顺序存储结构中，数组下标
代表结点的编号，下标中所存的内容指示了结点之间的关系.而在二又树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。当然，二叉树属于树，因此二又树都可以用树的存储结构来存储，但树却不都能用二叉树的存储结构来存储。

2，孩子表示法

        孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点
就有n个孩子链表(叶子结点的孩子链表为空表)，如图5.15(a)所示。
这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指
针域所指向的n个孩子链表。

 3.孩子兄弟表示法

        孩子兄弟表示法又称二又树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每
个结点包括三部分内容:结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点)，如图5.15(b)所示。

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点,则查找结点的父结点也很方便。

 

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

    由于二叉树和树都可以用二叉链表作为存储结构，因此以二叉链表作为媒介可以导出树与二
叉树的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构上看，
它们的二叉链表是相同的，只是解释不同而已。
    树转换为二叉树的规则:每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻
右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树，
如图5.16所示。

         树转换成二叉树的画法:①在兄弟结点之间加一连线:②对每个结点，只保留它与第一个
孩子的连线，而与其他孩子的连线全部抹掉;③以树根为轴心，顺时针旋转45°
        森林转换成二叉树的画法:①将森林中的每棵树转换成相应的二叉树;②每棵树的根也可
视为兄弟关系，在每棵树的根之间加一根连线;③以第一棵树的根为轴心顺时针旋转45°

 

二叉树转换为树或森林是唯一的。

5.4.3树和森林的遍历

        树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式:
1)先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵
  循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。
2)后根遍历。若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵
  循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

        图5.16的树的先根遍历序列为ABEFCDG，后根遍历序列为EFBCGDA
另外，树也有层次遍历，与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。
按照森林和树相互递归的定义，可得到森林的两种遍历方法。

1)先序遍历森林。若森林为非空，则按如下规则进行遍历:
 .访问森林中第一棵树的根结点。
  .先序遍历第一棵树中根结点的子树森林。
  .先序遍历除去第一棵树之后剩余的树构成的森林。
2)中序遍历森林。森林为非空时，按如下规则进行遍历:
 ·中序遍历森林中第一棵树的根结点的子树森林。
  .访问第一棵树的根结点。
  .中序遍历除去第一棵树之后剩余的树构成的森林。
图5.17的森林的先序遍历序列为ABCDEFGHI，中序遍历序列为B CDAFEHI G
        当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换成右子树，可知森林的先序和中序遍历即为其对应二叉树的先序和中序遍历。

 5.5树与二叉树的应用

5.5.1哈夫曼树和哈夫曼编码

    1.哈夫曼树的定义

    在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，
也称最优二叉树。例如，图5.18中的3棵二叉树都有4个叶子结点a, b, c, d，分别带权7,5,2,4
它们的带权路径长度分别为

 2.哈夫曼树的构造

1、在哈夫曼算法中,初始时有n颗二叉树,要经过n-1次合并最终形成哈夫曼树。
2、经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点。

哈夫曼树中共有2n-1个结点,且其所有的分支结点的度均不为1.

 3.哈夫曼编码

左0右1