《叉树与树》PPT课件.ppt

《《叉树与树》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《叉树与树》PPT课件.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 二 叉 树与树n n树树形形结结构构是是一一种种十十分分重重要要的的数数据据结结构构。本本章讨论的二叉树、树和树林都属于树形结构。章讨论的二叉树、树和树林都属于树形结构。n n在在树树形形结结构构中中每每个个结结点点最最多多只只有有一一个个前前驱驱，但可有多个后继的结构。但可有多个后继的结构。n n它它们们的的共共同同之之处处是是都都表表示示了了一一种种具具有有层层次次的分支关系。的分支关系。5.1 二叉树及其抽象数据类型二叉树及其抽象数据类型 基本概念n n二二二二叉叉叉叉树树树树可可以以定定义义为为结结点点的的有有限限集集合合，这这个个集集合合或或者者为为空空集集，或或者者由由一一

2、个个根根及及两两棵棵不不相相交交的的分分别别称称作作这这个个根根的的左左左左子子子子树树树树和和右右右右子树子树子树子树的二叉树组成。的二叉树组成。n n二二叉叉树树的的定定义义是是个个递递归归定定义义。二二叉叉树树可可以以是是个个空空集集合合，这这时时的的二二叉叉树树称称为为空空空空二二二二叉叉叉叉树树树树。二二叉叉树树也也可可以以是是只只有有一一个个结结点点的的集集合，这个结点只能是根；它的左子树和右子树均是空二叉树。合，这个结点只能是根；它的左子树和右子树均是空二叉树。n n二二叉叉树树描描述述的的是是一一种种层层次次关关系系，除除了了根根节节点点外外其其余余节节点点都都有有且只有一个前

3、驱节点，所有节点可以有且只有一个前驱节点，所有节点可以有0 0到两个后继节点。到两个后继节点。n n二叉树的五种基本形态二叉树的五种基本形态二叉树的相关术语n n父父父父结结结结点点点点、左左左左（右右右右）子子子子结结结结点点点点、边边边边：若若节节点点x x是是根根节节点点，y y是是x x的的左左（右右）子子树树的的根根，则则称称x x是是y y的的父父节节点点，y y是是x x的的左左（右右）子子节点，有序对节点，有序对称作称作x x到到y y的边。的边。n n兄弟兄弟兄弟兄弟：具有同一个父节点的节点彼此称为兄弟。：具有同一个父节点的节点彼此称为兄弟。n n祖祖祖祖先先先先、子子子子孙

4、孙孙孙：若若节节点点y y在在以以节节点点x x为为根根的的左左（右右）子子树树中中，且且xyxy，则称，则称x x是是y y的祖先，的祖先，y y是是x x的子孙。的子孙。n n路路路路径径径径、路路路路径径径径长长长长度度度度：如如果果x x是是y y的的祖祖先先，又又有有x=xx=x0 0,x,x1 1,x,xn n=y=y满满足足x xi i为为x xi+1i+1的的父父节节点点，称称x x0 0,x,x1 1,x,xn n为为从从x x到到y y的的一一条条路路径径，n n称为路径长度。称为路径长度。n n结结结结点点点点的的的的层层层层数数数数：根根的的层层数数为为1 1，其其余余

5、节节点点的的层层数数等等于于其其父父节节点点的措施加的措施加1 1。n n结结结结点点点点的的的的度度度度数数数数：节节点点的的非非空空子子树树的的个个数数称称作作节节点点的的度度数数。二二叉叉树中节点的最大度数为树中节点的最大度数为2 2。n n二叉树的高度二叉树的高度二叉树的高度二叉树的高度：二叉树中结点的最大层数称为二叉树的高度。：二叉树中结点的最大层数称为二叉树的高度。n n树树树树叶叶叶叶、分分分分支支支支结结结结点点点点：左左（右右）子子树树均均为为空空二二叉叉树树的的节节点点称称作作树树叶；否则称为分支节点。叶；否则称为分支节点。特殊的二叉树特殊的二叉树n n满二叉树满二叉树满二

6、叉树满二叉树：如果一棵二叉树的任何结点或者是树叶，或有两棵：如果一棵二叉树的任何结点或者是树叶，或有两棵非空子树，则此二叉树称作满二叉树（离散数学中称此树是正非空子树，则此二叉树称作满二叉树（离散数学中称此树是正则的则的)。n n完全二叉树完全二叉树完全二叉树完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数：如果一棵二叉树至多只有最下面的两层结点度数可以小于可以小于2 2，其余各层结点度数都必须为，其余各层结点度数都必须为2 2，并且最下面一层的，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。二叉树。n

7、 n完全二叉树不一定是满二叉树。满二叉树不一定是完全二叉树。完全二叉树不一定是满二叉树。满二叉树不一定是完全二叉树。n n扩扩扩扩充充充充的的的的二二二二叉叉叉叉树树树树：把把原原二二叉叉树树的的结结点点都都变变为为度度数数为为2 2的的分分支支结结点点，也也就就是是说说，如如果果原原结结点点的的度度数数为为2 2，则则不不变变，度度数数为为1 1，则增加一个分支，度数为则增加一个分支，度数为0 0（树叶），则增加两个分支。（树叶），则增加两个分支。n n新新增增加加的的结结点点（树树叶叶结结点点）都都用用小小方方框框表表示示，称称为为外外外外部部部部结结结结点点点点，树中原有的结点称为树中原

8、有的结点称为内部结点内部结点内部结点内部结点。n n由由 非非 空空 二二 叉叉 树树 扩扩 充充 的的 二二 叉叉 树树 都都 是是 满满 二二 叉叉 树树。把把空空二二叉叉树树扩扩充充得得到到的的扩扩充充二二叉叉树树规规定定为为只只有有一一个个外外部部结结点点组成的二叉树。组成的二叉树。n n在在扩扩充充的的二二叉叉树树中中，外外外外部部部部路路路路径径径径长长长长度度度度E E定定义义为为在在扩扩充充的的二二叉叉树树中中从从根根到到每每个个外外部部结结点点的的路路径径长长度度之之和和。内内内内部部部部路路路路径径径径长长长长度度度度I I定定义义为为在在扩扩充充的的二二叉叉树树中中从从根

9、根到到每每个内部结点的路径长度之和。个内部结点的路径长度之和。n n如在图的扩充二叉树中：如在图的扩充二叉树中：E=2+2+4+4+3+3+3=21E=2+2+4+4+3+3+3=21I=0+1+1+2+2+3=9I=0+1+1+2+2+3=95.1.2 主要性质n n性性性性质质质质1 1 在在非非空空二二叉叉树树的的i i层层上上至至多多有有2 2i i个个结结点点(i0)(i0)。证明：用归纳法来证。证明：用归纳法来证。n n性质性质性质性质2 2 高度为高度为k k的二叉树中最多有的二叉树中最多有2 2k+1k+1-1-1个结点个结点(k0)(k0)。证明：假设第证明：假设第i i层上

10、的最大结点个数是层上的最大结点个数是mmi i，由性质，由性质1 1可知，深度为可知，深度为k k的二叉树中最大结点个数的二叉树中最大结点个数MM为为:n n性性性性质质质质3 3 对对于任何一棵非空的二叉于任何一棵非空的二叉树树，如果叶，如果叶结结点个数点个数为为n n0 0，度度为为2 2的的结结点个数点个数为为n n2 2，则则有：有：n n0 0=n=n2 2+1 +1。证证明：明：设设一棵非空二叉一棵非空二叉树树中有中有n n个个结结点，度点，度为为1 1的的结结点个数点个数为为n n1 1，因，因为为二叉二叉树树中所有中所有结结点的度均不大于点的度均不大于2 2，所以，所以 n=n

11、n=n0 0+n+n1 1+n+n2 2 (1)(1)在二叉在二叉树树中，除根中，除根结结点外，其余每个点外，其余每个结结点都有一个分支点都有一个分支进进入，入，假假设设B B为为分支分支总总数，数，则则有有B=n 1 (2)B=n 1 (2)又由于二叉又由于二叉树树中的分支都是由度中的分支都是由度为为1 1和和2 2的的结结点点发发出，所以有出，所以有B=nB=n1 1+2n+2n2 2 (3)(3)综综合合(1)(1)、(2)(2)、(3)(3)式可得式可得 n n0 0=n=n2 2+1+1。n n性性性性质质质质4 4 具有具有n n个个结结点的完全二叉点的完全二叉树树的深度的深度k

12、k为为 。证证明：根据性明：根据性质质2 2和完全二叉和完全二叉树树的定的定义义可知可知2 2k k-1 -1 n 2 n 2k+1k+1 1 1即：即：2 2k k n n 2 2k+1k+1 对对不等式取不等式取对对数有：数有：k k k+1 k+1由于由于k k为为整数，所以有整数，所以有 k=k=n n性性性性质质质质5 5 对对于于具具有有n n个个结结点点的的完完全全二二叉叉树树，如如果果按按照照从从上上（根根结结点点）到到下下（叶叶结结点点）和和从从左左到到右右的的顺顺序序对对二二叉叉树树中中的的所所有有结结点从点从0 0开始到开始到n-1n-1进行编号，则对于任意的下标为进行编

13、号，则对于任意的下标为i i的结点，有：的结点，有：n n如如果果i=0i=0，则则它它是是根根结结点点，它它没没有有父父结结点点：如如果果i i0 0，则则它它的父结点的下标为的父结点的下标为(i-1)/2(i-1)/2；n n如如果果2i 2i1n1n1 1，则则下下标标为为i i的的结结点点的的左左子子结结点点的的下下标标为为2i 2i1 1；否则，下标为；否则，下标为i i的结点没有左子结点：的结点没有左子结点：n n如如果果2i+2n2i+2n1 1，则则下下标标为为i i的的结结点点的的右右子子结结点点的的下下标标为为2i+22i+2；否则，下标为；否则，下标为i i的结点没有右子

14、结点。的结点没有右子结点。n n性质性质性质性质6 6 在满二叉树中，叶结点的个数比分支结点个数多在满二叉树中，叶结点的个数比分支结点个数多1 1。n n性性性性质质质质7 7 扩充二叉树中，外部结点的个数比内部结点的个数多扩充二叉树中，外部结点的个数比内部结点的个数多1 1。n n性性性性质质质质8 8 对对任任意意扩扩充充二二叉叉树树，外外部部路路径径长长度度E E和和内内部部路路径径长长度度I I之之间满足以下关系：间满足以下关系：E=I+2nE=I+2n，其中，其中n n是内部结点个数。是内部结点个数。5.1.3 二叉树的抽象数据类型ADT BinTree isoperations B

15、inTree createEmptyBinTree(void)BinTree createEmptyBinTree(void)创建一棵空的二叉树。创建一棵空的二叉树。BinTree consBinTree(BinTreeNode root,BinTree left,BinTree right)BinTree consBinTree(BinTreeNode root,BinTree left,BinTree right)返回一棵二叉树，其根结点是返回一棵二叉树，其根结点是rootroot，左右二叉树分别为，左右二叉树分别为leftleft和和rightright。int isNull(BinTr

16、ee t)int isNull(BinTree t)判断二叉树判断二叉树t t是否为空。是否为空。BinTreeNode root(BinTree t)BinTreeNode root(BinTree t)返回二叉树返回二叉树t t的根结点。若为空二叉树，则返回一特殊值。的根结点。若为空二叉树，则返回一特殊值。BinTreeNode parent(BinTree t,BinTreeNode p)BinTreeNode parent(BinTree t,BinTreeNode p)返回结点返回结点p p的父结点。当指定的结点为根时，返回一个特殊值。的父结点。当指定的结点为根时，返回一个特殊值。B

17、inTree leftChild(BinTree t,BinTreeNode p)BinTree leftChild(BinTree t,BinTreeNode p)返回返回p p结点的左子树，当指定结点没有左子树时，返回一个特结点的左子树，当指定结点没有左子树时，返回一个特殊值。殊值。BinTree rightChild(BinTree t ,BinTreeNode p)BinTree rightChild(BinTree t ,BinTreeNode p)返回返回p p结点的右子树，当指定结点没有右子树时，返回一个特结点的右子树，当指定结点没有右子树时，返回一个特殊值。殊值。end ADT

18、 BinTree 此外作为抽象数据类型，二叉树还应该有插入、删除和检索节点等运算，由于于本章关系不大，故省略。由于二叉树的概念是递归定义的，二叉树中的每个结点也可标识以这个结点为根的二叉树，所以二叉树类型和二叉树中结点二叉树类型和二叉树中结点类型在具体实现时常常看成是同一种类型。类型在具体实现时常常看成是同一种类型。5.2 二叉树的周游 什么是周游n n二叉树的周游（二叉树的遍历）二叉树的周游（二叉树的遍历）是指按某种方式访问二叉树中的所有结点，使每个结点被访问一次且只被访问一次。n n深度优先周游（深度优先遍历）n n广度优先周游（广度优先遍历）5.2.2 周游的分类周游的分类n n深度优先

19、周游 若以符号D、L、R分别表示根结点、左子树、右子树，则二叉树的周游共有六种方式：DLR，LDR，LRD，DRL，RDL和RLD。如果限定先左后右，则只能采用前三种周游方式，即DLR，LRD和LDR，它们分别被称为先根次序（简称先序或前序）周游、后根次序（简称后序）周游和中根次序（简称中序）周游（也叫对称序次序周游）。n n先根次序：先根次序：先根次序：先根次序：若二叉树不空，则先访问根；然后按先根次序若二叉树不空，则先访问根；然后按先根次序周游左子树；最后按先根次序周游右子树。周游左子树；最后按先根次序周游右子树。n n如图所示二叉树，结点序列为：如图所示二叉树，结点序列为：A A，B B

20、，DD，C C，E E，GG，F F，HH，I I n n将按先根次序周游二叉树得到的线性表称为该二叉树的先根序列。将按先根次序周游二叉树得到的线性表称为该二叉树的先根序列。n n后根次序：后根次序：后根次序：后根次序：若二叉树不空，则先按后根次序周游左子树；若二叉树不空，则先按后根次序周游左子树；然后按后根次序周游右子树；最后访问根。然后按后根次序周游右子树；最后访问根。n n如图所示二叉树，结点序列为：如图所示二叉树，结点序列为：DD，B B，GG，E E，HH，I I，F F，C C，A A n n将按后根次序周游二叉树得到的线性表称为该二叉树的后根序列。将按后根次序周游二叉树得到的线性

21、表称为该二叉树的后根序列。n n中中中中根根根根次次次次序序序序：若若二二叉叉树树不不空空，则则先先按按中中根根次次序序周周游游左左子子树树；然然后后访访问问根根；最最后按中根次序周游右子树。后按中根次序周游右子树。n n如图所示二叉树，结点序列为：如图所示二叉树，结点序列为：DD，B B，A A，E E，GG，C C，HH，F F，I In n将按中根次序周游二叉树得到的线性表称将按中根次序周游二叉树得到的线性表称为该二叉树的中根序列。为该二叉树的中根序列。n n对于给定的二叉树，可以唯一确定它的先根序列、对于给定的二叉树，可以唯一确定它的先根序列、后根序列和中根序列。但是反过来，给定一个二

22、后根序列和中根序列。但是反过来，给定一个二叉树的任意一种周游的序列，无法唯一确定这个叉树的任意一种周游的序列，无法唯一确定这个二叉树。二叉树。n n一般而言，如果已知一个二叉树的中根序列，又一般而言，如果已知一个二叉树的中根序列，又知道另外一种周游序列（无论是先根序列还是后知道另外一种周游序列（无论是先根序列还是后根序列），就可以唯一确定这个二叉树。根序列），就可以唯一确定这个二叉树。n n广度优先周游n n若二叉树的高度为若二叉树的高度为h h，则从，则从0 0到到h h逐层如下处理：从左到逐层如下处理：从左到右逐个访问存在的结点。右逐个访问存在的结点。n n前图的二叉树，广度优先周游所得到

23、的结点序列为：前图的二叉树，广度优先周游所得到的结点序列为：A A，B B，C C，DD，E E，F F，GG，HH，I In n广度优先周游一棵二叉树所得到的结点序列，叫作这广度优先周游一棵二叉树所得到的结点序列，叫作这棵二叉树的棵二叉树的层次序列层次序列层次序列层次序列。5.2.3 一个例子一个例子n n对于二叉树不同的周游策略，所得到的不同线性序列，常对于二叉树不同的周游策略，所得到的不同线性序列，常常具有不同的实际意义。常具有不同的实际意义。n n如如图图是是算算术术表表达达式式（a-ba-b）（c+dc+d）的的一一种种语语法法结结构构图图。由由于于二二叉叉树树本本身身的的层层次次已

24、已经经可可以以定定义义计计算算的的次次序序，所所以以原原表达式中的括号就不需要了。表达式中的括号就不需要了。n n先根序列（前缀表达式）：先根序列（前缀表达式）：a b a b c d c d n n后根序列（后缀表达式）：后根序列（后缀表达式）：a b a b c d c d n n中根序列（中缀表达式）中根序列（中缀表达式）：a a b c b c d dacbdn n中缀表达式中计算的次序与运算符的优先级中缀表达式中计算的次序与运算符的优先级可能产生冲突，所以需要把每个子树的中根可能产生冲突，所以需要把每个子树的中根序列用括号括起来。但前缀表达式、后缀表序列用括号括起来。但前缀表达式、后

25、缀表达式不需要。如前所述，中缀可转换为后缀。达式不需要。如前所述，中缀可转换为后缀。n n广度优先周游的层次序列没有什么实际意义。广度优先周游的层次序列没有什么实际意义。5.2.4 5.2.4 周游的抽象算法周游的抽象算法n n利用二叉树抽象数据类型中的定义，可以方便地写出二叉树的周游算法。n n这里给出的算法，都是建立在上节关于抽象数据类型基本运算的基础上。它们不依赖于二叉树的具体存储结构，所以称为抽象算法。深度优先递归算法深度优先递归算法三种深度优先周游的递归算法：先根次序周游：void preOrder(BinTree t)中根次序周游：void inOrder(BinTree t)后根

26、次序周游：void postOrder(BinTree t)注意是抽象算法，需要根据二叉树的实现方式进行修改。深度优先非递归算法深度优先非递归算法n n利用栈的帮助，可以写出各种深度优先周游的非递归算法。由于本节给出的算法，基本都不涉及具体的存储结构，所以对于栈或者队列的使用，算法中也不依赖于具体的表示方式。n n先根次序周游非递归n n中根次序周游非递归n n后根次序周游非递归先根次序周游非递归先根次序周游非递归n n采采用用非非递递归归算算法法实实现现先先根根次次序序周周游游二二叉叉树树的的主主要要思思路路是是：首首先先把把根根结结点点压压入入栈栈中中；然然后后从从栈栈顶顶中中取取出出元元

27、素素（包包括括退退栈栈），只只要要取取出出元元素素非非空空，就就访访问问该该结结点点，然然后后顺顺序序将将其其右右子子结结点点和和左左子子结结点点进进栈栈，重重复复执执行行上上述述过过程程，直直到到当当从从栈栈顶顶中中取取出出的的元元素素（包包括括退退栈栈）为为空空，并并且且栈栈也也为为空空时时，周周游结束。游结束。n n程程序序实实现现：void void nPreOrder(BinTree nPreOrder(BinTree t)t)。注注意意是是抽抽象象算法，需要根据二叉树的实现方式进行修改。算法，需要根据二叉树的实现方式进行修改。n n算算法法中中每每个个二二叉叉树树恰恰好好进进栈栈、

28、出出栈栈各各一一次次，所所以以它它的的时时间间代代价价为为O(n)O(n)，其其中中n n为为二二叉叉树树中中子子二二叉叉树树（也是结点）的个数。（也是结点）的个数。n n采采用用非非递递归归算算法法实实现现中中根根次次序序周周游游二二叉叉树树的的主主要要思思路路是是：若若二二叉叉树树不不为为空空时时，则则沿沿其其左左子子树树前前进进，在在前前进进过过程程中中，把把所所经经过过的的二二叉叉树树逐逐个个压压入入栈栈中中，当当左左子子树树为为空空时时，弹弹出出栈栈顶顶元元素素，并并访访问问该该二二叉叉树树的的根根，如如果果它它有有右右子子树树，再再进进入入当当前前二二叉叉树树的的右右子子树树，从从

29、头头执执行行上上述述过过程程；如如果果它它没没有有右右子子树树，则则弹弹出出栈栈顶顶元元素素，从从前前面面继继续续执执行行。直直到到当当前前二二叉叉树树为为空空并并且且栈栈也也为为空空时时，周游结束。周游结束。n n程程序序实实现现：void void nInOrder(BinTree nInOrder(BinTree t)t)。注注意意是是抽抽象算法，需要根据二叉树的实现方式进行修改。象算法，需要根据二叉树的实现方式进行修改。n n算法中每个二叉树恰好进栈、出栈各一次，所以算法中每个二叉树恰好进栈、出栈各一次，所以它的时间代价为它的时间代价为O(n)O(n)。中根次序周游非递归中根次序周游非

30、递归n n采采用用非非递递归归算算法法实实现现中中根根次次序序周周游游二二叉叉树树的的主主要要思思路路与与中中根根周周游游有有些些类类似似：若若二二叉叉树树不不为为空空时时，则则沿沿其其左左子子树树前前进进，在在前前进进过过程程中中，把把所所经经过过的的二二叉叉树树逐逐个个压压入入栈栈中中，当当左左子子树树为为空空时时，将将右右子子树树重重复复上上述述过过程程，直直到到左左、右右子子树树都都为为空空时时弹弹出出栈栈顶顶元元素素，并并访访问问该该二二叉叉树树的的根根。如如果果该该二二叉叉树树是是左左子子树树，进进入入作作为为其其兄兄弟弟的的右右子子树树，从从头头执执行行上上述述过过程程；如如果果

31、该该二二叉叉树树是是右右子子树树，则则弹弹出出栈栈顶顶元元素素，从从前前面面继继续续执执行行。直直到到当当前前二二叉叉树树为为空空并并且栈也为空时，周游结束。且栈也为空时，周游结束。n n程程序序实实现现：void void nPostOrder2(BinTree nPostOrder2(BinTree t)t)。注注意意是是抽抽象算法，需要根据二叉树的实现方式进行修改。象算法，需要根据二叉树的实现方式进行修改。n n算算法法中中每每个个二二叉叉树树恰恰好好进进栈栈、出出栈栈各各一一次次，所所以以它的时间代价为它的时间代价为O(n)O(n)。后根次序周游非递归后根次序周游非递归n n根根据据广

32、广度度优优先先周周游游的的思思想想不不难难想想到到，可可以以利利用用一一个个队队列列实实现现其其算算法法：首首先先把把二二叉叉树树送送入入队队列列；其其后后，每每当当从从队队首首取取出出一一个个二二叉叉树树访访问问之之后后，马马上上把把它它的的子子二二叉叉树树按按从从左左到到右右的的次次序序送送入入队队列列尾尾端端；重复此过程直到队列为空。重复此过程直到队列为空。n n程程序序实实现现：void void levelOrder(BinTree levelOrder(BinTree t)t)。注注意意是是抽抽象算法，需要根据二叉树的实现方式进行修改。象算法，需要根据二叉树的实现方式进行修改。n

33、n每每个个二二叉叉树树进进队队列列一一次次出出队队列列一一次次，所所以以时时间间代代价价为为O(n)O(n)。主主要要空空间间代代价价是是需需要要队队列列的的附附加加空空间间。若若二二叉叉树树结结点点个个数数为为n n，最最坏坏的的情情况况出出现现在在完完全全二叉树时，需要大约二叉树时，需要大约n/2n/2个队列元素的空间。个队列元素的空间。广度优先周游非递归广度优先周游非递归5.3 二叉树的实现二叉树的实现 n n顺序表示 n n链接表示 n n线索二叉树 5.3.1 顺序表示n n二二叉叉树树的的顺顺序序表表示示，也也是是采采用用一一组组连连续续的的存存储储单单元元来来存存放放二二叉叉树树

34、中中的的结结点点，但但是是，由由于于二二叉叉树树是是非非线线性性结结构构，所所以以结结点点之之间间的的逻逻辑辑关关系系难难以以从从存存储储的的先先后后确确定定。不不过过，由由二二叉叉树树的的性性质质5 5可可知知，对对于于完完全全二二叉叉树树，如如果果按按照照从从上上（根根结结点点）到到下下（叶叶结结点点）和和从从左左到到右右的的顺顺序序，对对二二叉叉树树中中的的所所有有结结点点从从0 0到到n-1n-1编编号号，这这样样存存放放到到一一维维数数组组中中。只只要要通通过过数数组组元元素素的的下下标标关系，就可以确定二叉树中结点之间的逻辑关系。关系，就可以确定二叉树中结点之间的逻辑关系。n n对

35、对于于一一般般的的二二叉叉树树，如如果果仍仍采采用用顺顺序序表表示示，首首先先要要对对它它进进行行扩扩充充，增增加加一一些些并并不不存存在在的的空空结结点点，使使之之成成为为一一棵棵完完全全二二叉叉树树，然然后后再再用用一一维维数数组组顺顺序序存存储储。在在二二叉叉树树中中人人为为增增加加的的空空结结点点，在在数数组组所所对对应应的的元元素素中中，可可以以用用一一个特殊值表示。个特殊值表示。n n采用顺序存储表示的二叉树，可用下列方式定义：采用顺序存储表示的二叉树，可用下列方式定义：struct SeqBinTreestruct SeqBinTree/顺序二叉树类型定义顺序二叉树类型定义 in

36、t MAXNUM /int MAXNUM /完全二叉树中允许结点的最大个数完全二叉树中允许结点的最大个数 int n;/int n;/改造成完全二叉树后，结点的实际个数改造成完全二叉树后，结点的实际个数DataType *nodelist;/DataType *nodelist;/存放结点的数组存放结点的数组;typedef struct SeqBinTree *PSeqBinTree;/typedef struct SeqBinTree *PSeqBinTree;/顺序二叉树类型的指针顺序二叉树类型的指针n nnodelistnodelist数数组组中中的的每每个个元元素素表表示示二二叉叉树

37、树中中的的一一个个结结点点，以以这这个个结结 点点 为为 根根 的的 子子 二二 叉叉 树树 的的 根根 就就 是是 它它 自自 己己，它它 的的 左左 子子 树树 以以nodelist2*i+1nodelist2*i+1为为根根，它它的的右右子子树树以以nodelist2*nodelist2*（i+1i+1）为为根根，它的父结点则是它的父结点则是nodelistnodelist（i-1i-1）/2/2（前提是这些结点存在）。（前提是这些结点存在）。n nn n是是扩扩充充成成完完全全二二叉叉树树以以后后结结点点的的实实际际个个数数。当当二二叉叉树树为为空空二二叉树时，叉树时，n=0n=0。n

38、 nMAXNUMMAXNUM是是完完全全二二叉叉树树中中允允许许结结点点的的最最大大个个数数，它它可可以以作作为为数数组组空空间间的的大大小小参参数数提提供供给给二二叉叉树树的的创创建建函函数数使使用用，也也可可以以在数组溢出时，通过程序扩充空间。在数组溢出时，通过程序扩充空间。运算的实现运算的实现 n n返回下标为p的结点的父结点的下标 int parent_seq(PSeqBinTree t,int p)n n返回下标为p的结点的左子结点的下标 int leftChild_seq(PSeqBinTree t,int p)n n返回下标为p的结点的右子结点的下标 int rightChild

39、_seq(PSeqBinTree t,int p)n n顺序表示法对完全二叉树比较适合，既可以节省存储空间，又可以利用数组元素的下标确定节点在二叉树中的位置以及节点间的关系。5.3.2 链接表示二二叉叉树树的的链链接接表表示示是是用用一一个个链链表表来来存存储储一一棵棵二二叉叉树树，二二叉叉树树中中的的每每个个结结点点对对应应链链表表中中的的一一个个结结点点。由由于于二二叉叉树树是是非非线线性性结结构构，每每个个结结点点最最多多有有两两个个后后继继，所所以以最最常常用用的的链链接接表表示示方方式式是是左左左左-右右右右指指指指针针针针表表表表示示示示法法法法，这这种种表表示示法法在在每每个个结

40、结点点中中，除除了了存存储储结结点点本本身身的的数数据据外外，再再设设置置两两个个指指针针字字段段：llinkllink和和rlinkrlink，分分别别存存放放结结点点的的左左子子结结点点和和右右子子结结点点的的位位置置，当当结结点点的的某某个个子子树树为为空空时时，则则相相应应的的指指针针为为空指针。空指针。struct BinTreeNode;/二叉树中结点typedef struct BinTreeNode *PBinTreeNode;/结点的指针类型struct BinTreeNode DataType info;/数据域 PBinTreeNode llink;/指向左子结点 PBi

41、nTreeNode rlink;/指向右子结点;由于递归是二叉树的固有特性，二叉树的许多处理都可以用递归算法来描述，因此，为了运算和参数传递的方便，不再对二叉树进行封装，直接将二叉树定义为指向结点的指针类型：typedef struct BinTreeNode *BinTree;在实际应用中，将二叉树作为参数传递时，可能需要传递二叉树根结点指针的地址（避免被调用函数中修改根节点位置）。因此，为了说明方便，可以引入二叉树类型的指针类型：typedef BinTree *PBinTree;运算的实现运算的实现 n n返回结点返回结点p p的左子结点的地址的左子结点的地址 PBinTreeNode

42、PBinTreeNode leftChild_linkleftChild_link(PBinTreeNode p)(PBinTreeNode p)n n返回结点返回结点p p的右子结点的地址的右子结点的地址 PBinTreeNode PBinTreeNode rightChild_linkrightChild_link(PBinTreeNode p)(PBinTreeNode p)n n求求父父节节点点的的操操作作就就比比较较困困难难，只只能能从从根根节节点点出出发发，使使用用前前面面的的周周游游算算法法，跳跳过过算算法法中中的的访访问问函函数数（visitvisit），检检查查当当前前节节点

43、点是是否否是是所所求求节节点点的的父父节节点点。最最坏坏的的时时间间代代价价与与周周游游整个二叉树的代价相同。整个二叉树的代价相同。n n为为了了提提高高求求父父结结点点操操作作的的速速度度，可可以以采采用用的的另另一一种种链链接接表表示示方方式式是是三三叉叉链链表表表表示示，即即给给二二叉叉树树中中的的每每个个结结点点增增加加一一个个指指向向父父结结点点的的指指针针域域。采采用用三三叉叉链链表表表表示示，既既便便于于查查找找子子结结点点，又又便便于于查查找找父父结结点点，但但是是相相对对于于左左右右指指针针表表示示而言，它增加了空间开销。而言，它增加了空间开销。5.3.3 线索二叉树n n周

44、周游游是是二二叉叉树树中中许许多多操操作作的的基基础础，经经常常使使用用。但但一一般般的的周周游游算算法法都都需需要要大大约约O(n)O(n)的的时时间间代代价价。对对于于静静态态的的二二叉叉树树，如如果果多多次次重重复复进进行行周周游游也也是是时时间间的的浪浪费费。如如果果第第一一次次周周游游时时，能能够够把把周周游游的的主主要要信信息息保保存存起起来来，在在重重复复执执行行周周游游时时利用这些信息，就能达到节省资源的效果。利用这些信息，就能达到节省资源的效果。n n线线索索二二叉叉树树是是对对于于左左右右指指针针表表示示法法的的一一种种修修改改。它它利利用用结结点点的的空空的的左左指指针针

45、（llinkllink）存存储储该该结结点点在在某某种种周周游游序序列列中中的的前前驱驱结结点点的的位位置置；利利用用结结点点的的空空的的右右指指针针（rlinkrlink）存存储储该该结结点点在在同同种种周周游游序序列列中中的的后后继继结结点点的的位位置置。这这种种附附加加的的指指向向前前驱驱结结点点和和后后继继结结点点的的指指针针称称作作线线线线索索索索，加加进进了了线线索索的的二二叉叉树树左左右右指指针针表表示示称称作作线线线线索索索索二二二二叉叉叉叉树树树树。把把二二叉叉树树左左右指针表示改造成线索二叉树的过程称为右指针表示改造成线索二叉树的过程称为线索化线索化线索化线索化。n n由由

46、于于周周游游的的方方法法较较多多，根根据据不不同同周周游游方方法法构构造造的的二二叉叉树树也也不同。这里主要讨论中根次序的线索二叉树。不同。这里主要讨论中根次序的线索二叉树。中根次序线索二叉树中根次序线索二叉树为区分左右指针和线索，需要在每个结点里增加两个标志位ltag和rtag，令：ltag=0，则llink是指针，指向结点的左子结点；ltag=1，则llink是线索，指向结点的对称序的前驱结点；rtag=0，则rlink是指针，指向结点的右子结点；rtag=1，则rlink是线索，指向结点的对称序的后继结点。struct ThrTreeNode;/线索二叉树中的结点*/typedef st

47、ruct ThrTreeNode*PThrTreeNode;/指向线索二叉树结点的指针类型struct ThrTreeNode/线索二叉树中结点的定义 DataType info;PThrTreeNode llink,rlink;int ltag,rtag;typedef struct ThrTreeNode*ThrTree;/线索二叉树类型的定义typedef ThrTree*PThrTree;/线索二叉树类型的指针类型按中根次序按中根次序线线索化二叉索化二叉树树n n在在未未线线索索化化之之前前，所所有有结结点点的的llinkllink和和rlinkrlink都都是是指指向向子子结结点点指

48、指针针，因因此此所所有有ltagltag和和rtagrtag的的初初始始状状态态都都为为0 0。给给出出一一棵棵二二叉叉树树，要要将将它它按按中中根根次次序序线线索索化化，其其做做法法就就是是按按中中根根次次序序周周游游此此二二叉叉树树，在在周周游的过程中用线索代替空指针。游的过程中用线索代替空指针。void thread(ThrTree t)void thread(ThrTree t)n n用用线线索索树树的的最最大大优优点点是是：由由于于有有了了线线索索的的存存在在，在在某某些些情情况况下下可可以以很很方方便便地地找找到到指指定定结结点点在在某某种种周周游游序序列列中中的的前前驱驱和和后后

49、继继，而而不不必必再再对对二二叉叉树树重重新新周周游游。另另外外，在在线线索索树树上上进进行行某某种种次次序序周周游游要要比在一般二叉比在一般二叉树树上上进进行行这这种周游容易得多。种周游容易得多。按中根次序周游中根次序按中根次序周游中根次序线索线索树树n n要要按按中中根根次次序序周周游游中中根根次次序序线线索索二二叉叉树树，算算法法十十分分简简洁洁。只只要要首首先先找找到到中中根根序序列列中中的的第第一一个个结结点点，然然后后依依次次找找到到结结点点的的后后继继结结点点，直直至至其其后后继继结结点点为为空空即可。即可。n n第第一一个个结结点点也也很很容容易易找找，只只要要从从根根结结点点

50、出出发发沿沿着着左左指指针针不不断断往往下下走走，直直至至左左指指针针为为空空，到到达达“最最左左下下”的结点，这就是中根次序第一个结点。的结点，这就是中根次序第一个结点。n n找找任任意意结结点点的的中中根根次次序序后后继继时时，也也非非常常容容易易做做：一一个个结结点点的的右右指指针针字字段段如如果果是是线线索索，则则根根据据定定义义，它它就就指指向向该该结结点点在在中中根根次次序序下下的的后后继继；如如果果不不是是线线索索，则则它它指指向向该该结结点点右右子子树树的的根根，而而该该结结点点在在中中根根次次序序下的后继应是此右子树的最左下结点。下的后继应是此右子树的最左下结点。void n