数据结构---树

数据结构：

• 线性结构（线性表，栈，队列）
• 非线性结构:至少存在一个数据元素有不止一个直接前驱或后继(树,图等)

树的定义

树是n个数据元素的有限集(记为T)，对任意一棵树T有:
1．存在唯一 一个称为根的数据元素;
2．当n>1时，其它数据元素可分为m(m>0)个互不相交的有限集，其中每个集合T(i=1,2, ...,m)本身又是一棵树，并称树T是根的子树。

---

树的表示法

树的基本术语

• 树的结点:
  包含一个DE和指向其子树的所有分支。
• 结点的度:
  一个结点拥有的子树的个数,度为零的结点称为叶结点。
• 树的度:
  树中所有结点的度的最大值,含义:树中最大分支数为树的度。
• 结点的层次及树的深度:
  根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为层.树中结点的最大层次称为树的深度或高度。
  森林:
  是棵互不相的树的集合。森林与树概念相近,相互很容易转换。

---

树的基本运算

INITIATE(T)：初始化操作,创建一棵空树。
ROOT(T)：求根函数,求树T的根
ROOT(x)：求结点x所在树的根。
PARENT(T,x)：求双亲函数，在树T中求x的双亲。
CHILD(T,x,i)：求第i个孩子函数，在树T中求结点x的第i个孩子。
LSIBLING(T,x)：求左兄弟函数,在T中求x的左兄弟
RSIBLING(T,x)：求右兄弟函数,在树T中求x的右兄弟
------------------------------------------------------
CRT-TREE(X,F)：建树函数,建立以结点x为根,森林F为子树的树。
INS-CHILD(y,i,x)：插入子树操作,将x作为y的第i根子树。
DEL-CHILD(x,i)：删除子树操作,删除x的第i棵子树。
TRAVERSE(T)：遍历树操作,按顺序访问树T中各个结点。
CLEAR(T)：置空树操作，将树T置为空树。

二叉树

二叉树的定义

二叉树是结点数为0或每个结点最多只有左右两棵子树的树。
二叉树是一种特殊的树,它的特点是:

• 每个结点最多只有两棵子树,即不存结点度大于2的结点;
• 子树有左右之分,不能颠倒。

---

二叉树与度为2的树的区别

二叉树与度为2的树，二叉树可以是度为0，度为1，度为2的树，而度为2的树，必须度为2.
二叉树是有序树，两个孩子有严格的先后次序。而度为2的树，没有左右之分。

---

二叉树概念与性质

性质1：在二叉树的第i层上至多有个结点(i≥1)。
证明:用数学归纳法
1.当i=1,即第一层只有一个根结点,显然成立。
2假设对所有的j上述性质成立,即第j层上至多有个结点
3.要证明时,命题也成立。
由归纳假设:第i-1层上至多有个结点，又由于二叉树每个结点的度最大为2,所以第层上结点总数最多为第i-1层上最大结点数的2倍。即

---

性质2：深度为k的二叉树至多有个结点(k≥1)。（深度一定,二叉树的最大结点数也确定)
证明：深度为K的二叉树的最大结点数是二叉树中每层上结点的最大数之和。即

---

性质3.二叉树中,终端结点数n₀与度为2的结点数n₂有如下关系:

满二叉树

深度为k,且有2^k-1个结点的二叉树。
特点:
(1)每一层上结点数都达到最大
(2）度为1的结点n=0
结点层序编号方法:从根结点起从上到下逐层(层内从左到右）对二叉树的结点进行连续编号。

完全二叉树

深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时,称为完全二叉树。

完全二叉树的特点

(1）每个结点i的左子树的深度Lh;-其结点i的右子树的深度Rh_i;等于0或1,即叶结点只可能出现在层次最大或次最大的两层上。
(2）完全二叉树结点数n满足2^k-1-1<n≤2^k-1
(3）满二叉树一定是完全二叉树,反之不成立。

---

性质4：结点数为n的完全二叉树,其深度为
证明：设深度为k，则由性质2和完全二叉树定义有：
结点数n满足:
或写为
于是有:,
因为和均为整数。
显然有，故

性质5：在按层序编号的n个结点的完全二叉树中,任意一结点有:
(1)时,结点是树的根;1时,结点的双亲为结点.
(2)时,结点无左孩子,为叶结点;否则,结点的左孩子为结点i。
(3) 时,结点无右孩子;否则,结点的右孩子为结点。

性质5是二叉树顺序存储的理论基础

---

二叉树的存储结构

1、顺序存储结构

用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。

一般二叉树也按完全二叉树形式存储,没结点处用0表示。 这种存储结构适合于完全二叉树,既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置,但对一般二叉树，可能造成存储空间的浪费。

2、链式存储结构

设计不同的结点结构,可以构成不同的链式存储结构。常用的有:二叉链表、三叉链表。
线索链表用空链域存放指向前驱或后继的线索。

二叉链表不方便寻找双亲，必须遍历整个二叉树，因此有了三叉链表。

性质6.含有n个结点的二叉链表中,有n+1个空链域。
证明:空链域数=2n₀+n₁
因为n=n₀+n₁+n₂ (1)
又有no-n2+1 即-1= n2+n₀（2)
(1) - (2）得n+1-2n₀+n₁
故空链域数=n+1
性质6是二叉树线索化的理论基础。

---

遍历二叉树和线索二叉树

一、遍历二叉树

遍历二叉树是指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。

• 访问是一种抽象操作,是对结点的某种处理,例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。
• 一次遍历后,使树中结点的非线性排列,按访问的先后顺序变为某种线性排列。

---

• 遍历的次序:若设二叉树根为D，左子树为L，右子树为R,并限定先左后右，则有以下三种遍历次序:
  LDR 中序遍历; LRD 后序遍历; DLR 先序遍历

• 按照根的不同访问顺序确定，而左右子树的访问顺序在三种遍历中保持不变，先遍历左子树再遍历右子树。

---

1、中序遍历二叉树(递归)

中序遍历的前提：遍历的二叉树一定不可为空
算法思想：
若二叉树非空，则：①中序遍历左子树
②访问根结点 ③中序遍历右子树

2、后序遍历二叉树

算法思想：
若二叉树非空，则：①后序遍历左子树

②后序遍历右子树 ③访问根结点

3、先序遍历二叉树

算法思想：
若二叉树非空，则：①访问根结点

② 先序遍历左子树③先序遍历右子树

根结点先进栈,左结点紧跟根后面进栈,右结点在根出栈后入栈·每个结点都要进—次和出一次栈,并且总是访间栈顶元素,因此,算法正确,时间复杂度为 O(n)。

二、线索二叉树

通过一次遍历以后，记录下对该结点的访问序列，记录其任一结点前驱和后继，这样更有利于以后的便捷遍历。
分析：
n个结点有n-1个前驱和n-1个后继;一共有2n个链域，其中:n+1个空链域,n-1个指针域;
因此,必须用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。

---

线性二叉树的结构

• 称这种结点结构为线索链表;
• 其中指示前驱和后继的链域称为线索;
• 加上线索的二叉树称为线索二叉树;
• 对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
• 按中序遍历得到的线索二叉树称为中序线索二叉树;按先序遍历得到的线索二叉树称为先序线索二叉树;按后序遍历得到的线索二叉树称为后序线索二叉树;

遍历线索二叉树

有了线索二叉树，就容易遍历二叉树了.只要
(1)先找要遍历的第一个结点;
(2)然后依次找结点的后继;
(3）重复（2）直到其后继为头结点.
所有问题归为如何在线索二叉树中找结点的后继?

1、遍历中序线索二叉树

(1）中序线索二叉树中，找结点的后继算法。
算法思想:
对任意结点p，若rtag=1，则rchild指向该结点的后继;若rtag=0，则rchild指向该结点的右孩子。
此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点s(ltag=1),则s就是p的后继,即后继是中序遍历右子树时，访问的第一个结点;

2、遍历后续线索二叉树

(1）后序线索二叉树中，找结点的后继算法
算法思想:
对任意结点p,若p为二叉树的根，则无后继;
若p是双亲的右孩子、或是独生左孩子，则后继为双亲;
若p是有兄弟的左孩子，则后继为双亲的右子树上按后序遍历时，访问的第一个结点(叶结点)。

3、遍历先续线索二叉树

(1)先序线索二叉树中，找结点的后继算法
算法思想:
对任意结点p:若p有左孩子，则后继为左孩子;
若p无左孩子,有右孩子,则后继为右孩子;
若p无左孩子,也无右孩子，则后继为右线索;

---

习题：
1.试编写按层次遍历二叉树的算法.
2.试编写将二叉树中的所有结点的左右子树互换的算法.
3.试编写输出二叉树中所有叶结点的算法.

树和森林

一、树的存储结构

1.双亲表示法：

用一组地址连续的存储单元来存放树的结点,每个结点有两个域:
data域———存放结点的信息;

parent域——存放该结点双亲结点的位置.

2.孩子表示法：

每个结点的孩子用单链表存储，称为孩子链表。
n个结点可以有n个孩子链表(叶结点的孩子链表为空表）。

n个孩子链表的头指针用一个向量表示。

3.双亲孩子表示法：

在孩子表示法的头指针向量中，增加一项，用来表示该结点的双亲。

4.孩子兄弟表示法：

用二叉链表作为树的存储结构,每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。

二、森林、树与二叉树的对应关系

1、树与二叉树的对应关系

树与二叉树均可用二叉链表作为存储结构，因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。

树变为二叉树的方法

(1)在兄弟之间加一连线;
(2）对每一个结点，只保留它与第一个孩子的连线,去掉与其他孩子的连线;
(3）以树根为轴心,将整棵树顺时针旋转45度。
特点:根无右子树（共同点）

森林转换为二叉树的方法

• 将森林F={T₁,T₂… T_m}的各棵树分别转成二叉树BT₁, BT₂,…BT_m
• 将BT;n1作为BT;根结点的右子树（i=1,2,,m-1） ,得到一棵BT。

二叉树转换为森林的方法

• 将当前根结点和其左子树作为森林的一棵树,并将其右子树作为森林的其他子树;·
• 重复上面直到某结点的右子树为空。

哈夫曼树及其应用

哈夫曼树（Huffman）树是一类带权路径长度最短的树。

一、Huffman树(最优二叉树)

1、概念

• 两结点间的路径:从一结点到另一结点所经过的结点序列
• 路径长度:路径上的分支数

• 树的路径长度:从根到每一结点的路径长度之和!
  

  -树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。

完全二叉树是路径长度最短的二叉树。
考虑带权时:设树中有m个叶结点，每个叶结点带一个权值w_i且根到叶结点i的路径长度为L_i (i=1，2，.. m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。

WPL最小的二叉树称为最优二叉树(Huffman树)

一、构造Huffman树算法

(1)以权值分别为W₁,W₂ …W_n的n各结点，构成n棵二叉树T₁,T₂,. .．T.并组成森林F-{T1,T2. ..Tm},其中每棵二叉树T仅有一个权值为W的根结点;
(2)在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树,并且置新二叉树根结点权值为左右子树上根结点的权值之和(根结点的权值-左右孩子权值之和,叶结点的权值=W）
(3)从F中删除这两棵二叉树,同时将新二叉树加入到F中;(4)重复(2)．(3)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman树。

---

HT不唯一性,可能出现在:
(1）构造新树时,左、右孩子未作规定。
(2)当有多个权值相同的树,可作有候选树时，选择谁未作规定。

二、哈夫曼编码（Huffman树的应用)

1、问题的提出

通讯中常需要将文字转换成二进制字符串电文进行传送。文字→电文,称为编码。
反之，收到电文后要将电文转换成原来的文字，电文→文字，称为译码。