第5章+树与二叉树

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

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

3、在“一对多”的关系,5.1.1 树的定义,5.1.2 树的常用术语,5.1 树的基本概念,5.1.2 树的常用术语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+所有关联子树根的分支,结点所拥有子树的数目,树中所有结点的度的最大值,度为零的结点,度大于零的结点,分支:,根和子树根之间的连线(边),结点的路径:,由从根到该结点所经分支和结点构成,孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点,结点的层次:,树的深度：,树中所有结点层次数的最大值加1。,假设根结点的层次为0，则其它结点的层次是其双亲结点的层次数加1。,有序树：,树中各结点的所有子树之间从左到右有严格的次

4、序关系。,无序树:,森林：,由m（m0）棵互不相交的树所构成的集合。,与有序树相反，无序树是指树中各结点的所有子树之间没有严格的次序关系。,5.2.1 二叉树的定义,5.2.2 二叉树的性质,5.2.3 二叉树的存储结构,5.2 二叉树的基本概念,5.2.1 二叉树的定义,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,5.2.1 二叉树的定义,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,5.2.1 二叉树的定义,具有3个结点的树与二叉树的形态各有多少种

5、?,树有2种而二叉树有5种。,问,二叉树就是度小于等于2的树，这个结论是否正确？,满二叉树的定义,如果在一棵二叉树中，它的所有结点或者是叶结点，或者是左、右子树都非空，并且所有叶结点都在同一层上，则称这棵二叉树为满二叉树 。,完全二叉树的定义,如果在一棵具有n个结点的二叉树中，它的逻辑结构与满二叉树的前n个结点的逻辑结构相同，则称这样的二叉树为完全二叉树,完全二叉树,非完全二叉树,单分支树的定义,左支树：,左支树,右支树,右支树：,所有结点都没有右孩子的二叉树。,所有结点都没有左孩子的二叉树。,5.2.1 二叉树的定义,5.2.2 二叉树的性质,5.2.3 二叉树的存储结构,5.2 二叉树的基

6、本概念,5.2.2 二叉树的性质,在二叉树的第 i 层上至多有2i 个结点。(i0),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 0 层时，只有一个根结点： 20 = 1；,假设对所有的 j(0ji)层，命题成立；,则第 i层的结点数 2i-1 2 = 2i。,性质1：,5.2.2 二叉树的性质,深度为 h （h1）的二叉树上至多含 2h-1 个结点。,性质2：,证明：,基于上一条性质，深度为 h 的二叉树上的结点数至多为: 20+21+ +2h-1 = 2h-1 。,5.2.2 二叉树的性质,对于任何一棵二叉树，若其叶结点的个数为n0 ，度为2的结点个数为n2，则有n0 = n

7、2+1 。,性质3：,则 二叉树上结点总数 n = ？ 二叉树上分支总数 e = ？,n0 + n1 + n2,而 e与 n的关系如何？,证明：,n1+2n2,由此得， n0 = n2 + 1 。,设度为1的结点数为n1,e= n-1,5.2.2 二叉树的性质,度为m的树中，叶子结点数与其它结点数之间的关系如何？,思考,5.2.2 二叉树的性质,具有 n 个结点的完全二叉树的深度为 log2n +1 或 log2(n+1) 。,性质4：,证明：,设完全二叉树的深度为 h , 则根据第二条性质得,2h-1-1 n 2h -1,即2h-1 n 2h ,h-1 log2 n h,因为 h 只能是整数

8、，因此，,h =log2n + 1,推出,5.2.2 二叉树的性质,性质5：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 0至 n-1 的编号，则对完全二叉树中任意一个编号为 i 的结点,有：(1) 若 i=0，则该结点是二叉树的根，无双亲， 否则，编号为 (i-1)/2 的结点为其双亲结 点；(2) 若 2i+1n，则该结点无左孩子，否则，编 号为 2i+1 的结点为其左孩子结点；(3) 若 2i+2n，则该结点无右孩子结点，否 则，编号为2i+2 的结点为其右孩子结点。,5.2.1 二叉树的定义,5.2.2 二叉树的性质,5.2.3 二叉树的存储结构,5.2 二叉树的基本概念,5

9、.2.3 二叉树的存储结构,2.二叉树的链式存储结构,1. 二叉树的顺序存储结构,5.2.3 二叉树的存储结构顺序存储,用一组地址连续的存储单元从根结点开始依次自上而下，并按层次从左到右存储完全二叉树上的各结点元素，即将完全二叉树编号为i的结点元素存储在下标为i数组元素中。,对于完全二叉树：,5.2.3 二叉树的存储结构顺序存储,例如(完全二叉树）：,5.2.3 二叉树的存储结构顺序存储,先在树中增加一些并不存在的虚结点并使其成为一棵完全二叉树，然后用与完全二叉树相同的方法对结点进行编号，再将编号为i的结点的值存放到数组下标为i的数组单元中，虚结点不存放任何值。,对于非完全二叉树：,5.2.3

10、 二叉树的存储结构顺序存储,例如(非完全二叉树）：,问：一个深度为 k 且只有 k 个结点的右支树需要的数组存储单元为多少？,顺序存储仅适用于满或完全二叉树。,5.2.3 二叉树的存储结构链式存储,1. 二叉链表,2三叉链表,5.2.3 二叉树的存储结构二叉链表,root,结点结构:,5.2.3 二叉树的存储结构三叉链表,结点结构:,5.2.3 二叉树的存储结构二叉链表,二叉链表中结点类的描述(书中P156),public class BiTreeNode ,/ 构造一个空结点 public BiTreeNode() this(null); ,/ 构造一个左、右孩子域为空的结点 public

11、BiTreeNode(Object data) this(data, null, null)； ,private Object data; / 结点的数据域 private BiTreeNode lchild, rchild; / 左、右孩子域,5.2.3 二叉树的存储结构二叉链表,二叉链表中结点类的描述(书中P156),public class BiTreeNode ,/ 构造一个数据域和左、右孩子域都不为空的结点 public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) this.data = data; th

12、is.lchild = lchild; this.rchild = rchild; ,5.2.3 二叉树的存储结构二叉链表,二叉链表存储结构下二叉树类的描述(书中P158),public class BiTree ,/ 构造一棵空树 public BiTree () this.root=null; ,/ 构造一棵根结点为root的树 public BiTree(BiTreeNode root) this.root=root; ,private BiTreeNode root; / 树的根结点,5.3.1 二叉树的遍历方法及其实现,5.3.2 二叉树遍历算法的应用举例,5.3.3 建立二叉树,5

13、.3 二叉树的遍历,5.3.1 二叉树的遍历方法及其实现,一、问题的提出,二、二叉树遍历方法及其递归实现,三、二叉树遍历方法的非递归实现,5.3.1 二叉树的遍历方法及其实现,沿着某一条搜索路径对二叉树中的结点进行访问，使得每个结点均被访问一次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出结点的信息等。,什么是遍历?,5.3.1 二叉树的遍历方法及其实现,一、问题的提出,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构。,每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。

14、,5.3.1 二叉树的遍历方法及其实现,一、问题的提出,二、二叉树遍历方法及其递归实现,三、二叉树遍历方法的非递归实现,5.3.2 二叉树的遍历方法及其实现,二、二叉树的遍历方法及递归实现,对“二叉树”而言，可以有三条搜索路径：,1先上后下的遍历； 2先左后右的遍历； 3先右后左的遍历。,5.3.1 二叉树的遍历方法及其实现,二叉树的遍历方法,对应三条搜索路径，“二叉树” 有7种遍历方法：,1. 层次遍历方法；,2. DLR(先根遍历)； LDR(中根遍历)； LRD(后根遍历)。,3. DRL；RDL；RLD。,5.3.1 二叉树的遍历方法及其实现,1.层次遍历,若二叉树为空，则为空操作；否

15、则，按自上而下先访问第0层的根结点，然后再从左到右依次访问各层次中的每一个结点。,层次遍历序列：,ABECFDGHK,5.3.1 二叉树的遍历方法及其实现,2.先根(序)遍历(DLR)定义及递归实现,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先根遍历左子树； （3）先根遍历右子树。,先根遍历序列：,ABCDEFGHK,先根遍历序列：,A B C D E F G H K,public void preRootTraverse(BiTreeNode T) ,先根遍历操作实现的递归算法描述:,5.3.1 二叉树的遍历方法及其实现,if (T！=null) ,System.out.p

16、rint(T.getData();,preRootTraverse(T.getLchild();,preRootTraverse(T.getRchild();,5.3.1 二叉树的遍历方法及其实现,3.中根(序)遍历(LDR)定义及递归实现,若二叉树为空树，则空操作；否则， （1）中根遍历左子树； （2）访问根结点； （3）中根遍历右子树。,动画播放 （6-4-2-2）,中根遍历序列：,BDCQEHGKF,中根遍历序列：,B D C A E H G K F,public void intRootTraverse(BiTreeNode T) ,中根遍历操作实现的递归算法描述:,5.3.1 二叉树

17、的遍历方法及其实现,if (T！=null) ,System.out.print(T.getData();,intRootTraverse(T.getLchild();,intRootTraverse(T.getRchild();,5.3.1 二叉树的遍历方法及其实现,4.后根(序)遍历(LRD)定义及递归实现,若二叉树为空树，则空操作；否则， （1）后根遍历左子树； （2）后根遍历右子树； （3）访问根结点。,动画播放 （6-4-2-3）,后根遍历序列：,DCBHKGFE,后根遍历序列：,D C B H K G F E A,public void postRootTraverse(BiTre

18、eNode T) ,后根遍历操作实现的递归算法描述:,5.3.1 二叉树的遍历方法及其实现,if (T！=null) ,System.out.print(T.getData();,postRootTraverse(T.getLchild();,postRootTraverse(T.getRchild();,5.3.1 二叉树的遍历方法及其实现,一、问题的提出,二、二叉树遍历方法及其递归实现,三、二叉树遍历方法的非递归实现,5.3.1 二叉树的遍历方法及其实现,1 . 先根遍历操作的非递归实现,方法：,借助一个栈来记载当前被访问结点的右孩子 结点。,主要思想：,从非空二叉树的根结点出发，沿着该结

19、点的左子树向下搜索，在搜索过程中每遇到一个结点就先访问该结点，并将该结点的非空右孩子结点压栈。当左子树结点访问完成后，从栈顶弹出结点的右孩子结点，然后用上述同样的方法去遍历该结点的右子树，依此类推，直到二叉树中所有的结点都被访问为止。,5.3.1 二叉树的遍历方法及其实现,1 . 先根遍历操作的非递归实现,基本步骤：, 创建一个栈对象，根结点入栈；, 当栈为非空时，将栈顶结点弹出栈内并访问该结点；,LinkStack S=new LinkStack();,T=(BiTreeNode)S.pop();,S.push(T);,System.out.print(T.getData();,5.3.1

20、二叉树的遍历方法及其实现,1 . 先根遍历操作的非递归实现,基本步骤：, 对当前访问结点的非空左孩子结点相继依次访问，并将当前访问结点的非空右孩子结点压入栈内；, 重复执行步骤和，直到栈为空为止。,While(T!=null) ,if (T.getLchild()!=null) System.out.print(T.getData();,if (T.getRchild()!=null) S.push(T.getRchild();,T=T.getLchild();,先根遍历的非递归算法(书P161算法5.4),LinkStack S=new LinkStack();,T=(BiTreeNode)

21、S.pop();,S.push(T);,System.out.print(T.getData();,while(T!=null) ,if (T.getLchild()!=null) System.out.print(T.getData();,if (T.getRchild()!=null) S.push(T.getRchild();,T=T.getLchild();,while(!S.isEmpty() ,public void preRootTraverse() BiTreeNode T=root; ,if (T! =null) ,时间复杂度：O(n),5.3.1 二叉树的遍历方法及其实现,

22、2 . 中根遍历操作的非递归实现,方法：,借助一个栈来记载遍历截长过程中所经历的而未被访问的所有结点,主要思想：,从非空二叉树的根结点出发，沿着该结点的左子树向下搜索，在搜索过程中将所遇到的每一个结点依次压栈，直到二叉树中最左下的结点压栈为止，然后从栈中弹出栈顶结点并对其进行访问，访问完后再进入该结点的右子树并用上述同样的方法去遍历该结点的右子树，依此类推，直到二叉树中所有的结点都被访问为止。,5.3.1 二叉树的遍历方法及其实现,2 . 中根遍历操作的非递归实现,基本步骤：, 创建一个栈对象，根结点入栈；,若栈顶结点非空，则将栈顶结点的非空左孩子相继进栈；,LinkStack S=new L

23、inkStack();,while( S.peek()!=null ) ,S.push(T);,S.push(BiTreeNode)S.peek().getLchild();,S.pop(); /空结点出栈,5.3.1 二叉树的遍历方法及其实现,2 . 中根遍历操作的非递归实现,基本步骤：,栈顶结点出栈并访问非空栈顶结点，再 使该栈顶结点的非空右孩子结点入栈；, 重复执行步骤和，直到栈为空为止。,if (!S.isEmpty() ,T=(BiTreeNode)S.pop();,System.out.print(T.getData();,S.push(T.getRchild();,中根遍历的非递

24、归算法(书P162算法5.5),LinkStack S=new LinkStack();,S.push(T);,while(!S.isEmpty() ,public void inRootTraverse() BiTreeNode T=root; ,if (T! =null) ,while( S.peek()!=null ) ,S.push(BiTreeNode)S.peek().getLchild();,S.pop();,if (!S.isEmpty() ,T=(BiTreeNode)S.pop();,System.out.print(T.getData();,S.push(T.getRch

25、ild();,时间复杂度：O(n),5.3.1 二叉树的遍历方法及其实现,3 . 后根遍历操作的非递归实现,方法：,借助一个栈来记载遍历截长过程中所经历的而未被访问的所有结点;,引进一个访问标志变量flag和一个结点指针p。,其中：flag用来标记当前栈顶结点是否被访问，当值为true时，表示栈顶结点已被访问；当值为false时，表示当前栈顶结点未被访问，指针p指向当前遍历过程中最后一个被访问的结点。,5.3.1 二叉树的遍历方法及其实现,3 .后根遍历操作的非递归实现,基本步骤：, 创建一个栈对象，根结点入栈，p赋初始值null；,若栈顶结点非空，则将栈顶结点的非空左孩子相继进栈；,Link

26、Stack S=new LinkStack();,while( S.peek()!=null ) ,S.push(T);,S.push(BiTreeNode)S.peek().getLchild();,S.pop();,BiTreeNOde p=null;,若栈非空，查看栈顶结点，若栈顶结点的右孩子为空，或者与p相等，则将栈顶结点弹出栈并访问它，同时使p指向该结点，并置flag值为true；否则，将栈顶结点的右孩子压入栈，并置flag值为false。,if (T.getRchild()=null |T.getRchild()=p) else ,System.out.print(T.getDat

27、a();,S.push(T.getRchild();,T=(BiTreeNode)S.pop();,p=T;,flag=true;,flag=flase;,5.3.1 二叉树的遍历方法及其实现,3 . 后根遍历操作的非递归实现,基本步骤：,若flag值为true，则重复执行步骤；否则，重复执行步骤和，直到栈为空为止。,while( !S.isEmpty() while( !S.isEmpty() if (!flag) break; ,后根遍历的非递归算法(书P163算法5.6),public void postRootTraverse() BiTreeNode T=root; ,if (T!

28、=null) ,while( !S.isEmpty() while( !S.isEmpty() if (!flag) break; ,时间复杂度：O(n),5.3.1 二叉树的遍历方法及其实现,4 . 层次遍历操作的非递归实现,方法：,借助一个队列。在遍历开始时，首先将根结点入队，然后每次从队列中取出队首元素进行处理，每处理一个结点，都是先访问该结点，再按从左到右的顺序把它的孩子结点依次入队。,5.3.1 二叉树的遍历方法及其实现,4 . 层次遍历操作的非递归实现,基本步骤：,创建一个链队列对象，根结点入队；,LinkStack L=new LinkQueue();,L.offer(T);,5

29、.3.1 二叉树的遍历方法及其实现,4 . 层次遍历操作的非递归实现,基本步骤：,若队列非空，重复将队首结点出队并访问该结点，再将该结点的非空左、右孩子结点依次入队，直到队列为空为止。,while( !L.isEmpty() ,T=(BiTreeNode)L.poll();,System.out.print(T.getData();,if (T.getLchild()!=null) L.offer(T.getLchild();,if (T.getRchild()!=null) L.offer(T.getRchild();,层次遍历的非递归算法(书P166算法5.7),public void l

30、evelTraverse() BiTreeNode T=root; ,if (T! =null) ,LinkStack L=new LinkQueue();,L.offer(T);,while( !L.isEmpty() ,T=(BiTreeNode)L.poll();,System.out.print(T.getData();,if (T.getLchild()!=null) L.offer(T.getLchild();,if (T.getRchild()!=null) L.offer(T.getRchild();,时间复杂度：O(n),5.3.1 二叉树的遍历方法及其实现,5.3.2 二叉

31、树遍历算法的应用举例,5.3.3 建立二叉树,5.3 二叉树的遍历,5.3.2 二叉树的遍历应用举例,1. 在二叉树上的查找某个结点,2. 计算二叉树中结点的个数,3. 求二叉树的深度,4.判断两棵二叉树是否相等,1. 在二叉树上的查找某个结点,要求： 实现方法：,在以T为根结点的二叉树中查找值为x的结点，若找到，则返回该结点；否则，返回空值。,可在先根遍历过程中进行查找，并将先根遍历算法中的“访问结点”的操作改为：将根结点的值与x进行比较的操作。,1. 在二叉树上的查找某个结点,实现步骤：,1)若二叉树为空，则不存在这个结点，返回空值；否则，将根结点的值与x进行比较，若相等，则返回该结点；,

32、2) 否则在左子树中进行查找，若找到，则返回找到的结点；,3) 否则返回在右子树中进行查找的结果。,1. 在二叉树上的查找某个结点,实现算法(书P166算法5.8)：,public BiTreeNode searchNode(BiTreeNode T, Object x) ,if (T! =null) ,if (T.getData().equals(x) return T; else ,BiTreeNode lresult=searchNOde(T.getLchild(),x);,return lresult!=null?lresult:searchNOde(T.getRchild(),x);

33、,5.3.2 二叉树的遍历应用举例,1. 在二叉树上的查找某个结点,2. 计算二叉树中结点的个数,3. 求二叉树的深度,4.判断两棵二叉树是否相等,要求： 实现方法:,计算以T为根结点的二叉树中所含结点的个数，并返回其值。,由于二叉树中结点的个数等于1个根结点再分别加上它的左、右子树中结点的个数，所以可以运用不同的遍历递归算法的思想来统计出二叉树中结点的个数。,2. 计算二叉树中结点的个数,实现步骤:(以中根遍历为例),1)引进计数变量count并赋初值0 ；,2) 若二叉树非空，则：,3) 返回count值。, 统计根结点的左子树的结点个 数，并加入到count变量中；, count值加1；

34、, 统计根结点的右子树的结点个 数，并加入到count变量中；,2. 计算二叉树中结点的个数,实现算法(参看书P167算法5.9)：,public int countNode(BiTreeNode T) ,if (T! =null) ,count+=countNode(T.getLchild();,count+;,count+=countNode(T.getRchild();,2. 计算二叉树中结点的个数,int count = 0;,return count;,5.3.2 二叉树的遍历应用举例,1. 在二叉树上的查找某个结点,2. 计算二叉树中结点的个数,3. 求二叉树的深度,4.判断两棵二

35、叉树是否相等,要求： 实现方法:,求出以T为根结点的二叉树的深度并返回其值。,1)先分别求得左、右子树的深度；,3. 求二叉树的深度,2)再将后根遍历算法中的“访问结点”的操作改为：求得左、右子树深度的最大值，最后将最大值加1后返回其值。,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1，所以可利用后根遍历算法来实现。,实现算法(书P168算法5.11)：,public int getDepth(BiTreeNode T) ,if (T! =null) return 0;,int lDepth = getDepth(T.getLchild();,int rDepth = g

36、etDepth(T.getRchild();,return 1 + (lDepth rDepth ? lDepth : rDepth);,3. 求二叉树的深度,5.3.2 二叉树的遍历应用举例,1. 在二叉树上的查找某个结点,2. 计算二叉树中结点的个数,3. 求二叉树的深度,4.判断两棵二叉树是否相等,要求： 实现方法:,判断根结点为T1、T2的两棵二叉树是否相等，若相等，则返回true；否则，返回false。,因为一棵二叉树由根、左子树和右子树三个部分组成，所以只有当两棵二叉树的三个组成部分都对应相等时，这两棵树才相等。而左、右子树的相等判断可以用对二叉树相等判断的同样方法来实现，即可用递

37、归调用来实现。,4.判断两棵二叉树是否相等,所以，可利用先根、中根、和后根遍历中的任何一种算法思想来实现。,实现步骤:(以中根遍历为例),1)若两棵二叉树都为空，则两棵二叉树相等，返回true;,2)若两棵二叉树都非空，则：,3)其它任何情况都返回false。,若左子树相等，则继续判断它们的根结点是否相等，即转 ；,若根结点的值相等，则继续判断它们的右子树是否相等，即转 ；,若右子树也相等，则两棵二叉树相等，返回true;,4.判断两棵二叉树是否相等,实现算法(书P168算法5.12)：,public boolean isEqual(BiTreeNode T1, BiTreeNode T2)

38、,if (T1=null,if (T1!=null,return false;,5.3.1 二叉树的遍历方法及其实现,5.3.2 二叉树遍历算法的应用举例,5.3.3 建立二叉树,5.3 二叉树的遍历,5.3.3 建立二叉树 (二叉链式存储结构),3. 由标明空子树的先根遍历序列建 二叉树,1. 由先根和中根遍历序列建二叉树,2. 由后根和中根遍历序列建二叉树,4. 由完全二叉树的顺序存储结构建 立二叉链式存储结构,1. 由先根和中根遍历序列建二叉树,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，,如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,二叉树的先序序列,

39、二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,1. 由先根和中根遍历序列建二叉树,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,1. 由先根和中根遍历序列建二叉树-算法,建立一棵二叉树的过程如下：,其中： preOrder是整棵树的先根遍历序列； inOrder是整棵树的中根遍历序列； reIndex是先根遍历序列在preOrder中的开始位置; inIndex是中根遍历序列在inOrder中的开始位置; count表示树中结点的个数。,1. 由先根和中根遍历序列

40、建二叉树- 算法,实现方法：,引入5个参数：,preOrder、inOrder、preIndex、inIndex和count。,1. 由先根和中根遍历序列建二叉树-算法,public BiTree(String preOrder, String inOrder, int preIndex, int inIndex,int count) ,if (count 0) ,char r = preOrder.charAt(preIndex);,for (int i=0; i count; i+),if (r = inOrder.charAt( i + inIndex ) break;,root = n

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

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

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

44、ing preStr) / 算法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;,5.3.3 建立二叉树 (二叉链式存储结构),3.

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

46、reeNode 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;,算法：,作业1：,习题五中的 三、1，2,附加题如下：,1. 已知一棵度为m的树中有n1个度为1 的结点，n2个度为2的结点，nm个度为m的结点，问该树中有多少片叶子？,

47、2.试采用顺序存储方法和二叉链式存储方法分别画出下图所示的二叉树的存储结构。,附加题：,附加题：,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，请画出此二叉树，并写出它的后根遍的序列。,1.已知一棵度为m的树中有n1个度为1的结点，n2个度结点，nm个度为m的结点，问该树中有多少片叶子？

48、,解：设树的总结点个数为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,附加题解答：,2.试采用顺序存储方法和二叉链式存储方法分别画出下图所示的二叉树的存储结构。,二叉链式存储结构：,顺序存储结构：,附加题解答：,3.分别写出题2中二叉树的先根、中根和后序根遍历序列。,前根序列：ABDEGCFH,中根序列：DBGEACHF,后根序列：D

49、GEBHFCA,附加题解答：,4. 已知一棵树二叉树的后根遍历和中根遍历的序列分别为：A C D B G I H F E和A B C D E F G H I，请画出该二叉树，并写出它的先根遍历的序列。,先根遍历序列：EBADCFHGI,构造的二叉树如下：,附加题解答：,5. 已知一棵树二叉树的先根遍历和中根遍历的序列分别为：A B D G H C E F I和G D H B A E C I F，请画出此二叉树，并写出它的后根遍的序列。,后根遍历序列：GHDBEIFCA,构造的二叉树如下：,附加题解答：,5.4.1 哈夫曼树的基本概念,5.4.2 哈夫曼树和哈夫曼编 码的构造方法,5.4.3 构

50、造哈夫曼树和哈夫 曼编码类的描述,5.4 哈夫曼树及哈夫曼编码,5.4.1 哈夫曼树的基本概念,结点的路径长度：,结点间的路径：,从一个结点到另一个结点所经历的结点和分支序列。,从根结点到该结点的路径上分支的数目。,结点的权：,在实际应用中，人们往住会给树中的每一个结点赋予一个具有某种实际意义的数值，这个数值被称为该结点的权值。,5.4.1 哈夫曼树的基本概念,树的带权路径长度：,结点的带权路径长度：,结点的路径长度与该结点的权值的乘积。,树中所有叶结点的带权路径长度之和 。,假设树上有 n 个叶结点，通常记作: 其中Li为带权 wi的叶子结点的带权路径长度。,5.4.1 哈夫曼树的基本概念,

51、最优二叉树：,给定n个权值并作为n个叶结点按一定规则构造一棵二叉树，使其带权路径长度达到最小值，则这棵二叉树被称为最优二叉树。也称哈夫曼树。,在所有含 n 个叶子结点、并带相同权 值的 二叉树中，必存在一棵其带权路径 长度取最小值的树，这树就是“最优树”。,WPL(T)= 72+52+23+43+92 =60,WPL(T)= 74+94+53+42+21 =89,5.4.1 哈夫曼树的基本概念,如何构造最优树（哈夫曼树）呢？,5.4.1 哈夫曼树的基本概念,5.4.2 哈夫曼树和哈夫曼编 码的构造方法,5.4.3 构造哈夫曼树和哈夫 曼编码类的描述,5.4 哈夫曼树及哈夫曼编码,5.4.2 哈

52、夫曼树及哈夫曼编码的构造方法,(1) 根据给定的 n 个权值 w1, w2, , wn， 构造 一个由n 棵二叉树所构成的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树；,赫夫曼算法的主要步骤（P175）,5.4.2 哈夫曼树及哈夫曼编码的构造,赫夫曼算法的主要步骤（P175）,(2)在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树，分别把它们作为左子树和右子树去构造一棵新二叉树，新二叉树的根结点权值为其左、右子树根结点的权值之和。,5.4.2 哈夫曼树及哈夫曼编码的构造方法,赫夫曼算法的主要步骤（P175）,(3) 作为

53、新二叉树的左、右子树的这两棵二叉树从森林F中删除，同时加入刚生成的新二叉树；,(4) 重复 (2) 和 (3) 两步，直至 F 中只 含一棵二叉树为止，则这种棵二叉树就是所构成的哈夫曼树。,5.4.2 哈夫曼树及哈夫曼编码的构造方法,9,例如: 已知权值 W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,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,5.4.2 哈夫曼树及哈夫曼编码的构造方法,再例如:

54、书P177的例5.8 (由学生完成）,已知在一个信息通信联络中使用了8个字符：a、b、c、d、e、f、g和h，每个字符的使用频度分别为：6、30、8、9、15、24、4和12，试设计各个字符的哈夫曼编码。,问：一棵有 n个叶子结点的哈夫曼树共有多 少个结点？,2*n+1 个,5.4.2 哈夫曼树及哈夫曼编码的构造方法,用哈夫曼树进行译码,指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,前缀编码：,哈夫曼编码是一种前缀码。,从哈夫曼树的根开始，从左到右把二进制编码的每一位进行判别，若遇到0，则选择左分支走向下一个结点；若遇到1，则选择右分支走向下一个结点，直至到达一个树叶结

55、点，便求得相应字符。,译码过程是编码过程的逆过程：,5.4.1 哈夫曼树的基本概念,5.4.2 哈夫曼树和哈夫曼编 码的构造方法,5.4.3 构造哈夫曼树和哈夫 曼编码类的描述,5.4 哈夫曼树及哈夫曼编码,5.4.3 哈夫曼树及哈夫曼编码类的描述,哈夫曼树的结点存储结构示意图：,其中: weight域存放结点的权值； flag域存放结点是否加入哈夫曼树的标志 值，等于1时表示已加入，否则没加入； parent、rchild、lchild域分别存放父结 点，左、右孩子结点的地址。,5.4.3 哈夫曼树及哈夫曼编码类的描述,哈夫曼树的结点类描述：（书中P178）,public class Huf

56、fmanNode ,public HuffmanNode () / 构造一个空结点 this(null); ,/ / 构造一个左、右孩子域为空的结点 public HuffmanNode (int weight ) this.weight=weight; flag=0; parent=lchild=rchild=null; ,private int weight; / 结点的数据域 private int flag; /结点是否加入哈夫曼树的标志 private HuffmanNode parent, lchild, rchild; /父结点， 左、右孩子结点域,5.4.3 哈夫曼树及哈夫曼编

57、码类的描述,构造哈夫曼树和哈夫曼编码的类描述：,public class HuffmanTree ,（略）,书中P179,public int huffmanCoding (int W) ,int n = W.length; / 字符个数 int m = 2 * n - 1; / 哈夫曼树的结点数,5.4.3 哈夫曼树及哈夫曼编码类的描述,例如：对于书P177例5.8，按HuffmanTree类中的HuffmanCoding方法可构造如下图的一棵二棵树：,weight flag parent lchild rchild,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,其存

58、储结构HN的初始和终结状态分别如下图所示 ：,weight flag parent lchild rchild,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,5.4.3 哈夫曼树及哈夫曼编码类的描述,所得的哈夫曼编码如下图所示 ：,5.5.1 树、森林与二叉树之间的转换,5.5.2 树的存储结构,5.5.3 树与森林的遍历,5.5 树与森林,5.5.1 树、森林与二叉树之间的转换,1. 树转换成二叉树的规则：,左孩子右兄弟,5.5.1 树、森林与二叉树之间的转换,树转换成二叉树可形象描述为以下3个步骤：,(1) 加线,(2) 删线,(3) 旋转,树,二叉树,5.5.1 树、森林与二叉树之间的转换,2. 二叉树转换成树的规则：,是树转换成二叉树的逆过程：,(1) 加线,(2) 删线,(3) 旋转,二叉树,树,5.5.1 树、森林与二叉树之间的转换,3. 森林转换成二叉树