数据结构第6章.

1第六章树和二叉树复习一、二叉树二叉树的定义、存储二叉树的性质线索化二叉树二、树和森林树的定义、存储树和森林的遍历树和森林与二叉树之间的转换三、哈夫曼树哈夫曼树定义、建立哈夫曼编码2本章学习要求掌握：树和二叉树的性质，有关术语及基本概念掌握：二叉树的两种存储方法，重点是链式存储掌握：各次次序的遍历算法，能灵活遍历算法实现二叉树的各种运算掌握：几种建立二叉树的方法了解：二叉树的线索化，了解在各种线索树中查找给定结点的前趋和后继的方法了解：树、森林和二叉树之间的转换方法了解：树的各种存储结构及其特点；树和森林的两种次序的遍历掌握：哈夫曼树的基本概念及哈夫曼编码的方法3一、二叉树或空，或由根和由互不相交的左子树、右子树构成。1、二叉链表第六章树和二叉树abcdfeabcedfg2、顺序存储gabc##de####fg##4特征：1.叶子结点只可能在层次最大的两层上出现2.任一结点，若其右分支下的子孙的最大层次为k，则其左分支下的最大层次为K或K+1.3.完全二叉树最多只有一个度为1的结点满二叉树和完全二叉树满二叉树：深度为k且有2k-1个结点的二叉树。可以对满二叉树进行编号。编号方式为：根编号为1，从上到下，从左到右。189101112131415452673满二叉树完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1到n的结点一一对应时，称为完全二叉树。189101112452673完全二叉树5练习1（第六章课后习题四、2）已经某完全二叉树有100个结点，试求该二叉树的叶子数解：设度为0的结点n0个数为x，则度为2的结点个数n2为x-1且完全二叉树的度为1的结点个数为0或1根据题意得：n0+n1+n2=100即2x-1+n1=100所以,n1=1x=50可得：叶子数为50个练习2（第六章课后习题四、5）已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树，并指出结点最多的那棵树的叶子数解：完全二叉树的叶子只会出现在最下面两层6性质1：在二叉树的第i(i0)层上至多有2i-1个结点。性质2：深度为k的二叉树中至多有2k-1个结点(k0)。性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1。性质4：有n个结点的完全二叉树的深度为+1。2、二叉树的性质7性质5：如果对一棵有n个结点的完全二叉树按层序从1开始编号，则对任一结点(i=i=n),有：(1)如果i=1，则结点i是二叉树的根结点；如果i1,则其双亲结点是[i/2]。(2)如果2i=n,则结点i的左孩子是结点2i；否则结点i无左孩子。(3)如果2i+1=n,则结点i的右孩子是结点2i+1；否则结点i无右孩子。832个结点的完全二叉树，从根开始，按层次从左到右用1-32编号。请回答：（1）它共有多少层？（2）各层最左边的结点的编号是多少？（3）编号为6的结点的左孩子的编号是多少？它的右孩子呢？（4）编号为16的结点的左孩子的编号是多少？它的右孩子呢？（5）对于编号为8的结点，它的父结点的编号是多少？编号为13的结点呢？编号为1的结点呢？练习39二叉树的遍历：按某条搜索路径访问二叉树中每一个结点，使得每个结点被访问一次且仅被访问一次。遍历方法有4种：先序遍历，中序遍历，后序遍历，层次遍历。3、二叉树的遍历10先序遍历二叉树：（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树先序遍历序列：abcdfge1234567abcdfge11中序遍历二叉树：（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树中序遍历序列：bafgdceabcdfge123456712后序遍历二叉树：（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点后序遍历序列：bgfdecaabcdfge123456713abcdfge1234567层次遍历二叉树：按层次（1-k层)，每层从左到右依次访问二叉树中的每一个结点。层次遍历序列：abcdefg14练习4已知二叉树先序遍历序列是:abcdefg;中序遍历序列是:cbdaefg;（1）画出该二叉树;（2）写出后序遍历序列（1）（2）写出后序遍历序列：cdbgfeaabcdefg12345671515ltag=0：lchild指示该结点的左孩子ltag=1：lchild指针该结点的前趋。rtag=0：rchild指示该结点的右孩子rtag=1：rchild指针该结点的后继。有线索标志的二叉树4线索二叉树16BACEDGFroot先序线索二叉树NULL先序序列：ABDEGCF17BACEDGFroot中序线索二叉树NULLNULLIH中序序列：DBGIEHACF18BACEDGFroot后序线索二叉树HILK后序序列：IDGHEBKLFCANULL1919ABCDEABDCET中序序列：BCAED00001111^11^中序线索二叉树20练习5设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABDFCEGH中序遍历序列：BFDAGEHC（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。（3）将这棵二叉树转换成对应的树（或森林）。AEDCBHGFAEDCBHGFnullABFDCEHG21练习6：判断:1.二叉树是度为2的有序树。2.完全二叉树一定存在度为1的结点。3.对于有N个结点的二叉树，其高度为log2n。4．深度为K的二叉树中结点总数≤2k-1。5.（第六章课后习题三、9）一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。6．完全二叉树中，若一个结点没有左孩子，则它必是树叶。7.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。8.（第六章课后习题三、5）非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子9（第六章课后习题三、7）由先序和后遍历序列不能唯一确定一棵二叉树。10（三、2）二叉树中序线索化后，不存在空指针域。×××√√√×√√×22二、树1、树的定义树（Tree)是n(n=0)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个根结点；(2)除根结点外，其余结点可分为m(m=0)个互不相交的子树。2、树的存储1）、孩子兄弟表示法（用二叉链表存储）IACBHGFEDA∧BF∧∧D∧C∧E∧G∧H∧I∧∧23IACBHGFED9A0B1C1D2E2F3G5H5I50123456789dataparent01234567892ABCDEFGHI∧∧∧∧∧3∧45∧6∧789∧2）双亲表示法3）孩子表示法243、树与二叉树的转换树转换成二叉树：(左孩子-右兄弟)OacgbdefOacgbdef1.树的先根遍历与对应二叉树的先序遍历相同；2.树的后根遍历相当于对应二叉树的中序遍历；3.树没有中序遍历，因为子树无左右之分。254、树的遍历Oacgbdef先根遍历树：（1）访问根结点（2）先根遍历每一个子树先根遍历序列：oabcdfeg后根遍历树：（1）后根遍历每一个子树（2）访问根结点后根遍历序列：bafdecgo26练习7（第六章课后习题四、6）一个深度为L的满k叉树有如下性质，第L层上的结点都是叶子结点，其余各层上个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：（1）各层的结点数目是多少？（2）编号为n的结点的双亲结点（若存在）的编号是多少？（3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？（4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ki-1kn-1k(n-1)+i+1kn-1×k+1n≠n+1273、哈夫曼码：是一种前缀编码（即任一字符的编码都不是另一编码的前缀）。左支用0表示，右支用1表示。1、二叉树的带权路径长度WPL=wklkk=1其中，n:叶子结点个数，wk:第k个叶子的权，lk:第k个叶子到根的路径长度。2、Huffman树的构造方法（1）将{w1,w2,…….,wn}看成n个二叉树；（2）选择2个根结点的值最小的二叉树，构造1个新的二叉树；…….；直至剩1个树止。n三、Huffman树28(1)构造huffman树——以小值为左孩子(2)在哈夫曼树的所有左分支上编上号码“0”,右分支上编上号码“1”；(3)将根结点到每个叶子结点的路径编码串起来,得到字符集的哈夫曼编码。(4)WPL=(25+36+50)*2+(8+10+14)*4+(2+5)*5=385练习8设通信用8个字符abcdefgh,各字符使用的相对频率分别为25,36,2,5,8,14,10,50,设计哈夫曼编码,求该树的带树路径长度ＷＰＬ。a:2500b:3601c:210000d:510001e:81001g:101010f:141011h:501129练习9：判断:1．（第六章课后习题三、1）霍夫曼树的结点个数不能是偶数。2.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。3.哈夫曼树无左右子树之分。4．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。5．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。6．（第六章课后习题三、10）在哈夫曼树中，权值相同的叶结点都在同一层上7（第六章课后习题三、10）哈夫曼树是前缀编码。√√××√×√