第6章 树和二叉树课件

第6章树和二叉树树型结构是一类非常重要的非线性结构，它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象。因此在计算机领域里有着广泛应用。如：操作系统中的文件管理编译程序中的语法结构数据库系统信息组织形式第6章树和二叉树第6章树和二叉树祖父父亲伯父叔叔堂兄堂弟兄弟我长子次子孙子孙子第6章树和二叉树主要内容6.1树及其抽象数据类型6.2二叉树及其抽象数据类型6.3二叉树的表示和实现6.4线索二叉树6.5哈夫曼编码与哈夫曼树6.6树的表示目的：理解树结构。要求：掌握二叉树的表示和实现。重点：二叉树实现，哈夫曼树。难点：哈夫曼树。第6章树和二叉树6.1树及其抽象数据类型6.1.1树定义6.1.2树的术语6.1.3树的表示法6.1.4树抽象数据类型第6章树和二叉树6.1.1树定义树（tree）是由n（n≥0）个结点组成的有限集合。n=0的树称为空树；n＞0的树T：有且仅有一个结点n0，它没有前驱结点，只有后继结点。n0称作树的根（root）结点。除结点外n0

，其余的每一个结点都有且仅有一个直接前驱结点；有零个或多个直接后继结点。（1）非递归定义ABCDEFGHJI第6章树和二叉树一颗大树分成几个大的分枝，每个大分枝再分成几个小分枝，小分枝再分成更小的分枝，…

，每个分枝也都是一颗树，由此我们可以给出树的递归定义。树（tree）是由n（n≥0）个结点组成的有限集合。n=0的树称为空树；n＞0的树T：有且仅有一个结点n0，它没有前驱结点，只有后继结点。n0称作树的根（root）结点。除根结点之外的其他结点分为m（m≥0）个互不相交的集合T0，T1，…，Tm-1，其中每个集合Ti（0≤i＜m）本身又是一棵树，称为根的子树（subtree）。（2）递归定义ABCDEFGHJI第6章树和二叉树举例第6章树和二叉树6.1.2树的术语父母、孩子与兄弟结点度结点层次、树的高度边、路径无序树、有序树森林第6章树和二叉树1.父母、孩子与兄弟结点结点的直接前驱结点称为父母（parents）结点。结点的直接后继结点称为孩子（child）结点。拥有同一个父母结点的多个结点之间称为兄弟（sibling）结点。结点的祖先（ancestor）是指从根结点到其父母结点所经过的所有结点。结点的后代（descendant）是指该结点的所有孩子结点，以及孩子的孩子等。祖先与后代的关系则是对父子关系的延伸，其定义了树中结点的纵向次序。ABCDEFGHJI第6章树和二叉树2.度结点的度（degree）是指结点所拥有子树的棵数。度为零的结点称为叶子（leaf）或者终端结点

度不为零的结点称为分支结点或者非终端结点、非叶结点。树的度是指树中各结点度的最大值。ABCDEFGHJI第6章树和二叉树3.结点层次、树的高度结点的层次（level）属性反映结点处于树中的层次位置。约定根结点的层次为1，其余结点的层次是其父母结点的层次加1.树的高度（height）或深度（depth）是树中结点的最大层次数。ABCDEFGHJI第6章树和二叉树4.边、路径设树中X结点是Y结点的父母结点，有序对（X，Y）称为连接这两个结点的分支，也称为边（edge）。设（X0，X1，…，Xk-1）是由树中结点组成的一个序列，且（Xi，Xi+1）（0≤i＜k-1）都是树中的边，则该序列称为X0到Xk-1的一条路径（path）。路径长度（pathlength）为路径上的边数。ABCDEFGHJI第6章树和二叉树5.无序树、有序树若把树中每个结点的各子树看成从左到右有次序的（即不能互换），则称该树为有序树（OrderedTree）；否则称为无序树（UnorderedTree）如果规定k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边，则定义了树中结点的横向次序ABCDEFGHJIABCACB第6章树和二叉树6.森林森林（Forest）是m（m≥0）棵互不相交树的集合。给森林加上一个根结点就变成一棵树。将树的根结点删除就变成森林。ABCDEFGHJIBCDEFGHJI树森林第6章树和二叉树6.1.3树的表示法1、用二元组描述2、用树型图表示3、用文氏图表示4、用凹入图表示5、用广义表表示第6章树和二叉树1、树的逻辑结构可以用二元组描述为：

Group=（D，R）有限个数据元素的集合这些数据元素间关系的集合D={A,B,C,D,E,F,G,H,I,J}R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<D,G>,<D,H>,<F,I>,<F,J>}ABCDEFGHJI第6章树和二叉树2、用树型图表示

3、用文氏图表示ABCDEFGHJICEGHDBIJFA第6章树和二叉树4、用凹入图表示

5、用广义表图表示ABEFIJCDGHA（B（E，F（I，J）），C，D（G，H））ABCDEFGHJI第6章树和二叉树6.1.4树抽象数据类型(TTree.java)publicinterfaceTTree<E>{//树接口

booleanisEmpty();//判断是否空树

EgetRoot(); //返回根结点元素

EgetParent(Echild);//返回child的父母结点

intgetChildCount(Eparent);//返回parent孩子结点数

EgetFirstChild(Eparent);//返回parent的孩子结点

EgetNextSibling(Eelement);//返回下一个兄弟结点

voidtraverse();//遍历树

voidinsert(Eparent,Eelement);//插入作为parent的孩子

voidremove(Eparent);//删除以parent为根的子树

voidclear();//清空}第6章树和二叉树6.2二叉树及其抽象数据类型6.2.1二叉树定义6.2.2二叉树性质6.2.3二叉树抽象数据类型许多实际问题抽象出来的数据结构往往是二叉树的形式。即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法相比于树来说较为简单。因此将重点讨论二叉树的性质、存储以及常用的算法。第6章树和二叉树6.2.1二叉树定义二叉树（binarytree）是由n（n≥0）个结点组成的有限集合，此集合或者为空，或者由一个根结点加上两棵分别称为左、右子树的，互不相交的二叉树组成。二叉树可以为空集，因此根可以有空的左子树或者右子树，亦或者左、右子树皆为空。

第6章树和二叉树二叉树有别于度数为2的有序树，在二叉树中允许某些结点只有右子树而没有左子树；而有序树中，一个结点如果没有第一子树就不可能有第二子树的存在。第6章树和二叉树思考画出3个结点的无序树和二叉树的基本形态。第6章树和二叉树6.2.2二叉树性质性质1：若根结点的层次为1，则二叉树第i层最多有2i

1（i≥1）个结点。证明：用数学归纳法证明：

归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。

归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。

归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。

第6章树和二叉树性质2：在高度为k的二叉树中，最多有2k

1个结点（k≥0）。证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：

20+21+…+2k-1=2k-1第6章树和二叉树性质3：设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。证明：因为二叉树中所有结点的度均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点和2度结点数之和：

n=n0+n1+n2 (式子1)

另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2

树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：

n=n1+2n2+1 (式子2)

由式子1和式子2得到：

n0=n2+1

ABCEF第6章树和二叉树满二叉树(FullBinaryTree)

一棵高度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点：

（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。

（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。

ABCDEFG第6章树和二叉树完全二叉树(CompleteBinaryTree)

若一棵二叉树至多只有最下面的两层上结点的度可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

第6章树和二叉树完全二叉树的特点：（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树就是一棵完全二叉树。（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

第6章树和二叉树性质4

具有n个结点的完全二叉树的高度为：

证明：设所求完全二叉树的高度为k。由完全二叉树定义可得：高度为k得完全二叉树的前k-1层是高度为k-1的满二叉树，一共有2k-1-1个结点。

由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：n>2k-1-1。

另一方面，由性质2可得：n≤2k-1，即：

2k-1-1<n≤2k-1

由此可推出：2k-1≤n<2k，取对数后有：

k-1≤log2n<k

又因k-1和k是相邻的两个整数，故有

k-1=

由此即得：

k=+1第6章树和二叉树给二叉树结点编号

在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。

ABCDEFG0413265（a）完全二叉树第6章树和二叉树性质5：一棵具有n个结点的完全二叉树，对序号为i（0≤i＜n）的结点，有：若i=0，则i为根结点，无父母结点；若i>0，则i的父母结点序号为:。若2i+1＜n，则i的左孩子结点序号为2i+1；否则i无左孩子。若2i+2＜n，则i的右孩子结点序号为2i+2；否则i无右孩子。第6章树和二叉树6.2.3二叉树抽象数据类型(BinaryTTree.java)publicinterfaceBinaryTTree<E>{//二叉树接口

booleanisEmpty(); //判断是否空二叉树

intcount(); //返回二叉树的结点个数

intheight(); //返回二叉树的高度

BinaryNode<E>getRoot();//返回二叉树的根结点

BinaryNode<E>getParent(BinaryNode<E>node);//返回node父母结点

voidpreOrder(); //先根次序遍历二叉树

voidinOrder(); //中根次序遍历二叉树

voidpostOrder(); //后根次序遍历二叉树

voidlevelOrder(); //按层次遍历二叉树

BinaryNode<E>search(Eelement);//查找并返回元素为element结点

voidinsert(BinaryNode<E>p,Eelement,booleanleftChild);//插入element元素作为p结点的左/右孩子

voidremove(BinaryNode<E>p,booleanleftChild);//删除p的左/右子树

voidclear(); //清空}第6章树和二叉树6.3二叉树的表示和实现6.3.1二叉树的存储结构6.3.2二叉树的二叉链表实现6.3.3二叉树的遍历6.3.4构造二叉树6.3.5二叉树的插入和删除操作6.3.6二叉树遍历的非递归算法6.3.7二叉树的层次遍历第6章树和二叉树6.3.1二叉树的存储结构1、二叉树的顺序存储结构二叉树的顺序存储结构是把把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。在二叉树的顺序存储结构中只存储结点的值（数据域），结点在这个序列中的相互位置决定结点之间的逻辑关系。二叉树顺序存储的原则是：不管给定的二叉树是不是完全二叉树，都看作完全二叉树，即按完全二叉树的层次次序（从上到下，从左到右）把各结点依次存入数组中第6章树和二叉树（1）编号办法在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列

ABCDEFG0413265（a）完全二叉树ABCD0413265（b）一般二叉树第6章树和二叉树

该编号方案中，由某结点的编号可以推出其父亲、左儿子、右儿子及兄弟的编号，假设给定结点的编号为i（0≤i<n），则：（1）若i＝0，则该结点是为根结点，无父亲。（2）若i≠0，则该结点的父亲结点编号为(i-1)／2的整数部分。（3）若2i+1<n，则该结点的左儿子结点编号为2i+1，否则该结点无左儿子。该结点必为叶子结点。（4）若2i+2<n，则该结点的右儿子结点编号为2i+2，否则该结点无右儿子。（5）若i为偶数（不为0），则该结点的左兄弟为i-1。（6）若i为奇数（不为n-1），则该结点的右兄弟为i+1。（2）编号特点ABCDEFG0413265ABCD0413265第6章树和二叉树将二叉树中所有结点按编号顺序依次存储在一个数组中。具体实现

ABCDEFG0413265ABCD0413265ABCDEF012345G6ABC012345D6第6章树和二叉树若一个二叉树如下所示，试给出其顺序存储。练习ABCD第6章树和二叉树二叉树顺序存储的优点和缺点

对完全二叉树而言，顺序存储结构既简单又节省存储空间。一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。【例】最坏的情况下，一个高度为k且只有k个结点的右单支二叉树需要2k-1个存储单元。在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。第6章树和二叉树2.二叉树的链式存储结构（1）二叉链表若一颗具有n个结点的二叉树用二叉链表存储，有多少个空链？第6章树和二叉树（2）三叉链表第6章树和二叉树6.3.2二叉树的二叉链表实现1、二叉链表结点类（BinaryNode.java）

packagedataStructure.tree;publicclassBinaryNode<E>{publicEdata;publicBinaryNode<E>left,right;\\成员方法}datarightleft第6章树和二叉树构造方法publicBinaryNode(Edata,BinaryNode<E>left,BinaryNode<E>right){this.data=data;this.left=left;this.right=right;}publicBinaryNode(Edata){this(data,null,null);}publicBinaryNode(){this(null,null,null);}第6章树和二叉树

publicbooleanisLeaf(){returnthis.left==null&&this.right==null;}publicStringtoString(){returnthis.data.toString();}第6章树和二叉树packagedataStructure.tree;importdataStructure.tree.BinaryNode;publicclassBinaryTree<E>{protectedBinaryNode<E>root;publicBinaryTree(){root=null;}publicBinaryTree(BinaryNode<E>root){this.root=root;}publicbooleanisEmpty(){returnthis.root==null;}publicBinaryNode<E>getRoot(){returnthis.root;} //跟二叉树相关的其他操作}2、二叉树类（BinaryTree.java）AdatarightleftC^G^^E^^BD^^root第6章树和二叉树6.3.3二叉树的遍历遍历（traversal）二叉树就是按照一定规则和次序访问二叉树种的所有结点，并且每个结点仅被访问一次。一次完整的遍历就是按照某种顺序，使得二叉树中的所有结点产生一个线性序列。第6章树和二叉树遍历的种类非空二叉树根结点D左子树L右子树RP3=63DLR

LDR

LRDDRL

RDL

RLD先左后右先右后左先根遍历中根遍历后根遍历层序遍历DLR第6章树和二叉树1、二叉树的三种次序遍历先根次序：访问根结点，遍历左子树，遍历右子树。中根次序：遍历左子树，访问根结点，遍历右子树。后根次序：遍历左子树，遍历右子树，访问根结点。先根遍历序列：ABDGCEFH中根遍历序列：DGBAECHF后根遍历序列：GDBEHFCA第6章树和二叉树2、二叉树三种次序遍历的递归算法若二叉树为空二叉树，则算法结束；否则先访问根结点，再先根遍历左子树最后先根遍历右子树ABDECABCDEroot先根遍历二叉树递归算法第6章树和二叉树实现publicvoidpreOrder(){System.out.print("\npreOrderis:");preOrder(root);}privatevoidpreOrder(BinaryNode<E>p){if(p!=null){System.out.print(p.data+"");preOrder(p.left);preOrder(p.right);}}ABDECABCDEroot第6章树和二叉树中根遍历二叉树递归算法若二叉树为空二叉树，则算法结束；否则先中根遍历左子树再访问根结点，最后中根遍历右子树DBEACABCDEroot第6章树和二叉树实现publicvoidinOrder(){System.out.print("\ninOrderis:");inOrder(root);}privatevoidinOrder(BinaryNode<E>p){if(p!=null){inOrder(p.left);System.out.print(p.data+"");inOrder(p.right);}}DBEACABCDEroot第6章树和二叉树后根遍历二叉树递归算法若二叉树为空二叉树，则算法结束；否则先后根遍历左子树再后根遍历右子树最后访问根结点，DEBCAABCDEroot第6章树和二叉树实现publicvoidpostOrder(){System.out.print("\npostOrderis:");postOrder(root);}privatevoidpostOrder(BinaryNode<E>p){if(p!=null){postOrder(p.left);postOrder(p.right);System.out.print(p.data+"");}}DEBCAABCDEroot第6章树和二叉树P139【例6.1】构造并遍历二叉树Traverse.java先根遍历序列：ABDGCEFH中根遍历序列：DGBAECHF后根遍历序列：GDBEHFCA第6章树和二叉树3、基于遍历的操作（1）求结点个数

publicintcount(){returncount(root);}publicintcount(BinaryNode<E>p){if(p!=null)return1+count(p.left)+count(p.right);elsereturn0;}DLR第6章树和二叉树（2）求高度

publicintdepth(){returndepth(root);}publicintdepth(BinaryNode<E>p){if(p!=null){intld=depth(p.left);intrd=depth(p.right);return(ld>=rd)?ld+1:rd+1;}return0;}DLR第6章树和二叉树（3）查找publicBinaryNode<E>search(Evalue){returnsearch(root,value);}publicBinaryNode<E>search(BinaryNode<E>p,Evalue){BinaryNode<E>find=null;if(p!=null&&value!=null){if(p.data.equals(value))find=p;else{find=search(p.left,value);if(find==null)find=search(p.right,value);}}returnfind;}DLR第6章树和二叉树（4）获得父母结点

publicBinaryNode<E>getParent(BinaryNode<E>node){if(root==null||node==null||node==root)returnnull;returngetParent(root,node);}publicBinaryNode<E>getParent(BinaryNode<E>p,BinaryNode<E>node){BinaryNode<E>find=null;if(p!=null){if(p.left==node||p.right==node)find=p;else{find=getParent(p.left,node);if(find==null)find=getParent(p.right,node);}}returnfind;}DLR算法时间复杂度是O（n）第6章树和二叉树三种遍历总结先根遍历序列：ABDEC中根遍历序列：DBEAC后根遍历序列：DEBCAABCDE先根遍历序列中的第一个元素一定是整个二叉树的根结点中根遍历根结点会把两个左右子树中的结点分隔开来。后根遍历序列中的最后一个元素也一定是整个二叉树的根结点第6章树和二叉树思考题先根中根后根ABDCEBDAECCBEDAFIGHCEDBIFHGA已知一个二叉树的先根遍历序列和中根遍历序列，能否唯一决定一个二叉树？如果能，请画出这个二叉树，并给出它的后根遍历序列。已知一个二叉树的后根遍历序列和中根遍历序列，能否唯一决定一个二叉树？如果能，请画出这个二叉树，并给出它的先根遍历序列。已知一个二叉树的先根遍历序列和后根遍历序列，能否唯一决定一个二叉树？如果不能，请举例证明。第6章树和二叉树思考题解答先根中根后根ABDCEBDAECABCDE（B,D）（E,C）A（B,D）（E,C）BCA（B,D）（E,C）第6章树和二叉树先根中根后根CBEDAFIGHCEDBIFHGAA（C,B,E,D）（F,I）B（E,D）CGH（F,I,G,H）DEFI第6章树和二叉树6.3.4构造二叉树1、先根和中根序列表示2、标明空子树的先根序列表示3、广义表表示4、以完全二叉树的层次遍历序列构造链式存储结构的完全二叉树

建立一颗二叉树必须明确两点：结点与父母结点及孩子结点之间的层次关系。兄弟结点间的左右子树的次序关系。第6章树和二叉树1、先根和中根序列表示证明：设二叉树的先根和中根遍历序列分别用数组preorder和inorder表示。（1）由先根遍历序列知，该二叉树的根为：preorder[0]。（2）在inorder中一定存在下标i，使得inorder

[i]==

preorder[0];ABDCE下标01ii+1n-1preorder根左子树右子树BDAEC下标0i-1ii+1n-1inorder根左子树右子树第6章树和二叉树由中根遍历知，inorder[i]之前的结点在根的左子树上，inorder[i]之后的结点在根的右子树上，因此，根的左子树由i个结点组成：先根序列——preorder[1],…,preorder[i];根序序列——inorder[0],…,inorder[i-1];根的右子树由n-1-i个结点组成：先根序列——preorder[i+1],…,preorder[n-1];中根序列——inorder[i+1],…,inorder[n-1];（3）依次递归，可建立唯一的一颗二叉树。ABDCE下标01ii+1n-1preorder根左子树右子树BDAEC下标0i-1ii+1n-1inorder根左子树右子树A（B,D）（E,C）第6章树和二叉树2、标明空子树的先根序列表示第6章树和二叉树算法描述数组preorder表示一颗二叉树标明空子树的先根次序遍历序列，构造二叉树的递归算法描述如下：（1）preorder[0]一定是二叉树的根，创建根结点；preorder[1]一定是根的左孩子。（2）若preorder[i]不是“.”，则创建一个结点，该结点的左孩子结点元素是preorder[i+1]，但父母与孩子之间的链还未建立；否则当前子树为空，返回上一层结点。（3）返回到当前结点时，下一个元素preorder[i+1]是当前结点的右孩子结点；当一个结点的左右孩子链已建立，则以当前结点为根的一颗子树就已建好，返回上一层结点。（4）重复执行步骤2～3，直到返回根结点，则二叉树建成，使root指向根结点。第6章树和二叉树datarightleftA^^ABD.G...CE..FH...012345678910111213141516A^^B^^A^^B^^D^^p第6章树和二叉树A^^B^^D^pG^^A^^B^D^G^^pA^B^D^G^^pABD.G...CE..FH...012345678910111213141516第6章树和二叉树publicBinaryTree(E[]preorder){root=create(preorder);}privateinti=0;privateBinaryNode<E>create(E[]preorder){BinaryNode<E>p=null;if(i<preorder.length){Eelem=preorder[i];i++;if(elem!=null){p=newBinaryNode<E>(elem);p.left=create(preorder);p.right=create(preorder);}}returnp;}构造方法：第6章树和二叉树【例6.2】输出二叉树中指定结点的所有祖先结点。Ancestors.java第6章树和二叉树3、广义表表示广义表可以表示一棵树，但不能唯一表示一颗二叉树。ABABA（B）第6章树和二叉树第6章树和二叉树4.以完全二叉树的层次遍历序列构造链式存储结构的完全二叉树

【例6.3】建立二叉链表表示的完全二叉树。CompleteBinaryTree.javaABCDEFGH完全二叉树的层次遍历序列：ABCDEFGH第6章树和二叉树6.3.5二叉树的插入和删除操作1、插入一个结点

publicvoidinsert(BinaryNode<E>p,Eelement,booleanleftChild){if(p!=null){BinaryNode<E>q=newBinaryNode<E>(element);if(leftChild){q.left=p.left;p.left=q;}else{q.right=p.right;p.right=q;}}}第6章树和二叉树插入一个结点，作为p的左孩子结点

publicvoidinsert(BinaryNode<E>p,Eelement){insert(p,element,true);}第6章树和二叉树2、删除一棵子树publicvoidremove(BinaryNode<E>p,booleanleftChild){if(p!=null){if(leftChild)p.left=null;elsep.right=null;}}publicvoidremove(BinaryNode<E>p){remove(p,true);}第6章树和二叉树6.3.6二叉树遍历的非递归算法二叉树的二叉链表存储中每个结点都缺少指向其父母结点的链，因此，必须借助辅助的数据结构完成非递归遍历。应该选择具有“后进先出”特点的——栈第6章树和二叉树1.初始化一个空栈。2.从二叉树的根结点p开始，如果p不空或栈不空，循环执行以下操作。1)如果p不空，表示到达了一个结点，将结点p入桟，并进入其左子树。2)如果p为空而栈不空，表明已经沿着某条路径走出了二叉树，此时需返回访问这条路径起始的这个结点，而该结点正好被保存在栈的栈顶，因此弹出栈顶元素并让p指向它，接下来访问结点p，然后进入其右子树。3.算法结束算法描述第6章树和二叉树第6章树和二叉树第6章树和二叉树第6章树和二叉树代码见：BinaryTree.java中的inOrderTraverse()方法第6章树和二叉树6.3.7二叉树的层次遍历层次遍历：是指从二叉树的第1层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。层序遍历需要借助具有先进现出特点的——队列实现。层次遍历序列：ABCDEFG第6章树和二叉树1.初始化一个空队。2.从二叉树的根结点p开始，如果p不空时，循环执行以下操作。1)访问P结点；2)如果P存在左孩子结点，将左孩子结点入队；3)如果P存在右孩子结点，将右孩子结点入队；4)p指向出队结点，继续，直到队列为空。3.算法结束。算法描述第6章树和二叉树第6章树和二叉树第6章树和二叉树实现publicvoidlevelOrder(){LinkedQueue<BinaryNode<E>>que=new

LinkedQueue<BinaryNode<E>>();BinaryNode<E>p=this.root;System.out.print("levelOrderis:

");while(p!=null){System.out.print(p.data+"");if(p.left!=null)que.enqueue(p.left);if(p.right!=null)que.enqueue(p.right);p=que.dequeue();}System.out.println();}第6章树和二叉树演示：二叉树的操作BinaryTree_ex.java第6章树和二叉树6.5哈夫曼编码与哈夫曼树6.5.1哈夫曼编码6.5.2哈夫曼树第6章树和二叉树编码方案讨论什么是编码和解码（译码）？编码：将文件中的每个字符均转换为一个唯一的二进制位串。解码：将二进制位串转换为对应的字符。1、等长编码方案2、变长编码方案ASCII编码Unicode编码专用等长编码6.5.1哈夫曼编码第6章树和二叉树1、等长编码方案等长编码方案将给定字符集C中每个字符的码长固定为：，|C|表示字符集的大小。如：ASCII编码对每个字符采用8位二进制编码Unicode编码对每个字符采用16位二进制编码【例】语句：Ifawoodchuckcouldchuckwood！一共由32个字符组成（包括空格和标点符号）。如果每个字符采用Unicode编码，一共需要多少位？答：32×16＝512位。如果每个字符采用ASCII编码，一共需要多少位？答：32×8＝256位。但实际上上述的字符串中只有13个不同的字符，每个字符采用4位表示足已。一共需要多少位？答：32×4＝128位。第6章树和二叉树2、变长编码方案每个字符的编码长度不固定，一般的做法是将频度高的字符编码编成短码，将频度低的字符编成长码。

Ifawoodchuckcouldchuckwood！采用变长编码第6章树和二叉树等长、变长编码对比变长编码可以压缩数据量，从而节省存储空间，加快数据的传输。但等长编码解码时很方便，不会出现解码歧义问题。而变长编码就有可能会出现解码歧义问题产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分（称为前缀）相同。

【例】设E、T、W分别编码为00、01、0001，则解码时无法确定信息串0001是ET还是W。第6章树和二叉树哈夫曼编码因此对字符集进行编码时，要求字符集中任一字符的编码都不是其余字符编码的前缀。我们用哈夫曼树可以实现满足这种要求的编码，并且用这样的编码可以使得编码总长度最短。我们称这种编码为哈夫曼编码。第6章树和二叉树AAAABBBCDDBBAAA00001010101111101101010000存储“AAAABBBCDDBBAAA”，字符集[A、B、D、C]，字符出现次数为7、5、2、1，频率为0.47、0.33、0.13、0.07，哈夫曼编码过程为：第6章树和二叉树6.5.2哈夫曼树CDBA0001111257A：0B：10C：111D：110第6章树和二叉树从根结点到所有结点的路径长