树与二叉树(java版)【优质课堂】

1、第五章 树与二叉树,1,优质课堂,教学内容,5.2 二叉树的基本概念,5.1 树的基本概念,5.4 哈夫曼树及哈夫曼编码,5.3 二叉树的遍历,5.5 树与森林,教学重点与难点,重点：,二叉树的性质； 二叉树的存储方法 二叉树的遍历及其应用 哈夫曼编码,难点：,二叉树遍历算法的应用,课 前 思 考,你见过家族谱系图吗？试以图形表示从你的祖父起的家族成员关系。,这类图形正是本章要讨论的“树”结构。,5.1.1 树的定义,5.1.2 树的常用术语,5.1 树的基本概念,5/52,5.1.1 树的定义,树是由n（n0）个结点所构成的有限集合，当n=0时，称为空树；当n0时，n个结点满足以下条件：,

2、有且仅有一个称为根的结点。, 其余结点可分为m（m0）个互不相交的有限集合，且每一个集合又构成一棵树，这棵树称为是根结点的子树。,6/52,5.1.1 树的定义,例如:,root,T1,T2,T3,7/52,5.1.1 树的定义,树的表示方法：,树形表示法,文氏图表示法,凹入图表示法,广义表(括号)表示法,8/52,5.1.1 树的定义,9/52,5.1.1 树的定义,10/52,5.1.1 树的定义,11/52,线性结构,树型结构,第一个数据元素 (无前驱),存在一个根结点 (无前驱),最后一个数据元素 (无后继),存在多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它结

3、点 (一个前驱(双亲)、 多个后继(孩子),元素之间存在“一对一”的关系,元素之间存在“一对多”的关系,12/52,5.1.1 树的定义,5.1.2 树的常用术语,5.1 树的基本概念,13/52,5.1.2 树的常用术语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+所有关联子树根的分支,结点所拥有子树的数目,树中所有结点的度的最大值,度为零的结点,度大于零的结点,分支:,根和子树根之间的连线(边),结点的路径:,由从根到该结点所经分支和结点构成,14/52,孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点,结点的层次:,树的深度：,树中所有结点层次数的最大值加1。

4、,假设根结点的层次为0，则其它结点的层次是其双亲结点的层次数加1。,有序树：,树中各结点的所有子树之间从左到右有严格的次序关系。,15/52,无序树:,森林：,由m（m0）棵互不相交的树所构成的集合。,与有序树相反，无序树是指树中各结点的所有子树之间没有严格的次序关系。,16/52,5.2.1 二叉树的定义,5.2.2 二叉树的性质,5.2.3 二叉树的存储结构,5.2 二叉树的基本概念,17/52,5.2.1 二叉树的定义,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,18/52,5.2.1 二叉树的定义,二叉树的五种基本形态

5、：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,19/52,5.2.1 二叉树的定义,具有3个结点的树与二叉树的形态各有多少种?,树有2种而二叉树有5种。,问,二叉树就是度小于等于2的树，这个结论是否正确？,20/52,满二叉树的定义,如果在一棵二叉树中，它的所有结点或者是叶结点，或者是左、右子树都非空，并且所有叶结点都在同一层上，则称这棵二叉树为满二叉树 。,21/52,完全二叉树的定义,如果在一棵具有n个结点的二叉树中，它的逻辑结构与满二叉树的前n个结点的逻辑结构相同，则称这样的二叉树为完全二叉树,完全二叉树,非完全二叉树,22/52,

6、单分支树的定义,左支树：,左支树,右支树,右支树：,所有结点都没有右孩子的二叉树。,所有结点都没有左孩子的二叉树。,23/52,5.2.1 二叉树的定义,5.2.2 二叉树的性质,5.2.3 二叉树的存储结构,5.2 二叉树的基本概念,24/52,5.2.2 二叉树的性质,在二叉树的第 i 层上至多有2i 个结点。(i0),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 0 层时，只有一个根结点： 20 = 1；,假设对所有的 j(0ji)层，命题成立；,则第 i层的结点数 2i-1 2 = 2i。,性质1：,25/52,5.2.2 二叉树的性质,深度为 h （h1）的二叉树上至多含

7、 2h-1 个结点。,性质2：,证明：,基于上一条性质，深度为 h 的二叉树上的结点数至多为: 20+21+ +2h-1 = 2h-1 。,26/52,5.2.2 二叉树的性质,对于任何一棵二叉树，若其叶结点的个数为n0 ，度为2的结点个数为n2，则有n0 = n2+1 。,性质3：,则 二叉树上结点总数 n = ？ 二叉树上分支总数 e = ？,n0 + n1 + n2,而 e与 n的关系如何？,证明：,n1+2n2,由此得， n0 = n2 + 1 。,设度为1的结点数为n1,e= n-1,27/52,5.2.2 二叉树的性质,度为m的树中，叶子结点数与其它结点数之间的关系如何？,思考,2

8、8/52,5.2.2 二叉树的性质,具有 n 个结点的完全二叉树的深度为 log2n +1 或 log2(n+1) 。,性质4：,证明：,设完全二叉树的深度为 h , 则根据第二条性质得,2h-1-1 n 2h -1,即2h-1 n 0) ,char r = preOrder.charAt(preIndex);,for (int i=0; i count; i+),if (r = inOrder.charAt( i + inIndex ) break;,root = new BiTreeNode(r);,root.setLchild( new BiTree (preOrder, inOrder

9、, preIndex + 1, inIndex,i) .root );,root.setRchild( new BiTree (preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count - i - 1) .root );,P170/算法5.13,100/52,5.3.3 建立二叉树 (二叉链式存储结构),3. 由标明空子树的先根遍历序列建 二叉树,1. 由先根和中根遍历序列建二叉树,2. 由后根和中根遍历序列建二叉树,4. 由完全二叉树的顺序存储结构建 立二叉链式存储结构,101/52,2. 由后根和中根遍历序列建二叉树,二叉树的后

10、序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,问：由二叉树的前序和后序序列是否也可以唯一确定一棵树？,102/52,2. 由后根和中根遍历序列建二叉树,由二叉树的前序和后序序列不可以唯一确定一棵树,如下二棵树：,其前序遍历序列都为：A B,其后序遍历序列都为：B A,103/52,2. 由后根和中根遍历序列建二叉树-算法,学生可依照算法5.13自行完成！,略,104/52,5.3.3 建立二叉树 (二叉链式存储结构),3. 由标明空子树的先根遍历序列建 二叉树,1. 由先根和中根遍历序列建二叉树,2. 由后根和中根遍历序列建二叉树,4. 由完全二叉树的顺序存储结构建 立二叉

11、链式存储结构,105/52,3.由标明空子树的先根遍历序列建 二叉树,例如:,以字符“#”表示,AB # C # # D # #,空 树：,只含一个根结点,A,以下列字符串表示,标明空子树的先根遍历序列就是在先根遍历序列中加入空树信息。,以字符串“A#”表示,106/52,3.由标明空子树的先根遍历序列建 二叉树,算法步骤：,在完整先根遍历数据输入正确的前提下，由此建立二叉链表的算法为： 若读入的字符是#，则建立空树； 否则 建立根结点； 递归建立左子树的二叉链表； 递归建立右子树的二叉链表。,107/52,3.由标明空子树的先根遍历序列建 二叉树,public BiTree(String p

12、reStr) / 算法5.14结束,P172/算法5.14,private int index=0; /用于记从preStr中取字符的位置,char c=preStr.charAt( index+ );,if (c != #) else,root = new BiTreeNode(c); /建立树的根结点,root.setLchild(new BiTree(preStr).root); / 建立树的左子树,root.setRchild(new BiTree(preStr).root); / 建立树的右子树,root = null;,108/52,5.3.3 建立二叉树 (二叉链式存储结构),3

13、. 由标明空子树的先根遍历序列建 二叉树,1. 由先根和中根遍历序列建二叉树,2. 由后根和中根遍历序列建二叉树,4. 由完全二叉树的顺序存储结构建 立二叉链式存储结构,109/52,4.由完全二叉树的顺序存储结构建立二叉链式存储结构,完全二叉树：,其对应的顺序存储结构：,右孩子的编号为,由二叉树的性质5可知，结点编号规则：,根结点的编号为,？,0,编号为 i的结点其左孩子的编号为,？,2i+1,？,2i+2,110/52,4.由完全二叉树的顺序存储结构建立二叉链式存储结构,public BiTreeNode createBiTree(String sqBiTree,int index) ,P

14、173/Exam5_7中,BiTreeNode root=null;,if (indexsqBitree .length() ,root = new BiTreeNode(sqBiTree.charAt(index);,root.setLchild(creatBiTree(sqBiTree,2*i+1); / 建立树的左子树,root.setRchild(creatBiTree(sqBiTree,2*i+2); / 建立树的右子树,return root;,算法：,111/52,作业1：,习题五中的 三、1，2,附加题如下：,112/52,1. 已知一棵度为m的树中有n1个度为1 的结点，n2

15、个度为2的结点，nm个度为m的结点，问该树中有多少片叶子？,2.试采用顺序存储方法和二叉链式存储方法分别画出下图所示的二叉树的存储结构。,附加题：,113/52,附加题：,3. 分别写出题2中二叉树的先根、中根和后序根遍历序列。,4. 已知一棵树二叉树的后根遍历和中根遍历的序列分别为：A C D B G I H F E和A B C D E F G H I，请画出该二叉树，并写出它的先根遍历的序列。,5. 已知一棵树二叉树的先根遍历和中根遍历的序列分别为：A B D G H C E F I和G D H B A E C I F，请画出此二叉树，并写出它的后根遍的序列。,114/52,1.已知一棵度

16、为m的树中有n1个度为1的结点，n2个度结点，nm个度为m的结点，问该树中有多少片叶子？,解：设树的总结点个数为n, 叶子结点的个数为n0，则 n= n0 + n1 + n2 + nm (1) 又因为树的总分支数为 n-1,且 n-1= n1 + n2 *2+ n3 *3+ nm*m (2) (1)-(2)得 1= n0n1 -2 n2 - -（m-1) nm 则： n0 = 1 + n2+2 n3+(m-1) nm,附加题解答：,115/52,2.试采用顺序存储方法和二叉链式存储方法分别画出下图所示的二叉树的存储结构。,二叉链式存储结构：,顺序存储结构：,附加题解答：,116/52,3.分别

17、写出题2中二叉树的先根、中根和后序根遍历序列。,前根序列：ABDEGCFH,中根序列：DBGEACHF,后根序列：DGEBHFCA,附加题解答：,117/52,4. 已知一棵树二叉树的后根遍历和中根遍历的序列分别为：A C D B G I H F E和A B C D E F G H I，请画出该二叉树，并写出它的先根遍历的序列。,先根遍历序列：EBADCFHGI,构造的二叉树如下：,附加题解答：,118/52,5. 已知一棵树二叉树的先根遍历和中根遍历的序列分别为：A B D G H C E F I和G D H B A E C I F，请画出此二叉树，并写出它的后根遍的序列。,后根遍历序列：G

18、HDBEIFCA,构造的二叉树如下：,附加题解答：,119/52,5.4.1 哈夫曼树的基本概念,5.4.2 哈夫曼树和哈夫曼编 码的构造方法,5.4.3 构造哈夫曼树和哈夫 曼编码类的描述,5.4 哈夫曼树及哈夫曼编码,120/52,5.4.1 哈夫曼树的基本概念,结点的路径长度：,结点间的路径：,从一个结点到另一个结点所经历的结点和分支序列。,从根结点到该结点的路径上分支的数目。,结点的权：,在实际应用中，人们往住会给树中的每一个结点赋予一个具有某种实际意义的数值，这个数值被称为该结点的权值。,121/52,5.4.1 哈夫曼树的基本概念,树的带权路径长度：,结点的带权路径长度：,结点的路

19、径长度与该结点的权值的乘积。,树中所有叶结点的带权路径长度之和 。,假设树上有 n 个叶结点，通常记作: 其中Li为带权 wi的叶子结点的带权路径长度。,122/52,5.4.1 哈夫曼树的基本概念,最优二叉树：,给定n个权值并作为n个叶结点按一定规则构造一棵二叉树，使其带权路径长度达到最小值，则这棵二叉树被称为最优二叉树。也称哈夫曼树。,在所有含 n 个叶子结点、并带相同权 值的 二叉树中，必存在一棵其带权路径 长度取最小值的树，这树就是“最优树”。,123/52,WPL(T)= 72+52+23+43+92 =60,WPL(T)= 74+94+53+42+21 =89,5.4.1 哈夫曼树

20、的基本概念,124/52,如何构造最优树（哈夫曼树）呢？,125/52,5.4.1 哈夫曼树的基本概念,5.4.2 哈夫曼树和哈夫曼编 码的构造方法,5.4.3 构造哈夫曼树和哈夫 曼编码类的描述,5.4 哈夫曼树及哈夫曼编码,126/52,5.4.2 哈夫曼树及哈夫曼编码的构造方法,(1) 根据给定的 n 个权值 w1, w2, , wn， 构造 一个由n 棵二叉树所构成的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树；,赫夫曼算法的主要步骤（P175）,127/52,5.4.2 哈夫曼树及哈夫曼编码的构造,赫夫曼算法的主要步

21、骤（P175）,(2)在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树，分别把它们作为左子树和右子树去构造一棵新二叉树，新二叉树的根结点权值为其左、右子树根结点的权值之和。,128/52,5.4.2 哈夫曼树及哈夫曼编码的构造方法,赫夫曼算法的主要步骤（P175）,(3) 作为新二叉树的左、右子树的这两棵二叉树从森林F中删除，同时加入刚生成的新二叉树；,(4) 重复 (2) 和 (3) 两步，直至 F 中只 含一棵二叉树为止，则这种棵二叉树就是所构成的哈夫曼树。,129/52,5.4.2 哈夫曼树及哈夫曼编码的构造方法,9,例如: 已知权值 W= 5, 6, 2, 9, 7 ,5,6,2

22、,7,5,2,7,6,9,7,6,7,13,9,5,2,7,130/52,5.4.2 哈夫曼树及哈夫曼编码的构造方法,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,哈夫曼码,9,5,2,7,16,131/52,5.4.2 哈夫曼树及哈夫曼编码的构造方法,再例如: 书P177的例5.8 (由学生完成）,已知在一个信息通信联络中使用了8个字符：a、b、c、d、e、f、g和h，每个字符的使用频度分别为：6、30、8、9、15、24、4和12，试设计各个字符的哈夫曼编码。,问：一棵有 n个叶子结点的哈夫曼树共有多 少个结点？,2*n+1 个

23、,132/52,5.4.2 哈夫曼树及哈夫曼编码的构造方法,用哈夫曼树进行译码,指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,前缀编码：,哈夫曼编码是一种前缀码。,从哈夫曼树的根开始，从左到右把二进制编码的每一位进行判别，若遇到0，则选择左分支走向下一个结点；若遇到1，则选择右分支走向下一个结点，直至到达一个树叶结点，便求得相应字符。,译码过程是编码过程的逆过程：,133/52,5.4.1 哈夫曼树的基本概念,5.4.2 哈夫曼树和哈夫曼编 码的构造方法,5.4.3 构造哈夫曼树和哈夫 曼编码类的描述,5.4 哈夫曼树及哈夫曼编码,134/52,5.4.3 哈夫曼树及哈

24、夫曼编码类的描述,哈夫曼树的结点存储结构示意图：,其中: weight域存放结点的权值； flag域存放结点是否加入哈夫曼树的标志 值，等于1时表示已加入，否则没加入； parent、rchild、lchild域分别存放父结 点，左、右孩子结点的地址。,135/52,5.4.3 哈夫曼树及哈夫曼编码类的描述,哈夫曼树的结点类描述：（书中P178）,public class HuffmanNode ,public HuffmanNode () / 构造一个空结点 this(null); ,/ / 构造一个左、右孩子域为空的结点 public HuffmanNode (int weight ) t

25、his.weight=weight; flag=0; parent=lchild=rchild=null; ,private int weight; / 结点的数据域 private int flag; /结点是否加入哈夫曼树的标志 private HuffmanNode parent, lchild, rchild; /父结点， 左、右孩子结点域,136/52,5.4.3 哈夫曼树及哈夫曼编码类的描述,构造哈夫曼树和哈夫曼编码的类描述：,public class HuffmanTree ,（略）,书中P179,public int huffmanCoding (int W) ,int n =

26、 W.length; / 字符个数 int m = 2 * n - 1; / 哈夫曼树的结点数,137/52,5.4.3 哈夫曼树及哈夫曼编码类的描述,例如：对于书P177例5.8，按HuffmanTree类中的HuffmanCoding方法可构造如下图的一棵二棵树：,138/52,weight flag parent lchild rchild,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,其存储结构HN的初始和终结状态分别如下图所示 ：,weight flag parent lchild rchild,0 1 2 3 4 5 6 7 8 9 10 11 12 13

27、14,139/52,5.4.3 哈夫曼树及哈夫曼编码类的描述,所得的哈夫曼编码如下图所示 ：,140/52,5.5.1 树、森林与二叉树之间的转换,5.5.2 树的存储结构,5.5.3 树与森林的遍历,5.5 树与森林,141/52,5.5.1 树、森林与二叉树之间的转换,1. 树转换成二叉树的规则：,左孩子右兄弟,142/52,5.5.1 树、森林与二叉树之间的转换,树转换成二叉树可形象描述为以下3个步骤：,(1) 加线,(2) 删线,(3) 旋转,树,二叉树,143/52,5.5.1 树、森林与二叉树之间的转换,2. 二叉树转换成树的规则：,是树转换成二叉树的逆过程：,(1) 加线,(2)

28、 删线,(3) 旋转,二叉树,树,144/52,5.5.1 树、森林与二叉树之间的转换,3. 森林转换成二叉树的规则：,若 F = ，则 B = ； 否则， 由 ROOT( T1 ) 对应得到 Node(root)； 由 (t11, t12, , t1m ) 对应得到 LBT； 由 (T2, T3, Tn ) 对应得到 RBT。,145/52,树与二叉树的对应,例如：如下森林转化成二叉树的过程为：,5.5.1 树、森林与二叉树之间的转换,146/52,树根相连,（将森林中后一棵树视为前一棵树的右子树）,5.5.1 树、森林与二叉树之间的转换,147/52,4. 二叉树转换为森林的规则为：,若

29、B = ， 则 F = ； 否则， 由 Node(root) 对应得到 ROOT( T1 )； 由LBT 对应得到 ( t11, t12, ，t1m)； 由RBT 对应得到 (T2, T3, , Tn)。,（转换过程是森林转换成二叉树的逆过程）,5.5.1 树、森林与二叉树之间的转换,148/52,5.5.1 树、森林与二叉树之间的转换,5.5.2 树的存储结构,5.5.3 树与森林的遍历,5.5 树与森林,149/52,5.5.2 树的存储结构,1.双亲链表存储结构,2.孩子链表存储结构,4.孩子兄弟链表存储结构(重点掌握）,树的四种存储结构,3.双亲孩子链表存储结构,150/52,5.5.

30、2 树的存储结构,1.双亲链表存储结构,151/52,5.5.2 树的存储结构,2.孩子链表存储结构,152/52,5.5.2 树的存储结构,3.双亲孩子链表存储结构,153/52,5.5.2 树的存储结构,4. 孩子兄弟链表存储结构（*）,*左孩子右兄弟,154/52,5.5.2 树的存储结构,4. 孩子兄弟链表存储结构,孩子兄弟链表中结点类的描述：,public class CSTreeNode ,private Object data; / 结点的数据域 private CSTreeNode firstchild, nextsiblingchild; / 左孩子、右兄弟域,(书P186)

31、,155/52,5.5.1 树、森林与二叉树之间的转换,5.5.2 树的存储结构,5.5.3 树与森林的遍历,5.5 树与森林,156/52,5.5.3 树和森林的遍历,一、树的遍历,157/52,5.5.3 树和森林的遍历-树的遍历,树的遍历可有三条搜索路径:,3.层次遍历.,1.先根遍历;,2.后根遍历;,158/52,5.3.1 二叉树的遍历方法及其实现,1.先根遍历定义及递归实现,若树非空，则进行如一操作: （1）访问根结点； （2）从左到右依次先根遍历根结点的每一棵子树。,先根遍历序列：,A B E F C D G H I J K,159/52,public void preRoot

32、Traverse(BiTreeNode T) ,先根遍历操作实现的递归算法描述:,5.3.1 二叉树的遍历方法及其实现,if (T！=null) ,System.out.print(T.getData();,preRootTraverse(T.getFirstchild();,preRootTraverse(T.getNextsibling();,P187/算法5.16,160/52,5.3.1 二叉树的遍历方法及其实现,2.后根遍历定义及递归实现,若树非空，则进行如一操作: （1）从左到右依次后根遍历根结点的每一棵子树； （2）访问根结点。,后根遍历序列：,E F B C I J K H G

33、 D A,161/52,public void postRootTraverse(BiTreeNode T) ,后根遍历操作实现的递归算法描述:,5.3.1 二叉树的遍历方法及其实现,if (T！=null) ,System.out.print(T.getData();,postRootTraverse(T.getFirstchild();,postRootTraverse(T.getNextsibling();,P187/算法5.16,162/52,5.3.1 二叉树的遍历方法及其实现,3.层次遍历定义及操作实现,若树为非空，则从根结点开始，从上到下依次访问每一层的各个结点，在同一层中的结点，则按从左到右的顺序依次进行访问。,层次遍历序列：,A B C D E F G H I J K,163/52,public void levelTraverse(BiTreeNode T) ,