5 树与二叉树

Wu Jun 2020-02-05 00:16:43
01 数据结构与算法 > 数据结构 > 01 数据结构

一、树的基本概念

树:是 n ( n>=0 ) 个结点的有限集。

1、结点分类

2、结点间关系

3、树的其他相关概念

二、二叉树

1、二叉树的定义

二叉树:是 n(n >= 0) 个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

1)主要特征

2)特殊二叉树

3)二叉树性质

2、二叉树的存储结构

1)顺序存储结构

顺序存储结构一般只用于完全二叉树。

用一维数组存储二叉树中的结点,数组的下标和结点序号一致。没有结点的存空。

2)链式存储结构

二叉链表:一个数据域和两个指针域的链表。

指针域分别存左孩子和右孩子的指针。

3、二叉树的遍历

1)遍历方法

前序、中序、后序遍历用迭代很简单。

层序遍历,元素储存有先进先出的特性,选用队列。

2)遍历推导

3)二叉树的建立

扩展二叉树:将每个结点的空指针引出一个虚结点,值为特定值(如“#”)

扩展二叉树可以用递归采用前序、中序、后序遍历的一个遍历序列就确定一颗二叉树。

4、线索二叉树

1)基本概念

线索二叉树,等于是把一棵二叉树转属变成了一个双向链表,对插入删除结点、查找某个结点都带来了方便

2)构造

每个结点增设两个标志域 ltag 和 rtag,区分指针是指向孩子还是指向前驱、后继。

在遍历的过程中修改空指针。

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构就是非常不错的选择。

三、树、森林

1、树的存储结构

1 )双亲表示法

除了根结点外,其余每个结点,它不一定有孩子,但是一定有且仅有一个双亲。以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。

存储结构的设计是一个非常灵活的过程。

当算法中需要在树结构中频繁地查找某结点的父结点时,使用双亲表示法最合适。当频繁地访问结点的孩子结点时,双亲表示法就很麻烦,采用孩子表示法就很简单。

2)孩子表示法

由于树中每个结点可能有多棵子树,可以考虑用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法。

孩子表示法

把每个结点的孩子结点排列起来,以单链表作存储结构,则 n 个结点有 n 个孩子链表,如果是叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中

双亲孩子表示法

使用孩子表示法存储的树结构,正好和双亲表示法相反,适用于查找某结点的孩子结点,不适用于查找其父结点。可以将两种表示方法合二为一

孩子兄弟表示法

把一棵复杂的树变成一棵二叉树

链表中每个结点由 3 部分组成:

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

1)树转换为二叉树

  1. 加线。在所有兄弟结点之间加一条连线。
  2. 去钱。对树中每个结点,只保留它与第一个孩子结点的连线,删除色与其他孩子结点之间的连线。
  3. 层次调整。以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明。(注意第一个孩子是结点的左孩子,兄弟转换过来的孩子是结点的右孩子)

2)森林转换为二叉树

  1. 把每棵树转换为二叉树。
  2. 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。

3)二叉树转换为树

  1. 加线。若某结点X的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…,都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。
  2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。
  3. 层次调整。

4)二叉树转换为森林

假如一棵二叉树的根节点有右孩子,则这棵二叉树能够转换为森林,否则将转换为一棵树。

  1. 从根节点开始,若右孩子存在,则把与右孩子结点的连线删除。再查看分离后的二叉树,若其根节点的右孩子存在,则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。
  2. 将每棵分离后的二叉树转换为树。

3、树和森林的遍历

1)树的遍历

分为两种方式

2)森林的遍历

也分为两种方式:

森林的前序遍历和二叉树的前序遍历结果相同,森林的后序遍历和二叉树的中序遍历结果相同。

当以二叉链表作树的存储结构时,树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

四、二叉树的应用

1、BST(二叉排序树/二叉查找树/二叉搜索树)

1)定义

二叉排序树:又称为二叉查找树、二叉搜索树。它或者是一棵空树,或者是具有下列性质的二叉树。

二叉排序树利于插入和删除的实现。

2)操作

2、平衡二叉树

1)定义

2)失衡调整

3、堆

最大堆、最小堆

4、红黑树

把树中的节点定义为红、黑两种颜色,并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。

5、哈夫曼(Huffman)树和哈夫曼编码

1)赫夫曼树定义

赫夫曼树:带权路径长度 WPL 最小的二叉树称做赫夫曼树。

2)赫夫曼树构造

  1. 根据给定的 n 个权值 {$w_1,w_2,...,w_n$} 构成 n 棵二叉树的集合 F={ $T_1,T_2,...,T_n$},其中每棵二叉树 $T_i$ 中只有一个带权为 $w_i$ 根结点,其左右子树均为空。
  2. 在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
  3. 在 F 中删除这两棵树,同时将新得到的二叉树加入 F 中 。
  4. 重复 2 和 3 步骤,直到 F 只含一棵树为止。这棵树便是赫夫曼树。

3)赫夫曼编码

赫夫曼编码:对需要编码的字符集,统计各个字符出现的次数或频率,作为权值,构造赫夫曼树。规定赫夫曼树的做分支代表0,有分支代表1,从根节点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码。