第7讲 树和二叉树

1、第7讲 树和二叉树 7.1 树树 7.2 二叉树二叉树 7.3 二叉树的设计二叉树的设计 7.4 线索二叉树线索二叉树 7.5树与二叉树的转换树与二叉树的转换 本章主要知识点：本章主要知识点：树的定义、表示方法和存储结构树的定义、表示方法和存储结构二叉树的定义、性质和存储结构，满二叉树和二叉树的定义、性质和存储结构，满二叉树和完全二叉树的概念完全二叉树的概念二叉树的前序、中序、后序和层序遍历算法二叉树的前序、中序、后序和层序遍历算法二叉树中序和层序游标类的设计方法二叉树中序和层序游标类的设计方法线索二叉树的基本概念线索二叉树的基本概念哈夫曼树和哈夫曼编码，哈夫曼编码的软件设哈夫曼树和哈夫曼编码

2、，哈夫曼编码的软件设计方法计方法树与二叉树的转换，树的遍历树与二叉树的转换，树的遍历7.1 树 7.1.1 树的定义树的定义 树树是由是由n（n0）个结点构成的满足以下条件的结点集合：）个结点构成的满足以下条件的结点集合： （1）当）当n0时，有一个特殊的结点称为根结点，根结点时，有一个特殊的结点称为根结点，根结点没有前驱结点；没有前驱结点； （2）当）当n1时，除根结点外的其他结点被分成时，除根结点外的其他结点被分成m（m0）个互不相交的集合个互不相交的集合T1, T2, Tm，其中每一个集合，其中每一个集合Ti（1im）本身又是一棵结构和树结构类同的子树）本身又是一棵结构和树结构类同的子树

3、。A只有根结点的树ABCDEFGHIJKLM有子树的树根子树树的表示法树的表示法树的基本术语 结点表示树中的元素，包括数据项及若干指向其子树的分支 结点的度结点拥有的子树数 叶子度为0的结点，也叫终端结点 分支结点度不为0的结点，也叫非终端结点 内部结点除根结点之外，分支结点也称为内部结点 树的基本术语 树的度一棵树中最大的结点度数 孩子结点子树的根称为该结点的孩子 双亲孩子结点的上层结点叫该结点的双亲 兄弟同一双亲的孩子之间互成为兄弟 祖先结点的祖先是从根到该结点所经分支上的所有结点 子孙以某结点为根的子树中的任一结点都成为该结点的子孙树的基本术语 结点的层次从根结点算起，根为第一层，它的孩

4、子为第二层 堂兄弟其双亲在同一层的结点互称为堂兄弟。 深度树中结点的最大层次数 有序树 如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 森林m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先 7.

5、1.2 树的表示方法树的表示方法 1 直观表示法直观表示法 2 形式化表示法形式化表示法 树的形式化表示法主要用于树的理论描述。树树的形式化表示法主要用于树的理论描述。树的形式化表示法定义树的形式化表示法定义树T为为T=（D，R）其中）其中D为为树树T中结点的集合，中结点的集合，R为树为树T中结点之间关系的集中结点之间关系的集合。当树合。当树T为空树时为空树时D=；当树；当树T不为空树时有不为空树时有D=RootDF，其中，其中Root为树为树T的根结点，的根结点，DF为树为树T的根的根Root的子树集合，的子树集合，DF可由下式表示：可由下式表示： DF = D1D2Dm （1i, jm,

6、DiDj=） 7.1.3 树的基本操作树的基本操作 （1）双亲结点）双亲结点parent() （2）左孩子结点）左孩子结点leftChild() （3）右兄弟结点）右兄弟结点rightSibling() （4）遍历树）遍历树traverse(vs) 7.1.4 树的存储结构树的存储结构 1 双亲表示法双亲表示法 双亲表示法就是用指针表示出每个结点双亲表示法就是用指针表示出每个结点的双亲结点。的双亲结点。 对于使用仿真指针的双亲表示法来说，对于使用仿真指针的双亲表示法来说，每个结点应有两个域，一个是数据元素域，每个结点应有两个域，一个是数据元素域，另一个是指示其双亲结点在数组中下标序号另一个是指

7、示其双亲结点在数组中下标序号的仿真指针域。的仿真指针域。 树及其使用仿真指针的双亲表示法树及其使用仿真指针的双亲表示法 2 孩子表示法孩子表示法 孩子表示法就是用指针表示出每个结点的孩子孩子表示法就是用指针表示出每个结点的孩子结点。结点。 常规指针的孩子表示法常规指针的孩子表示法 3 双亲孩子表示法双亲孩子表示法 双亲孩子表示法就是用指针既表示出每个双亲孩子表示法就是用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结结点的双亲结点，也表示出每个结点的孩子结点。点。 4 孩子兄弟表示法孩子兄弟表示法 由于每个结点的孩子数可以变化很大并且事由于每个结点的孩子数可以变化很大并且事先不知道，建

8、立到各个孩子结点的链接不可行先不知道，建立到各个孩子结点的链接不可行 class TreeNode Object element; TreeNode firstChild; /第一个孩子第一个孩子 TreeNode nextSibling; /下一个兄弟下一个兄弟 4 孩子兄弟表示法孩子兄弟表示法 孩子兄弟表示法就是用指针既表示出每个结孩子兄弟表示法就是用指针既表示出每个结点的孩子结点，也表示出每个结点的兄弟结点。点的孩子结点，也表示出每个结点的兄弟结点。7.9 树的遍历及应用 树的用法之一就是许多操作系统中的目录结构 如果要列出目录中所有文件的名字，输出格式是：层次为di的文件将在di次跳格

9、（tab）缩进后打印其名 private void listAll(int depth) printName(depth); /Print the name of the object; if(isDeirectory() for each file c in this directory (for each child) c.listAll(depth+1); public void listAll() listAll(0); 1 先根遍历先根遍历 树的先根遍历递归算法为：树的先根遍历递归算法为： （1）访问根结点；）访问根结点； （2）按照从左到右的次序先根遍历根结点的每）按照从左到右的次

10、序先根遍历根结点的每一棵子树。一棵子树。 在每个结点上的工作量是常数。如果有在每个结点上的工作量是常数。如果有N个文件个文件名需要输出，则运行时间就是名需要输出，则运行时间就是O(N) 2 后根遍历后根遍历 树的后根遍历递归算法为：树的后根遍历递归算法为： （1）按照从左到右的次序后根遍历根结点的每一）按照从左到右的次序后根遍历根结点的每一棵子树；棵子树； （2）访问根结点。）访问根结点。 例如：计算文件系统某目录下所有文件占用的磁例如：计算文件系统某目录下所有文件占用的磁盘区块的总数（由于目录也是文件，也有大小）盘区块的总数（由于目录也是文件，也有大小） public int size()

11、int totalSize=sizeOfThisFile(); if(isDirectory() for each file c in this directory(for each child) totalSize+=c.size(); return totalSize(); 先根遍历得到的结点序列为：先根遍历得到的结点序列为：A B E J F C G K L D H I后根遍历得到的结点序列为：后根遍历得到的结点序列为：J E F B K L G C H I D AABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：AB E F I GCDHJ KL NOME I F G B C

12、 J K N O L M H D AAB C DE F GH I J KL MNO一般树的遍历（续）一般树的遍历（续）7.2二叉树的定义及特点 定义： 二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成。 特点：1）每个结点至多有二棵子树(即不存在度大于2的结点)2）二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的五种基本形态图5.3二叉树的五种基本形态（a）空二叉树（b）仅有根结点的二叉树（c）右子树为空的二叉树（d）左、右子树均非空的二叉树（e）左子树为空的二叉树(a)(b)(c)(d)(e)满二叉树定义：一颗深度为k的满二叉

13、树，是由k 个结点的深度为K的二叉树。k -个结点是二叉树所具有的最大结点个数。为从第一层的结点（即根）便于访问满二叉树的结点，对满二叉树开始，自上而下，从左到右，按顺序给结点编号，便得到满二叉树的一个顺序表。 12349851110图5.4 满二叉树6131271514完全二叉树定义：一颗具有n个结点、深度为K的二叉树，当且仅当其所有结点对应于深度为k的满二叉树中编号由1到n的那些结点时，该二叉树便是完全二叉树。112623749851110图5.5 完全二叉树1231145891213671014151231145891267101234567123456 7.2.2 二叉树的基本操作二叉

14、树的基本操作 （1）双亲结点）双亲结点parent()： （2）左孩子结点）左孩子结点leftChild() （3）右孩子结点）右孩子结点rightSibling() （4）左插入结点）左插入结点insertLeftNode(x) （5）右插入结点）右插入结点insertRightNode(x)： （6）左删除子树）左删除子树deleteLeftTree() （7）右删除子树）右删除子树deleteRightTree() （8）遍历二叉树）遍历二叉树traverse(vs) 7.2.3 二叉树的性质二叉树的性质 性质性质1 若规定根结点的层次为若规定根结点的层次为0，则一棵非，则一棵非空二叉树

15、的第空二叉树的第i层上最多有层上最多有2i（i0）个结点。）个结点。 性质性质2 若规定空二叉树树的深度为若规定空二叉树树的深度为-1(即根即根结点的深度为结点的深度为0)，则深度为，则深度为k的二叉树的最大的二叉树的最大结点数是结点数是2k+1-1（k-1）个。）个。 性质性质3 具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度k为不超过为不超过log2(n+1)-1的最大整数。的最大整数。 性质性质4 对于一棵非空的二叉树，如果叶结对于一棵非空的二叉树，如果叶结点个数为点个数为n0，度为，度为2的结点数为的结点数为n2，则有，则有n0= n2+1。 性质性质5 对于具有对于具有n

16、个结点的完全二叉树，如果按照个结点的完全二叉树，如果按照从上至下和从左至右的顺序对所有结点从从上至下和从左至右的顺序对所有结点从0开始顺序开始顺序编号，则对于序号为编号，则对于序号为i的结点，有：的结点，有： （1）如果）如果i0，则序号为，则序号为i结点的双亲结点的序结点的双亲结点的序号为号为 (i-1)/2（“/”表示整除）；如果表示整除）；如果i=0，则序号为，则序号为i结点为根结点，无双亲结点。结点为根结点，无双亲结点。 （2）如果）如果2i+1n，则序号为，则序号为i结点的左孩子结点的左孩子结点的序号为结点的序号为2i+1；如果；如果2i+1n，则序号为，则序号为i结结点无左孩子结点

17、。点无左孩子结点。 （3）如果）如果2i+2BDCD L RL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历: L R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:B二叉树的遍历练习112623749851110图5.5 完全二叉树先根次序遍历：1,2,4,8,9,5,10,11,3,6,12,7中根次序遍历：8,4,9,2,10,5,11,1,12,6,3,7后根次序遍历：8,9,4,10,11,5,2,12,6,7,3,1 除前序、中序和后序遍历算法外，二叉树还除前序、中序和后序遍历算法外，二叉树还有层序遍历。层序遍历的

18、要求是：按二叉树的有层序遍历。层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。层中按先左子树再右子树的次序遍历二叉树。 二叉树的层序遍历算法如下：二叉树的层序遍历算法如下： （1）初始化设置一个队列；）初始化设置一个队列； （2）把根结点指针入队列；）把根结点指针入队列； （3）当队列非空时，循环执行步骤（）当队列非空时，循环执行步骤（3.a）到步）到步骤（骤（3.c）；）； （3.a）出队列取得当前队头结点，访问该结点；）出队列取得当前队头结点，访问该结点； （3.b）若该结点的左孩子结点非空

19、，则将该结）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列；点的左孩子结点指针入队列； （3.c）若该结点的右孩子结点非空，则将该结）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列；点的右孩子结点指针入队列； （4）结束。）结束。 7.3.3 二叉树遍历的应用二叉树遍历的应用 1 打印二叉树打印二叉树 2 查找数据元素查找数据元素 7.3.4 应用举例应用举例 表达式树：叶子是操作数，其他结点为表达式树：叶子是操作数，其他结点为操作符，只考虑操作是二元的情况操作符，只考虑操作是二元的情况+ab*c *g*fde中序遍历的结果是中缀表达式；后序遍历的结果是后缀表达式构造表

20、达式树 把后缀表达式变成表达式树，方法类似后缀求值算法：一次一个符号地读入表达式，如果是操作数，那么就建立一个单节点树并将它入栈，如果是操作符，那么就冲栈中弹出两棵树T1和T2并形成一棵新树，该树的根就是操作符，然后将这棵新树入栈例如：ab+cde+* 7.3.5 非递归的二叉树遍历算法非递归的二叉树遍历算法 非递归的二叉树前序遍历算法如下：非递归的二叉树前序遍历算法如下： （1）初始化设置一个堆栈；）初始化设置一个堆栈； （2）把根结点指针入栈；）把根结点指针入栈； （3）当堆栈非空时，循环执行步骤（）当堆栈非空时，循环执行步骤（3.a）到步）到步骤（骤（3.c）；）； （3.a）出栈取得栈

21、顶结点，访问该结点；）出栈取得栈顶结点，访问该结点； （3.b）若该结点的右孩子结点非空，则将该结）若该结点的右孩子结点非空，则将该结点的右孩子点的右孩子 结点指针入栈；结点指针入栈； （3.c）若该结点的左孩子结点非空，则将该结）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入栈；点的左孩子结点指针入栈； （4）结束。）结束。 对于上图所示的二叉树，非递归的二叉树前序遍历对于上图所示的二叉树，非递归的二叉树前序遍历算法的执行过程算法的执行过程 如下页图所示：如下页图所示：中根序遍历的非递归算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-

22、BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)pABCDEFGiP-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)ABCDEFGiP-A访问：C B E G D Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap=NULL(15)7.4 线索二叉树 把结点中指向前驱结点和后继结点的指针称为把结点中指向前驱结点和后继结点的指针称为线索线索。在二叉树的结点上加上线索的二叉树称作。在二叉树的结点上加上线索的二叉树称作线索二叉树线索二叉树。对二叉树以某种方法（如前序、中。对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的过程序或后序方法）遍历使