1、国家教学资源库建设项目国家教学资源库建设项目单元单元4 4 树与二叉树树与二叉树2数据结构数据结构 教学目标教学目标【知识目标知识目标】l 理解树的逻辑结构和基本术语l 理解二叉树的递归定义，掌握二叉树的性质l 掌握二叉树的遍历，能确定遍历所得到的结点访问序列l 掌握二叉树的存储方法和二叉树的基本操作的算法l 掌握树和森林与二叉树之间的转换方法l 能根据给定的叶结点及其权值构造出相应的最优二叉树l 能根据最优二叉树构造对应的哈夫曼编码【能力目标能力目标】l 具有用树来描述现实世界、应用二叉树解决实际问题的能力l 具有恰当的选择二叉树作为数据的逻辑结构和存储结构的能力单元单元4 4 树与二叉树树
2、与二叉树3数据结构数据结构 引例描述引例描述文本文件的加密和解密文本文件的加密和解密 某公司有一份机密文件，是由英文字母（包括大小写）、英文逗号、英文句点、空格和回车换行等符号组成的文件名为Jimi.txt的文本文件。公司为保证文件不被泄密，要求技术人员将文件中的每个字符都用一个二进制位串进行加密，需要时能进行解密，但必须保证加密后的文件不要过大，且对加密的文件进行解密后与原文件必须完全一致。如果你是技术人员，你将如何按要求为公司的文件进行加密和解密呢？演示执行演示执行 单元单元4 4 树与二叉树树与二叉树4数据结构数据结构 一、树的递归定义一、树的递归定义 1.定义定义 树（Tree）是n(
3、n0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：有且仅有一个特定的称为根（Root）的结点；其余的结点可分为m(m0)个互不相交的有限子集Tl，T2，Tm，其中每个子集本身又是一棵树，并称其为根的子树（SubTree）。4.1 树的概念树的概念 知识储备知识储备单元单元4 4 树与二叉树树与二叉树5数据结构数据结构 2树的表示树的表示 树形图表示：结点用圆圈表示，结点名字写在圆圈旁或圆圈内，子树与其根之间用无向边来连接，如图4-1是树形图表示表示的树T1。嵌套集合表示法：用集合的包含关系描述树结构，如图4-2是树T1的嵌套集合表示。凹入表表示法：类似于书的目录。图图4-1 树
4、树T1的树形图表示的树形图表示ABCDEFIJGH图图4-2 树树T1的嵌套集合表示的嵌套集合表示EIJGHABDCF单元单元4 4 树与二叉树树与二叉树6数据结构数据结构 二、树结构的基本术语二、树结构的基本术语 1结点的度结点的度 结点的度：一个结点拥有子树的个数称为该结点的度。树的度：该树中结点的最大度数称为该树的度。叶子结点：度为零的结点称为叶子结点或终端结点。分支结点：度不为零的结点称分支结点或非终端结点。即除叶子结点外的结点均为分支结点。内部结点：除根结点之外的分支结点统称为内部结点。开始结点：根结点又称为开始结点。【示例示例】图4-1表示的树T1中结点A的度为3，其它结点的度都为
5、2或0。【示例示例】图4-1表示的树T1的度为3。【示例示例】图4-1表示的树T1中结点C、E、G、H、I、J都是叶子结点。【示例示例】图4-1表示的树T1中结点A、B、D、F都是分支结点。【示例示例】图4-1表示的树T1中结点A是开始结点。单元单元4 4 树与二叉树树与二叉树7数据结构数据结构 2结点之间的关系结点之间的关系孩子（Child）结点：树中某个结点的子树的根称为该结点的孩子结点。双亲（Parent）结点：孩子结点的根称为该结点的双亲。兄弟结点：同一个双亲的孩子互称为兄弟结点。堂兄弟：在后面介绍。祖先和子孙：在后面介绍。【示例示例】图4-1表示的树T1中结点B、C、D都是结点A的孩
6、子结点，结点E、F都是结点B的孩子结点，结点G、H都是结点D的孩子结点。【示例示例】图4-1表示的树T1中结点A是结点B、C、D的双亲结点，结点B是结点E、F的双亲结点，结点D是结点G、H的双亲结点。【示例示例】图4-1表示的树T1中结点B、C、D互为兄弟结点，结点E、F互为兄弟结点，而结点F和G非兄弟结点。单元单元4 4 树与二叉树树与二叉树8数据结构数据结构 3路径路径路径或道路：若树中存在一个结点序列k1,k2,kj,使得ki是ki+1的双亲(1ij)，则称该结点序列是从kl到kj的一条路径或道路。路径的长度：指路径所经过的边的数目。注意：注意：若一个结点序列是路径，则在树的树形图表示中
7、，该结点序列“自上而下”地通过路径上的每条边。从树的根结点到树中其余结点均存在一条惟一的路径。祖先和子孙：若树中结点k到ks存在一条路径，则称k是ks的祖先，ks是k的子孙。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。约定：约定：结点k的祖先和子孙不包含结点k本身。【示例示例】图4-1表示的树T1中结点序列ABFI是结点A到I的一条路径，因为自上而下A是B的双亲，B是F的双亲，F是I的双亲。该路径的长度为3。而结点B和G之间不存在路径，因为既不能从B出发自上而下地经过若干个结点到达G，也不能从G出发自上而下地经过若干个结点到达B。
8、单元单元4 4 树与二叉树树与二叉树9数据结构数据结构 4结点的层数和树的深度结点的层数和树的深度结点的层数：根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。堂兄弟：双亲在同一层的结点互为堂兄弟。树的深度：树中结点的最大层数称为树的深度。注意：要弄清结点的度、树的度和树的深度的区别。5有序树和无序树有序树和无序树若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树；否则称为无序树。若不特别指明，一般讨论的树都是有序树。6森林（森林（Forest）森林是m(m0)棵互不相交的树的集合。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。单元单元4 4
9、 树与二叉树树与二叉树10数据结构数据结构 三、树型结构的逻辑特征三、树型结构的逻辑特征 1树中任一结点都可以有零个或多个直接后继结点，但至多只能有一个直接前驱结点。2树中只有根结点无前驱，它是开始结点；叶结点无后继，它们是终端结点。3祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。4有序树中，同一组兄弟结点从左到右有长幼之分。对这一关系加以延拓，规定若k1和k2是兄弟，且k1在k2的左边，则kl的任一子孙都在k2的任一子孙的左边，那么就定义了树中结点之间的横向次序。树中结点之间的逻辑关系是“一对多”的关系，树是一种非线性的结构。单元单元4 4 树与二叉树树与二叉树11数据
10、结构数据结构【课堂实践【课堂实践4-1】已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，求该树中的叶子结点数。提示：分别从树的结点总数和树的孩子结点总数两个角度考虑。做做一一做做单元单元4 4 树与二叉树树与二叉树12数据结构数据结构 一、二叉树的定义一、二叉树的定义 1.二叉树的递归定义二叉树的递归定义 二叉树（Binary Tree）是n(n0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。2二叉树的五种基本形态二叉树的五种基本形态 二叉树可以是空集；可以有空的左子树或空的右子树；或者左、右子树皆为空。
11、二叉树的五种基本形态如图4-3。4.2 二叉树及其性质二叉树及其性质 图图4-3 二叉树的五种基本形态二叉树的五种基本形态(a)(b)(c)(d)(e)单元单元4 4 树与二叉树树与二叉树13数据结构数据结构 二、二、二叉树的性质二叉树的性质1性质性质性质1：二叉树第i层上的结点数目最多为2i-1(i1)个。性质2：深度为k的二叉树至多有2k-1(k1)个结点。性质3：在任意一棵非空二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。性质性质3说明：说明：在任意非空二叉树中叶子结点数总比度为2的结点数多1个。证明：证明：假设树非空，用数学归纳法证明。当i=1时，因为第1层
12、上只有一个根结点，而2i-1=20=1。所以命题成立。假设对所有的j(1j2k-1-1。另一方面，由性质2知：深度为k的二叉树至多有2k-1(k1)个结点，因此，n2k-1，即：2k-1-ln2k-1，由此可推出：2k-1n2k，取对数后有：k-1lgnk又因k-1和k是相邻的两个整数，故有。由此即得1lgn1)nlg（另外，由2k-1-ln2k-1得2k-11，则ki的双亲编号为i/2；若i=1，则ki是根结点，无双亲。（ii）若2in，则ki的左孩子的编号是2i；若2in，则ki无左孩子，因此也无右孩子，即ki必定是叶子。因此完全二叉树中编号in/2的结点必定是叶结点。（iii）若i为奇数
13、且不为1，则ki是结点ki/2的右孩子，ki的左兄弟的编号是i-1；若i=1或i为偶数，则ki无左兄弟。（iv）若i为偶数且小于n，则ki是结点ki/2的左孩子，ki的右兄弟的编号是i+1；若i=n或i为奇数，则ki无右兄弟。由此可知，完全二叉树中结点的编号序列，完全反映了结点之间的逻辑关系。单元单元4 4 树与二叉树树与二叉树19数据结构数据结构【课堂实践【课堂实践4-3】已知一棵完全二叉树含1000个结点，分别求该二叉树的度为2的结点数、度为1的结点数和叶子结点数。做做一一做做单元单元4 4 树与二叉树树与二叉树20数据结构数据结构（2）完全二叉树的顺序存储）完全二叉树的顺序存储 将完全二
14、叉树中所有结点按编号顺序依次存储在一个向量bt0n中。其中：bt1n用来存储结点，bt0不用或用来存储结点数目。说明：说明：完全二叉树的顺序存储结构既简单又节省存储空间；按这种方法存储的完全二叉树，向量元素bti的下标i就是对应结点的编号。【示例】【示例】图4-7所示的完全二叉树的顺序存储结构如图4-8。图图4-8 4-8 完全二叉树完全二叉树BT3BT3的顺序存储的顺序存储BT3BT3A AB BC CD DE EF FG GH HI IJ JK KL L1212下标下标0 01 12 23 34 45 56 67 78 89 9101011111212单元单元4 4 树与二叉树树与二叉树2
15、1数据结构数据结构 2一般二叉树的顺序存储一般二叉树的顺序存储（1）具体方法）具体方法将一般二叉树添上一些“虚结点”，使其成为完全二叉树；为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号；将结点按编号存入向量对应分量，其中“虚结点”用表示。（2）二叉树的顺序存储结构的优缺点：）二叉树的顺序存储结构的优缺点：优点是存储结构简单；缺点是可能浪费大量的存储空间。在最坏的情况下，一个深度为k的且只有k个结点的右单支树，需要2k-1个结点的存储空间，浪费了2k-1-k个存储空间。【示例】【示例】如图4-9的三个结点的添加上4个虚结点右单支树的存储结构如图4-10。图图4-
16、9 添加虚结点右单支树添加虚结点右单支树1BAC372456AB3C01234567下标下标bt图图4-10 右单支树的顺序存储结构右单支树的顺序存储结构单元单元4 4 树与二叉树树与二叉树22数据结构数据结构（3）二叉树顺序存储结构的描述）二叉树顺序存储结构的描述#define MAXSIZE 50 /设置二叉树的最大结点数typedef char DataType;/定义结点类型typedef struct/定义二叉树结构DataType btMAXSIZE;/存放二叉树的结点int num;/存放二叉树的结点数SeqBT;注：注：如果使用元素bt0存放二叉树的结点数，成员num可省略或不
17、定义结构而只定义数组。单元单元4 4 树与二叉树树与二叉树23数据结构数据结构 二二、二叉树的链式存储结构、二叉树的链式存储结构1结点的结构：结点的结构：二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构如图4-11。2结点的类型描述结点的类型描述说明：说明：定义新类型BinTree为指向BinTNode类型结点的指针类型，用于定义指向根结点的指针。图图4-11 结点的结构结点的结构 lchild data rchildtypedef char DataType;/定
18、义结点数据域类型typedef struct node/定义结点结构DataType data；struct node*lchild，*rchild；/左右孩子指针BinTNode；/结点类型typedef BinTNode*BinTree；单元单元4 4 树与二叉树树与二叉树24数据结构数据结构 3二叉树的链式存储结构二叉树的链式存储结构二叉链表二叉链表 在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点（即根结点）的BinTree型头指针（即根指针）root，就构成了二叉树的链式存储结构，并将其称为二叉链表。说明：说明：一个二叉链表由根指针root惟一确定。若二叉树为
19、空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。证明：证明：因为二叉树中结点总数n等于0度结点数n0、1度结点数n1和2度结点数n2之和：n=n0+n1+n2 由二叉树的性质3：n0=n2+1，所以，n1+2n2=n-1。而在二叉链表中，度为1的结点有一个指针域不空，度为2的结点的两个指针域都不空，即n个结点的二叉链表中共有n1+2n2个指针域不空，即n-1个指针域不空，分别指向左右孩子。因此，其余的n+1个指针域为空。【示例示例】如图4-12的二叉树BT4的二叉
20、链表如图4-13。图图4-12 二叉树二叉树BT4ABCDEFGH图图4-13 二叉树二叉树BT4的二叉链表的二叉链表rootABFEDHGC单元单元4 4 树与二叉树树与二叉树25数据结构数据结构 4带双亲指针的二叉链表带双亲指针的二叉链表三叉链表三叉链表 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表，也称为三叉链表。【示例示例】如图4-12的二叉树BT4的三叉链表如图4-14。图图4-12 二叉树二叉树BT4ABCDEFGH图图4-14 二叉树二叉树BT4的三叉链表的三叉链表GHFECDBAroot单元单元4 4 树与
21、二叉树树与二叉树26数据结构数据结构【课堂实践【课堂实践4-4】画出如图4-15的二叉树BT5的二叉链表和三叉链表的存储结构。做做一一做做图图4-15 二叉树二叉树BT5ABCDEGFH单元单元4 4 树与二叉树树与二叉树27数据结构数据结构 遍历（遍历（Traversal）：）：是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。一、遍历方案一、遍历方案1遍历方案：遍历方案：由于一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：访问结点本身(N)；遍历该结点的左子树(L)；遍历该结点
22、的右子树(R)。以上三种操作有六种遍历方案：NLR、LNR、LRN、NRL、RNL、RLN。由于前三种次序与后三种次序对称，所以只讨论先左后右的前三种次序。4.4 二叉树的遍历二叉树的遍历 单元单元4 4 树与二叉树树与二叉树28数据结构数据结构 2三种遍历的命名三种遍历的命名前（先）序遍历NLR：访问结点的操作发生在遍历其左右子树之前，又称为先根遍历。中序遍历LNR：访问结点的操作发生在遍历其左右子树之中（间），又称为中根遍历。后序遍历LRN：访问结点的操作发生在遍历其左右子树之后，又称为后根遍历。3遍历规则及算法遍历规则及算法中序遍历的递归算法若二叉树非空，则依次执行如下操作：（i）遍历左
23、子树；（ii）访问根结点；（iii）遍历右子树。中序遍历的递归算法：void InOrder(BinTree T)if(T)/如果二叉树非空InOrder(T-lchild);/遍历左子树printf(%c，T-data)/访问根结点InOrder(T-rchild);/遍历右子树 单元单元4 4 树与二叉树树与二叉树29数据结构数据结构 先序遍历的递归算法若二叉树非空，则依次执行如下操作：（i）访问根结点；（ii）遍历左子树；（iii）遍历右子树。先序遍历的递归算法：后序遍历得递归算法若二叉树非空，则依次执行如下操作：（i）遍历左子树；（ii）遍历右子树；（iii）访问根结点。后序遍历的递归
24、算法：void PreOrder(BinTree T)if(T)/如果二叉树非空printf(c，T-data);/访问根结点PreOrder(T-lchild);/遍历左子树PreOrder(T-rchild);/遍历右子树 void PostOrder(BinTree T)if(T)/如果二叉树非空 PostOrder(T-lchild);/遍历左子树PostOrder(T-rchild);/遍历右子树printf(c，T-data);/访问根结点 单元单元4 4 树与二叉树树与二叉树30数据结构数据结构 一、遍历序列一、遍历序列1中序序列：中序序列：中序遍历二叉树时，按对结点的访问次序形
25、成的结点序列称为中序序列。说明：说明：在中序遍历序列中，根结点左边的结点在根的左子树上，根结点右边的结点在根的右子树上。2先序序列：先序序列：先序遍历二叉树时，按对结点的访问次序形成的结点序列称为先序序列。说明：说明：在先序遍历序列中，最左边的结点是根结点。3后序序列：后序序列：后序遍历二叉树时，按对结点的访问次序形成的结点序列称为后序序列。说明：说明：在后序遍历序列中，最右边的结点是根结点。【示例示例】对如图4-12的二叉树BT4，求出它的中序遍历、先序遍历和后序遍历序列。单元单元4 4 树与二叉树树与二叉树31数据结构数据结构【课堂实践【课堂实践4-5】写出如图4-15的二叉树T2的先序遍
26、历序列、中序遍历序列和后序遍历序列。做做一一做做图图4-15 二叉树二叉树BT5ABCDEGFH单元单元4 4 树与二叉树树与二叉树32数据结构数据结构 4确定二叉树确定二叉树 已知中序遍历序列和先序遍历序列或后序遍历序列可以确定一棵二叉树。具体方法：具体方法：先根据先序遍历序列确定该二叉树的根，再根据中序遍历序列确定根的左子树和右子树上的结点，而对于左子树和右子树可用同样的方法确定子树的根和其左、右子树上的结点，这样便可确定该二叉树。【示例示例】已知一棵二叉树的中序遍历序列和先序遍历序列分别是：BGDAEHCF和ABDGCEHF，画出这棵二叉树。单元单元4 4 树与二叉树树与二叉树33数据结
27、构数据结构【课堂实践【课堂实践4-6】已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF，画出该二叉树的二叉链表存储表示，并写出该二叉树的后序序列。做做一一做做单元单元4 4 树与二叉树树与二叉树34数据结构数据结构 一、二叉链表的建立一、二叉链表的建立1基本思想基本思想 基于先序遍历建立二叉链表，即以二叉树的先序遍历序列为输入建立二叉链表。注：注：先序遍历序列中须加入虚结点以示空指针的位置。如图4-15的二叉树BT5的带虚结点的先序序列为：ABDGCEHF。2建立算法建立算法 以二叉树的先序序列为输入建立二叉链表，假设虚结点输入时以空格字符表示，算法如下：4.5 二叉树的
28、基本操作二叉树的基本操作 void CreateBinTree(BinTree*T)/建立二叉链表。T是指向根指针的指针char ch；if(ch=getchar()=)*T=NULL;/读入空格，将相应指针置空 else/读入非空格*T=(BinTNode*)malloc(sizeof(BinTNode);(*T)-data=ch；CreateBinTree(&(*T)-lchild);/建立左子树CreateBinTree(&(*T)-rchild);/建立右子树 单元单元4 4 树与二叉树树与二叉树35数据结构数据结构 二、二叉链表的基本操作二、二叉链表的基本操作1计算二叉树深度计算二叉
29、树深度分析：分析：如果二叉树BT为空，即BT=NULL，则BT的深度为0；如果二叉树BT不空，则分别计算其左、右子树的深度，左、右子树深度的最大者加1就是该二叉树的深度。算法步骤：算法步骤：如果二叉树BT为空，返回0，否则执行；分别计算BT的左右子树的深度；如果左子树深度大，返回左子树深度+1，否则返回右子树深度+1。递归算法：递归算法：int BinTreeDepth(BinTNode*BT)int leftdep,rightdep;/分别记录左右子树深度if(BT=NULL)return(0);elseleftdep=BinTreeDepth(BT-lchild);rightdep=Bin
30、TreeDepth(BT-rchild);if(leftdeprightdep)return(leftdep+1);elsereturn(rightdep+1);单元单元4 4 树与二叉树树与二叉树36数据结构数据结构 2计算双孩子结点个数计算双孩子结点个数分析：分析：如果二叉树BT为空，即BT=NULL，则BT无双孩子；如果二叉树BT不空，但左、右子树至少有一个为空，即BT-lchild=NULL|BT-rchild=NULL，此时左、右子树双孩子结点个数的和就是该二叉树的双孩子结点的个数；如果二叉树BT不空，且左、右子树都不空，此时左、右子树双孩子结点个数的和再加1就是该二叉树的双孩子结点
31、的个数。算法步骤：算法步骤：如果二叉树BT为空，返回0；如果左右子树至少有一个为空，返回左子树双孩子结点数与右子树双孩子结点数之和；如果左右子树都不空，返回左子树双孩子结点数与右子树双孩子结点数之和+1。递归算法：递归算法：int TwoSonCount(BinTNode*BT)if(BT=NULL)return(0);else if(BT-lchild=NULL|BT-rchild=NULL)return(TwoSonCount(BT-lchild)+TwoSonCount(BT-rchild);elsereturn(TwoSonCount(BT-lchild)+TwoSonCount(BT
32、-rchild)+1);单元单元4 4 树与二叉树树与二叉树37数据结构数据结构 3计算结点总数计算结点总数分析：分析：如果二叉树BT为空，即BT=NULL，则BT无结点；如果二叉树BT不空，则左、右子树结点的个数之和加1就是该二叉树的结点的个数。算法步骤：算法步骤：如果二叉树BT为空，返回0；如果二叉树BT不空，返回左子树结点数与右子树结点数之和加1。递归算法：递归算法：int NodeCount(BinTNode*BT)if(BT=NULL)return(0);elsereturn(NodeCount(BT-lchild)+NodeCount(BT-rchild)+1);单元单元4 4 树
33、与二叉树树与二叉树38数据结构数据结构【课堂实践【课堂实践4-7】用递归方法分别求二叉树的叶子结点数和单孩子结点个数。做做一一做做单元单元4 4 树与二叉树树与二叉树39数据结构数据结构 一、树、森林到二叉树的转换一、树、森林到二叉树的转换1将树转换为二叉树将树转换为二叉树转换方法：转换方法：加线：加线：在所有兄弟结点之间加一连线；去线：去线：对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线；调整：调整：按树的层次进行调整，将原来的右兄弟变成其右孩子，原来的无兄弟结点变成左孩子。4.6 树和森林树和森林【示例】将如图4-17(a)的树T2转换为二叉树的全过程如下：图图4-17(
34、a)树树T2ABCDEFGHI图图4-17(b)第一步第一步 加线加线ABCDEFGHI图图4-17 (c)第二步第二步 去线去线ABCDEFGHI图图4-17 (d)第三步第三步 调整调整ABCDEFGHI单元单元4 4 树与二叉树树与二叉树40数据结构数据结构 2将一个森林转换为二叉树将一个森林转换为二叉树转换方法：转换方法：树转换为二叉树：树转换为二叉树：将森林中的每棵树转换为二叉树；连接根结点：连接根结点：再将各二叉树的根结点视为兄弟从左至右连在一起；调整：调整：按树的层次进行调整，将原来的右兄弟变成其右孩子，原来的无兄弟结点变成左孩子。【示例】将如图4-18(a)的森林F1转换为二叉
35、树的全过程如下：第1步：将森林F1中的各棵树转换为二叉树，如图4-18(b)；图图4-18(b)第一步第一步 将各树转换为二叉树将各树转换为二叉树ABCDEFIJKGH图图4-18(a)森林森林F1ABCDEFIJKGH第2步：连接各二叉树的根结点，如图4-18(c)；图图4-18(c)第二步第二步 连接根结点连接根结点ABCDEFIJKGH第3步：按树的层次进行调整，调整为二叉树，如图4-18(d)。图图4-18(d)第三步第三步 调整调整IJKGHABCDEF单元单元4 4 树与二叉树树与二叉树41数据结构数据结构 3二叉树到树、森林的转换二叉树到树、森林的转换转换方法：转换方法：加线：加
36、线：在左孩子结点的双亲与左孩子结点的右孩子、右孩子的右孩子等等之间加一连线；去线：去线：去掉所有双亲与右孩子之间的连线；调整：调整：按树的层次进行调整，将原来根结点的右孩子、右孩子的右孩子等等变成森林中树的根，其它结点的右孩子、右孩子的右孩子等等变成兄弟。【示例】将如图4-19的二叉树BT6转换为树或森林的全过程如图4-19(a)-(c)：第1步：加线，如图4-19(a)；图图4-19 二叉树二叉树BT6GJCFABEHDI图图4-19(a)第一步第一步 加线加线GJCFABEHDI第2步：去线，如图4-19(b)；第3步：调整，如图4-19(c)。图图4-19(b)第二步第二步 去线去线GJ
37、CFABEHDI图图4-19(c)第三步第三步 调整调整GABEHDJCFI单元单元4 4 树与二叉树树与二叉树42数据结构数据结构 二、树的存储结构二、树的存储结构1双亲链表表示法双亲链表表示法 该表示法用向量表示结点，并用一个整型量parent指示其双亲的位置，称为指向其双亲的指针。双亲链表向量表示的描述2孩子链表表示法孩子链表表示法 该表示法为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。孩子链表表示的描述 3孩子兄弟链表表示法孩子兄弟链表表示法结点的结构：结点的结构：与二叉链表类似，在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指
38、针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示。孩子兄弟链表表示的描述#define MaxTreeSize 100/定义向量空间的容量typedef char DataType；/定义结点数据域类型typedef struct/定义结点DataType data；/定义结点数据域int parent；/双亲指针，指示双亲的位置PTreeNode；typedef struct/定义链表PTreeNode nodesMaxTreeSize;int n；/结点总数PTree；PTree T；/T是双亲链表【示例】如图4-20的树T3的双亲链表表示为图4-21。
39、图图4-21 树树T3的双亲链表的双亲链表dataparentABCDEFGHI下标012345678MaxTreeSize-100011133-1图图4-20 树树T3GCFABEHDI#define MaxTreeSize 100/定义向量空间的容量typedef char DataType；/定义结点数据域类型typedef struct Cnode/孩子链表结点int child；/孩子结点在向量中对应的序号struct CNode*next；CNode；typedef struct DataType data；/存放树中结点数据CNode*firstchild；/孩子链表的头指针PT
40、Node；typedef structPTNode nodesMaxTreeSize；int n，root；/n为结点总数，root指出根在向量中的位置CTree；CTree T；/T为孩子链表表示【示例】如图4-20的树T3的孩子链表表示如图4-22。图图4-22 树树T3的孩子链表的孩子链表013245678rootdata12345678firstchildnotesIHGFEDCBAtypedef char DataType;/定义结点数据域类型typedef struct node/定义结点结构DataType data;struct node*leftmostchild,*righ
41、tsibling;CSTNode;/结点类型CSTNode*T;/指向树的开始结点的指针【示例】如图4-20的树T3的孩子兄弟链表表示为图4-23。图图4-23 树树T3的孩子兄弟链表的孩子兄弟链表ABECDFGHIT3单元单元4 4 树与二叉树树与二叉树43数据结构数据结构 三、树的遍历三、树的遍历 设树T的根结点是R，根的子树从左到右依次为T1，T2，Tk。树的遍历分为先序遍历和后序遍历两种。1树树T的先序遍历规则的先序遍历规则若树T非空，则 访问根结点R；依次先序遍历根R的各子树T1，T2，Tk。2树树T的后序遍历规则的后序遍历规则若树T非空，则依次后序遍历根R的各子树T1，T2，Tk；
42、访问根结点R。说明：说明：前序遍历一棵树恰好等价于前序遍历该树对应的二叉树；后序遍历一棵树恰好等价于中序遍历该树对应的二叉树。【示例】图4-17(a)的树T2转换为二叉树如图4-17(d)树T2的先序序列为：ABEFGCHDI。转换得到的二叉树的先序序列为：ABEFGCHDI。树T2的后序序列为：EFGBHCIDA。转换得到的二叉树的中序序列为：EFGBHCIDA。转换得到的二叉树的后序序列为：GFEHIDCBA。显然，前序遍历一棵树恰好等价于前序遍历该树对应的二叉树，后序遍历一棵树恰好等价于中序遍历该树对应的二叉树。单元单元4 4 树与二叉树树与二叉树44数据结构数据结构【课堂实践【课堂实践
43、4-8】已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH，画出该森林所对应的二叉树，并画出该森林。做做一一做做单元单元4 4 树与二叉树树与二叉树45数据结构数据结构 一、哈夫曼树（一、哈夫曼树（Huffman Tree）的有关概念）的有关概念1树的路径长度：树的路径长度：从根结点到树中每一结点的路径长度之和称为树的路径长度。说明：说明：在结点数目相同的二叉树中，完全二叉树的路径长度最短。2树的带权路径长度树的带权路径长度结点的权（结点的权（Weight）：）：赋予树中某结点的一个有某种意义的实数，称为该结点的权。结点的带权路径长度：结点的带权路径长度：结点到树根之
44、间路径长度与该结点上权的乘积，称为结点的带权路径长度。树的带权路径长度（树的带权路径长度（Weighted Path Length of Tree）：）：树中所有叶结点的带权路径长度之和，称为树的带权路径长度，亦称为树的代价。记为：4.7 哈夫曼树及其应用哈夫曼树及其应用 niiilwWPL1 ，n表示叶子结点的数目，wi和li表示叶结点ki的权值和根到ki之间的路径长度。单元单元4 4 树与二叉树树与二叉树46数据结构数据结构 3哈夫曼树：哈夫曼树：在权为wl,w2,wn的n个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为哈夫曼树或最优二叉树。说明：说明：叶子上的权值均
45、相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树；哈夫曼树中，权越大的叶子离根越近；哈夫曼树的形态不唯一，但WPL值相同且最小。【示例】给定5个叶子结点a，b，c，d和e，分别带权7，6，12，15和10。可构造出许多棵二叉树，如图4-24所示的是其中两棵二叉树。它们的带权路径长度分别为：(a)WPL=7*2+6*3+12*3+15*3+10*3=143(b)WPL=7*3+6*3+12*2+15*2+10*2=113 实际上图(b)的二叉树是所有以a，b，c，d和e为叶子的二叉树中WPL最小的二叉树，它就是哈夫曼树。acbed图图4-24 两棵二叉树两棵二叉树(a)(b)
46、cdbae单元单元4 4 树与二叉树树与二叉树47数据结构数据结构 二、哈夫曼树的构造二、哈夫曼树的构造1哈夫曼算法哈夫曼算法基本思想：基本思想：根据给定的n个权值wl,w2,wn构成n棵二叉树的森林F=T1,T2,Tn，其中每棵二叉树Ti中都只有一个权值为wi的根结点，其左右子树均空；在森林F中选出两棵根结点权值最小的树（当这样的树不止两棵树时，可以从中任选两棵），将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子（谁左，谁右无关紧要），将这两个孩子的权值之和作为新树根的权值；对新的森林F重复，直到森林F中只剩下一棵树
47、为止。这棵树便是哈夫曼树。用哈夫曼算法构造哈夫曼树的过程：用哈夫曼算法构造哈夫曼树的过程：给定5个叶子结点a，b，c，d和e，分别带权7，6，12，15和10。用哈夫曼算法构造哈夫曼树的过程如下：第第1步：步：根据给定的5个权值7，6，12，15和10构成5棵二叉树的森林F=T1,T2,T3,T4,T5，如图4-25(a)；第第2步：步：在森林F中选出两棵根结点权值最小的树，将这两棵树合并成一棵新树，并添加到森林中，得到新的森林，如图4-25(b)；图图4-25(a)76121510abcde图图4-25(b)121510cde1376ab第第3步：步：重复第2步，进行第二次合并，得到新的森林
48、，如图4-25(c)；第第4步：步：重复第2步，进行第三次合并，得到新的森林，如图4-25(d)；图图4-25(c)15d1376ab221210ce图图4-25(d)221210ce15d1376ab28第第5步：步：重复第2步，进行第四次合并，由于森林F中只剩下一棵树，所以它就是哈夫曼树，如图4-25(e)。图图4-25(e)221210ce15d1376ab2850单元单元4 4 树与二叉树树与二叉树48数据结构数据结构 三、哈夫曼树算法的实现三、哈夫曼树算法的实现 1哈夫曼树结点的结构哈夫曼树结点的结构 哈夫曼树的结点用一个大小为2n-1的向量来存储，每个结点包含权值域weight、指
49、示左右孩子结点在向量中下标的整型量lchild和rchild、指示双亲结点在向量中下标的整型量parent。结点结构如图4-26。2哈夫曼树的描述哈夫曼树的描述注意：注意：因为C数组的下界为0，故用-1表示空指针。树中某结点的lchild、rchild和parent不等于-1时，它们分别是该结点的左、右孩子和双亲结点在向量中的下标。这里设置parent域有两个作用：其一是使查找某结点的双亲变得简单；其二是可通过判定parent的值是否为-1来区分根与非根结点。weight lchild rchild parent图图4-26 结点结构结点结构#define n 100/叶子数目#define
50、m 2*n-1/树中结点总数typedef struct /定义结点类型float weight;/定义权值域int lchild,rchild,parent;/定义左右孩子及双亲指针HTNode;typedef HTNode HuffmanTreem;/*定义HuffmanTree为新的类型标识符，用该标识符定义的变量是具有HTNode类型的含有m个元素的向量。*/单元单元4 4 树与二叉树树与二叉树49数据结构数据结构 3哈夫曼树哈夫曼树T算法实现的步骤算法实现的步骤（1）初始化：）初始化：将T0m-1中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。（2）输入：）输入：读入
