数据结构中的树课件.pptx

1、 第六章第六章 树和二叉树树和二叉树（Tree&Binary tree Tree&Binary tree）第六章第六章 树和二叉树树和二叉树 6.1 树的定义和基本术语树的定义和基本术语 6.1.2 二叉树二叉树 6.2.1 二叉树的定义和基本术语二叉树的定义和基本术语 6.2.2 二叉树的几个基本性质二叉树的几个基本性质 6.2.3 二叉树的存储结构二叉树的存储结构 6.2 遍历二叉树和线索二叉遍历二叉树和线索二叉树树 6.2.1 问题的提出问题的提出 6.2.2 遍历算法描述遍历算法描述 6.2.3 二叉树遍历应用举例二叉树遍历应用举例 6.2.4 线索二叉树线索二叉树n 6.3 6.3

2、树和森林树和森林n 6.3.1 6.3.1 树和森林的定义树和森林的定义n 6.3.2 6.3.2 树和森林的存储结构树和森林的存储结构n 6.3.3 6.3.3 树、森林与二叉树的转换树、森林与二叉树的转换n 6.3.4 6.3.4 树和森林的遍历树和森林的遍历n 6.4 6.4 树的应用树的应用n 6.4.1 6.4.1 堆排序的实现堆排序的实现n 6.4.2 6.4.2 二叉排序树二叉排序树n 6.4.3 6.4.3 赫夫曼树及其应用赫夫曼树及其应用6.1 二叉树二叉树6.1.1 树的定义和基本术语树的定义和基本术语6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语6.1.3 二叉

3、树的几个基本性质二叉树的几个基本性质6.1.4 二叉树的存储结构二叉树的存储结构第第6章章 树和二叉树树和二叉树 树型结构是一类重要的非线性数据结构，其中树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。直观角度看，树是以以树和二叉树最为常用。直观角度看，树是以分支关系分支关系定义的定义的层次结构层次结构。树在计算机领域中。树在计算机领域中得到广泛应用，如文件管理中的得到广泛应用，如文件管理中的目录结构目录结构、数、数据库系统中的据库系统中的信息组织形式信息组织形式等。树结构在客观等。树结构在客观世界中也广泛存在，如人类社会的族谱和各种世界中也广泛存在，如人类社会的族谱和各种社会组

4、织机构都可用树来形象表示。本章重点社会组织机构都可用树来形象表示。本章重点讨论二叉树的存储结构及各种操作，并研究树讨论二叉树的存储结构及各种操作，并研究树和森林与二叉树的转换关系。和森林与二叉树的转换关系。第第6章章 树和二叉树树和二叉树 到目前为止，我们已经介绍了线性数据结构和表数到目前为止，我们已经介绍了线性数据结构和表数据结构。这些数据结构据结构。这些数据结构一般不适合于描述具有层次一般不适合于描述具有层次结构的数据结构的数据。在层次化的数据之间可能有祖先。在层次化的数据之间可能有祖先-后后代、上级代、上级-下属、整体下属、整体-部分以及其他类似的关系。部分以及其他类似的关系。例例1Jo

5、e的后代的后代：上图给出了：上图给出了Joe的后代，并按层的后代，并按层次方式组织，其中次方式组织，其中Joe在最顶层。在最顶层。Joe的孩子（的孩子（Ann，Mary和和John）列在下一层，在父母和孩子间有一）列在下一层，在父母和孩子间有一条边。在层次表示中，非常容易地找到条边。在层次表示中，非常容易地找到Ann的兄弟的兄弟姐妹，姐妹，Joe的后代，的后代，Chris的祖先等。的祖先等。第第6章章 树和二叉树树和二叉树例例2软件工程软件工程：考察另一种层次：考察另一种层次数据数据软件工程中的模块化技术。软件工程中的模块化技术。通过模块化，可以把大的复杂的任通过模块化，可以把大的复杂的任务分

6、成一组小的不太复杂的任务。务分成一组小的不太复杂的任务。模块化的目标是把软件系统分成许模块化的目标是把软件系统分成许多功能不相关的部分或模块以便于多功能不相关的部分或模块以便于进行相对独立的开发。由于解决几进行相对独立的开发。由于解决几个小问题比解决大问题更容易一些，个小问题比解决大问题更容易一些，因此模块化方法可以缩短整个软件因此模块化方法可以缩短整个软件的开发时间。另外，不同的程序员的开发时间。另外，不同的程序员可以同时开发不同的模块。如果有可以同时开发不同的模块。如果有必要，每个模块可以再细分，从而必要，每个模块可以再细分，从而得到如图所示的用树形表示的模块得到如图所示的用树形表示的模块

7、层次结构。该树给出了某文字处理层次结构。该树给出了某文字处理器的一种可行的模块分解图。器的一种可行的模块分解图。第第6章章 树和二叉树树和二叉树 例例3：学校的组织结构学校的组织结构学院学院教务科教务科院办院办基础部基础部科学系科学系技术系技术系计算中心计算中心软件系软件系研究所研究所后勤处后勤处应用室应用室人工智能室人工智能室可计算性室可计算性室学生科学生科师资科师资科教学科教学科教材科教材科 何谓树状结构何谓树状结构 树是树是n(n0)个结点的有限集。个结点的有限集。在任意一棵非空树中在任意一棵非空树中：(1)有有且仅有一个特定的称为根的结且仅有一个特定的称为根的结点；点；(2)当当n1时

8、，其余结点可时，其余结点可分为分为m(m 0)个互不相交的有个互不相交的有限集限集T1,T2,Tm，其中每一，其中每一个集合本身又是一棵树，并且个集合本身又是一棵树，并且称为根的子树。称为根的子树。若一棵树中的结点可以有若一棵树中的结点可以有n个子结点，则称这样的树为个子结点，则称这样的树为n元树，例如二叉树中的结点，元树，例如二叉树中的结点，最多只能有两个结点。最多只能有两个结点。AMDCBRQPA为根结点为根结点B、C、D、M为为A的子结点的子结点6.1 树的定义和基本术语树的定义和基本术语 树的相关名称及意义树的相关名称及意义 根结点（根结点（root node）一棵树中没有父结点的结点

9、，称为根结点一棵树中没有父结点的结点，称为根结点 叶（子）结点叶（子）结点leaf node或终端结点或终端结点terminal node一棵树中没有子结点的结点，称为叶（子）结点或终端结点一棵树中没有子结点的结点，称为叶（子）结点或终端结点 分支结点或非终端结点（分支结点或非终端结点（nonterminal node）除了叶（子）结点以外的其他结点，称为分支结点或非终端结点除了叶（子）结点以外的其他结点，称为分支结点或非终端结点 ADCBEFGHI叶子结点叶子结点根结点根结点6.1 树的定义和基本术语树的定义和基本术语非终端结点非终端结点 父结点（父结点（parent）和子结点（）和子结点（

10、child）若结点若结点x有一个以结点有一个以结点y为树根的子树为树根的子树,则则x为为y的父结点（父亲），而的父结点（父亲），而y为为x的子结点（孩子）。的子结点（孩子）。兄弟（兄弟（sibling）同一个父结点之子结点，称为兄弟同一个父结点之子结点，称为兄弟如图如图B、C、D的父结点均为的父结点均为A，故，故B、C、D互为兄弟互为兄弟 结点的度（结点的度（degree）结点的子树个数，称为结点的度。结点的子树个数，称为结点的度。如图，如图，A的度为的度为3，B的度为的度为3，C的度为的度为1，最大的度值为，最大的度值为3，故树为，故树为3元元树。树。层次（层次（level）层次为结点之特性

11、值，将根结点之层次设为层次为结点之特性值，将根结点之层次设为1，其子结点为，其子结点为2，依此类推。，依此类推。如图，层次为如图，层次为1的有结点的有结点A,为为2的有结点的有结点B、C、D，为，为3的有结点的有结点E、F、G、H、I。6.1 树的定义和基本术语树的定义和基本术语ADCBEFG HI深度（深度（depth）或高度（）或高度（height）叶子结点的最大层次数称为树叶子结点的最大层次数称为树的深度的深度。如图，叶子最大层次值为如图，叶子最大层次值为3，故树，故树 T的深度为的深度为3祖先（祖先（ancestor）由某结点由某结点X到根结点之路径上的所有结点，均称为到根结点之路径上

12、的所有结点，均称为X之祖先之祖先树林（树林（forest）n=0个树的集合称为树林个树的集合称为树林 若将一树的根结点移去，所剩这恰是一树林若将一树的根结点移去，所剩这恰是一树林.ADCBEFG HIDCBEFGHI6.1 树的定义和基本术语树的定义和基本术语A6.1 树的定义和基本术语树的定义和基本术语例例1：只有根结点的树：只有根结点的树A例例2：一般的树：一般的树1.此树此树Tree-A 共有共有13个结点个结点,是由三棵子树组成：是由三棵子树组成：Tree-B(T1)=B，E，F，K，LTree-C(T2)=C，GTree-D(T3)=D，H，I，J，MB、C、D为三棵子树的根，且互不

13、相交为三棵子树的根，且互不相交2.T1又分为两个互不相交的又分为两个互不相交的Tree-E(T11)=E，K，L 和和Tree-F(T12)=FT2又分为一个树又分为一个树Tree-G(T21)=GT3又分为三棵互不相交的又分为三棵互不相交的Tree-H(T31)=H，MTree-I(T32)=I 和和Tree-J(T33)=J3.T11又分为又分为:Tree-K(T111)和和Tree-L(T112)T31又分又分为为:Tree-M(T311)ADCBKGLEFH IJM每棵子树的结构均符合上述定义每棵子树的结构均符合上述定义6.1 树的定义和基本术语树的定义和基本术语 例例3：不是一棵树：

14、不是一棵树 因为因为:子树子树Tree-H=H，M子树子树Tree-I=I，M出现了交叉，违出现了交叉，违反树的定义。反树的定义。树的其它表示形式树的其它表示形式Tree-A的结构：的结构：结点结点A包括包括B,C,D结点结点B包括包括E,F结点结点C包括包括G结点结点D包括包括H,I,J结点结点E包括包括K,L结点结点H包括包括MADCBKGLEFH IJMADCBKGLEFHIJM树的表示形式树的表示形式A:B,C,DB:E,FC:GD:H,I,JE:K,LH:MK KE EB BA AL LF FC CG GD DM MH HI IJ J2 2 凹入表示法凹入表示法1 1 集合表示法集合

15、表示法6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语 二叉树（二叉树（binary tree）是）是n(n0)个数据元素的有限集，个数据元素的有限集，它或为空集它或为空集(n0)，或者含有唯一的称为根的元素，且其，或者含有唯一的称为根的元素，且其余元素分成余元素分成两个两个互不相交的子集，每个子集自身也是一棵互不相交的子集，每个子集自身也是一棵二叉树二叉树，分别称为根的，分别称为根的左子树左子树和和右子树右子树。集合为空的树简称为空树。集合为空的树简称为空树。树中的元素称为结点。树中的元素称为结点。ADCBEFBDE左子树左子树CF右子树右子树6.1.2 二叉树的定义和基本术语二叉树

16、的定义和基本术语 根以外的任意两个结点不可能同根以外的任意两个结点不可能同时在同一棵子树中出现。时在同一棵子树中出现。二叉树的子树有左右之分，不能二叉树的子树有左右之分，不能任意颠倒。任意颠倒。如图所示如图所示 A为根结点为根结点 D、G、H、J为叶子结点为叶子结点 A是是B的父亲，的父亲，B是是A的左孩子，的左孩子，C是是A的右孩子，的右孩子，A是是E的祖先，的祖先，E是是A的子孙，的子孙，D和和E是兄弟，是兄弟，D和和F是堂兄弟是堂兄弟 A、B、的度为、的度为2，C、F、I的度为的度为1，D、G、H、J的的度为度为0 二叉树的深度为二叉树的深度为5ADCBEGFIJH二叉树的五种形态二叉树

17、的五种形态练习：如果只有三个结点，形态如何？练习：如果只有三个结点，形态如何？左、右子树左、右子树具全的二叉树具全的二叉树左子树为空左子树为空的二叉树的二叉树空的二叉树空的二叉树仅有根结点仅有根结点的二叉树的二叉树右子树为空右子树为空的二叉树的二叉树 满二叉树（满二叉树（full binary tree）若二叉树中所有的分支结点的度数都为若二叉树中所有的分支结点的度数都为2，且叶子，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。结点都在同一层次上，则称这类二叉树为满二叉树。若该树的高度为若该树的高度为h，则此满二叉树的结点为，则此满二叉树的结点为 2h-1A层次：层次：1 CB层次：层次

18、：2 DEFG层次：层次：3 6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语 完全二叉树（完全二叉树（complete binary tree）假如任意一棵包含假如任意一棵包含n个结点的二叉树中每个结点都可以和同深度个结点的二叉树中每个结点都可以和同深度的满二叉树中编号为的满二叉树中编号为1至至n的结点一一对应，则称这类二叉树为完的结点一一对应，则称这类二叉树为完全二叉树。全二叉树。一棵树扣除掉最大阶层那层后为一满二叉树，且阶层最大那层的一棵树扣除掉最大阶层那层后为一满二叉树，且阶层最大那层的结点均向左靠齐，则该二叉树称为完全二叉树。结点均向左靠齐，则该二叉树称为完全二叉树。满二叉树

19、满二叉树 level最大层的最大层的结点均向左靠齐结点均向左靠齐 完全二叉树完全二叉树 ADCBEF6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语 二叉树的应用二叉树的应用表示家族的血缘关系表示家族的血缘关系外曾祖母外曾祖母曾祖父曾祖父曾祖母曾祖母曾祖父曾祖父曾祖母曾祖母外曾祖母外曾祖母外曾祖父外曾祖父外曾祖父外曾祖父祖父祖父外祖父外祖父祖母祖母外祖母外祖母父亲父亲母亲母亲男方男方外曾祖母外曾祖母曾祖父曾祖父曾祖母曾祖母曾祖父曾祖父曾祖母曾祖母外曾祖母外曾祖母外曾祖父外曾祖父外曾祖父外曾祖父祖父祖父外祖父外祖父祖母祖母外祖母外祖

20、母父亲父亲母亲母亲女方女方家庭家庭1家庭家庭2不能有相同结点，不能有相同结点，否则为否则为近亲近亲结婚！结婚！6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语二叉树的基本操作定义二叉树的基本操作定义(1)initBiTree(&T)n操作结果：构造一棵空的二叉树操作结果：构造一棵空的二叉树T。DestroyBiTree(&T)n初始条件：二叉树初始条件：二叉树T存在。存在。n操作结果：销毁二叉树操作结果：销毁二叉树TCreateBiTree(&T,definition)n初始条件：初始条件：definition给出二叉树给出二叉树T的定义。的定义。n操作结果：按操作结果：按defini

21、tion给出的定义构造二叉树给出的定义构造二叉树T。BiTreeEmpty(T)n初始条件：二叉树初始条件：二叉树T存在。存在。n操作结果：操作结果：若若T为空二叉树，则返回为空二叉树，则返回TRUE，否则返回否则返回FALSE.6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语 二叉树的基本操作定义二叉树的基本操作定义(2)BiTreeDepth(T)n初始条件：二叉树初始条件：二叉树T存在。存在。n操作结果：返回操作结果：返回T的深度。的深度。Parent(T,e)n初始条件：二叉树初始条件：二叉树T存在存在,e是是T中某个结点。中某个结点。n操作结果：若操作结果：若e是是T的非根结

22、点，则返回它的双亲，的非根结点，则返回它的双亲，否则返回否则返回“空空”。LeftChiild(T,e)n初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。n操作结果：返回操作结果：返回e的左孩子。若的左孩子。若e无左孩子，则返回无左孩子，则返回“空空”。RightChild(T,e)n初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。n操作结果：返回操作结果：返回e的右孩子。若的右孩子。若e无右孩子，则返回无右孩子，则返回“空空”。6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语 二叉树的基本操作定义二叉树的基本操作定义(3)L

23、eftSibling(T,e)n初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。n操作结果：返回操作结果：返回e的左兄弟，若的左兄弟，若e是其双亲的左孩子或是其双亲的左孩子或无左兄弟，则返回无左兄弟，则返回“空空”。RighrtSibling(T,e)n初始条件：二叉树初始条件：二叉树T存在，存在，e是是T中某个结点。中某个结点。n操作结果：返回操作结果：返回e的右兄弟，若的右兄弟，若e是其双亲的左孩子或是其双亲的左孩子或无左兄弟，则返回无左兄弟，则返回“空空”。InsertChild(T,p,LR,C)n初始条件：二叉树初始条件：二叉树T存在存在,p指向指向T中

24、某个结点，左或右中某个结点，左或右的标志的标志LR为为0或或1，非空二叉树，非空二叉树c与与T不相交且右子树为空。不相交且右子树为空。n操作结果：根据操作结果：根据LR为为0或或1，插入，插入c为为T中中p所指结点的所指结点的左子树或右子树，左子树或右子树，p所指结点原有的左子树或右子树均成所指结点原有的左子树或右子树均成为为c的右子树。的右子树。6.1.2 二叉树的定义和基本术语二叉树的定义和基本术语二叉树的基本操作定义二叉树的基本操作定义(4)DeleteChild(T,p,LR)n初始条件：二叉树初始条件：二叉树T存在，存在，p指向指向T中某个结点，中某个结点，LR为为0或或1。n操作结

25、果：根据操作结果：根据LR为为0或或1，删除，删除T中中p所指结点的左或右所指结点的左或右子树。子树。Traverse（T）n初始条件：二叉树初始条件：二叉树T存在存在n操作结果：依某条搜索路径遍历操作结果：依某条搜索路径遍历T，对每个结点进行一次，对每个结点进行一次且仅一次访问（例如输出结点元素值）且仅一次访问（例如输出结点元素值）6.1.3 二叉树的几个基本性质二叉树的几个基本性质 性质性质1 在二叉树的第在二叉树的第i层上层上至多至多有有2i-1个结点（个结点（i 1）利用数学归纳法证明：利用数学归纳法证明：i=1时，只有一个根结点，显然时，只有一个根结点，显然2i-1=20=1是对的。

26、是对的。现在假定对所有现在假定对所有j（1jn0=n2+16.1.3 二叉树的几个基本性质二叉树的几个基本性质性质性质4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为证明：证明：n 假设深度为假设深度为k，则根据性质，则根据性质2和完全二叉树的定义有和完全二叉树的定义有 2k-1-1 n 2k-1，或，或2k-1 n 2k n 取对数便有取对数便有k-1 log2n 1，则其双亲结点，则其双亲结点parent(i)的编号是的编号是（2）如果）如果2in，则编号为，则编号为i的结点无左孩子（编号为的结点无左孩子（编号为i的结点为叶子结点）；否则其左孩子结点的结点为叶子结点）；否

27、则其左孩子结点lChild(i)的编的编号是号是2i（3）如果）如果2i+1n，则编号为，则编号为i的结点无右左孩子；否的结点无右左孩子；否则其右孩子结点则其右孩子结点rChild(i)的编号是的编号是2i+1 1log2 n 2/i 1log2 n6.1.3 二叉树的几个基本性质二叉树的几个基本性质ACBDFEGIHKJL1 12 23 34 45 56 67 78 89 9101011111212对于对于E E，2 2*5=1012,5=1012,其左孩子为其左孩子为10;210;2*5+1=11125+1=11126+1=1312，没有右孩子，没有右孩子对于对于J J，2 2*10=20

28、1210=2012，为叶子结点，为叶子结点 1.1.顺序存储结构顺序存储结构 用一组地址连续的存储单元存储二叉树中的数据元素用一组地址连续的存储单元存储二叉树中的数据元素 将完全二叉树编号为的结点存储在一维数组下标为的单元中将完全二叉树编号为的结点存储在一维数组下标为的单元中 一般二叉树可能浪费大量存储空间一般二叉树可能浪费大量存储空间ABC DEFG0123456ABCD0123456789ADCBEFG(0)(1)(2)(3)(4)(5)(6)(3)(7)(8)(2)(5)(6)(0)(1)(4)(9)ABCD6.1.4 二叉树的存储结构二叉树的存储结构6.1.4 二叉树的存储结构二叉树的

29、存储结构 1.1.顺序顺序存储结构存储结构 完全二叉树的顺序存储结构定义：完全二叉树的顺序存储结构定义：const MAXSIZE=100；/结点数最大值结点数最大值typedef struct TElemType*data;/存储空间基址存储空间基址 int nodenum;/树中结点数树中结点数SqBiTree;/完全二叉树的顺序存储结构完全二叉树的顺序存储结构 1.顺序存储结构（从下标为顺序存储结构（从下标为1的单元开始存储）的单元开始存储）假设父结点编号为假设父结点编号为n，可以得到：，可以得到：（1）左子结点为父结点乘以）左子结点为父结点乘以2：2*n （2）右子结点为父结点乘以）右

30、子结点为父结点乘以2加加1：2*n+1ABC DEFG01234567ABCD012345678109ADCBEFG(1)(2)(3)(4)(5)(6)(7)(4)(8)(9)(3)(6)(7)(1)(2)(5)(10)ABCD6.1.4 二叉树的存储结构二叉树的存储结构6.1.4 二叉树的存储结构二叉树的存储结构 2.链式存储表示链式存储表示二叉树结点的逻辑结构二叉树结点的逻辑结构 如左图如左图datadatalchildlchildrchildrchildlchildlchilddatadatarchildrchildn 二叉链表二叉链表 typedef struct BiTNode TE

31、lemType data;struct BiTNode*lchild,*rchild;/左、右孩子指针左、右孩子指针 BiTNode,*BiTree;/完全二叉树的二叉链表结构完全二叉树的二叉链表结构6.1.4 二叉树的存储结构二叉树的存储结构ABCDEGHFIJ二叉树的二叉链表二叉树的二叉链表 A A B B D D E E F F C C I I G G H H J J6.1.4 二叉树的存储结构二叉树的存储结构 2.链式存储链式存储表示表示 三叉链表三叉链表 typedef struct BiTNode TElemType data;/结点数据结点数据 struct BiTNode*pa

32、rent,*lchild,*rchild;BiTNode,*BiTree;/完全二叉树的三叉链表结完全二叉树的三叉链表结构构lchildlchildparentparentdatadatarchildrchilddatadataparentparentlchildlchildrchildrchild6.1.4 二叉树的存储结构二叉树的存储结构ABCDEGHFIJ二叉树的三叉链表二叉树的三叉链表 A A B B C C D D E E G G H H F F I I J J 6.1.4 二叉树的存储结构二叉树的存储结构3.结构体数组存储结构体数组存储可用结构体数组来存储二叉树，此结构体包含可用结

33、构体数组来存储二叉树，此结构体包含3个字段，其中个字段，其中一个字段是用来存放结点的数据内容，而另两个字段则是分别一个字段是用来存放结点的数据内容，而另两个字段则是分别存放左子树和右子树在数组中的索引值。存放左子树和右子树在数组中的索引值。二叉树的结构体数组声明如下：二叉树的结构体数组声明如下：typedef struct int left;TElemType data;int right;treenode;/完全二叉树的二叉链表结构完全二叉树的二叉链表结构treenode b_treeSIZE;在结构数组中在结构数组中b_tree，会将根结点置于数组结构中索引值为，会将根结点置于数组结构中索

34、引值为0之处，将结点值存在之处，将结点值存在data字段，而字段，而left及及right字段则分别存储字段则分别存储左右子树在数组结构中的索引值，若子树不存在则存值左右子树在数组结构中的索引值，若子树不存在则存值-1。6.1.4 二叉树的存储结构二叉树的存储结构3.结构体数组存储结构体数组存储例如，有一棵二叉树其树状结构与结构数组表示法如下：例如，有一棵二叉树其树状结构与结构数组表示法如下：图中根结点为图中根结点为A，故，故A在结构数组索引值为之处，其左子结点在结构数组索引值为之处，其左子结点B在索引值在索引值1，右子结点，右子结点B在索引值在索引值2，故结点，故结点A的的left字段和字段

35、和right字段分别为字段分别为1和和2，而结点，而结点C的的right字段值为字段值为-1，表示其没有右子，表示其没有右子结点，而结点结点，而结点D和和E都是叶结点（都是叶结点（leaf node）没有子结点，故）没有子结点，故left 和和right字段均为字段均为-1。索引值索引值leftleftdatadatarightright01A21-1B324C-13-1D-14-1E-1ACBDE(0)(1)(2)(3)(4)6.2 二叉树遍历二叉树遍历6.2.1 问题的提出问题的提出6.2.2 遍历算法描述遍历算法描述6.2.3 二叉树遍历应用举例二叉树遍历应用举例6.2.4 线索二叉树线

36、索二叉树6.2.1 问题的提出问题的提出 遍历二叉树（遍历二叉树（Traversing binary tree）：如何按某条搜索路径）：如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问到且仅被访问一次。巡访树中每个结点，使得每个结点均被访问到且仅被访问一次。访问：存取操作、打印等加工处理。访问：存取操作、打印等加工处理。数组和链表可以从前端到尾端或从尾端到前端依序抽取各个数据数组和链表可以从前端到尾端或从尾端到前端依序抽取各个数据值，而二叉树是一种值，而二叉树是一种特殊的数据结构特殊的数据结构，每个结点其下又各有左、，每个结点其下又各有左、右两个分支，右两个分支，“二叉树的遍历二叉树的

37、遍历”是以固定的顺序，有系统地抽取是以固定的顺序，有系统地抽取二叉树中的各结点，且每个结点均恰好被抽取一次。二叉树中的各结点，且每个结点均恰好被抽取一次。二叉树的遍历是以递归的方式进行，以递归的调用顺序不同，可二叉树的遍历是以递归的方式进行，以递归的调用顺序不同，可分为三种遍历方式：分为三种遍历方式：先序遍历方式先序遍历方式 中序遍历方式中序遍历方式 后序遍历方式后序遍历方式6.2.1 问题的提出问题的提出先序遍历（先序遍历（Preorder traversal）是是先遍历先遍历根根结点，再遍历结点，再遍历左子树左子树，最后，最后遍历遍历右子树右子树，若一棵二叉树如右图，若一棵二叉树如右图，则

38、先序遍历的顺序为：则先序遍历的顺序为：DLR,也就是说也就是说每当遍历一个结点就先处理该结点，每当遍历一个结点就先处理该结点，之后先向左方前进，直到无法前进才之后先向左方前进，直到无法前进才往右方走。往右方走。左图中从根结点左图中从根结点A开始，先往左开始，先往左子树子树B再到再到D，由于，由于D没有左子树，没有左子树，故转向右子树故转向右子树G；再回到；再回到B，因为，因为B没有右子树，所以此时没有右子树，所以此时A的左子树的左子树均遍历完毕，则转向均遍历完毕，则转向A的右子树，的右子树，再往左边继续遍历。再往左边继续遍历。依此类推，其前序遍历为：依此类推，其前序遍历为：ABDGCEHIF。

39、ADCBGEFHIDRL根结点根结点左子树左子树右子树右子树cDcLcRcAcIcHcGcFcEcDcCcB6.2.1 问题的提出问题的提出先序遍历二叉树的步骤如下：先序遍历二叉树的步骤如下：if 二叉树为空二叉树为空 then 遍历结束遍历结束else （1）访问当前结点）访问当前结点 （2）先序访问左子树）先序访问左子树 （3）先序访问右子树）先序访问右子树6.2.1 问题的提出问题的提出中序遍历（中序遍历（Inorder traversal）是先遍是先遍历历左子树左子树，再，再根根结点，最后才遍历结点，最后才遍历右子右子树树，若一棵二叉树如右图，则中序遍历，若一棵二叉树如右图，则中序遍历

40、的顺序为：的顺序为：LDR，也就是说一开始先往，也就是说一开始先往左方前进，直到无法前进才处理结点，左方前进，直到无法前进才处理结点，之后再往右方前进。之后再往右方前进。ADCBGEFHI左图中从根结点左图中从根结点A开始，一直开始，一直往左走到往左走到D无法再前进，则处理无法再前进，则处理D，再往再往D之右方到之右方到G。此时，已遍历。此时，已遍历完完B之左子树，接着处理之左子树，接着处理B，再往，再往B的右方向前进。由于的右方向前进。由于B没有右子没有右子树，故树，故A之左子树遍历完毕，再往之左子树遍历完毕，再往A之右子树前进。之右子树前进。依此类推，其中序遍历为：依此类推，其中序遍历为：

41、DGBAHEICF。DRL根结点根结点左子树左子树右子树右子树cDcLcRcAcIcHcGcFcEcDcCcB6.2.1 问题的提出问题的提出中序遍历二叉树的步骤如下：中序遍历二叉树的步骤如下：if 二叉树为空二叉树为空 then 遍历结束遍历结束else （1）中序访问左子树）中序访问左子树 （2）访问当前结点）访问当前结点 （3）中序访问右子树）中序访问右子树6.2.1 问题的提出问题的提出后序遍历（后序遍历（Postorder traversal）是是先遍历先遍历左子树左子树，再遍历，再遍历右子树右子树，最后，最后才遍历才遍历根根结点，若一棵二叉树如右图，结点，若一棵二叉树如右图，则后序

42、遍历的顺序为：则后序遍历的顺序为：LRD，也就是，也就是说一开始先往左方前进，直到无法前说一开始先往左方前进，直到无法前进才处再往右方前进，最后才处理结进才处再往右方前进，最后才处理结点。点。左图中从根结点左图中从根结点A开始，一直往左开始，一直往左走到走到D无法再前进，则往无法再前进，则往D之右方前之右方前进到进到G，由于，由于G没有左、右子树，故没有左、右子树，故处理结点处理结点G。之后由于。之后由于D之右子树处之右子树处理完毕，故进而处理理完毕，故进而处理D，而，而B之左子之左子树也相应完成。且结点树也相应完成。且结点B没有右子树，没有右子树，故可接着处理故可接着处理B。此时。此时A之左

43、子树已之左子树已遍历完毕，再往遍历完毕，再往A之右子树之右子树C前进。前进。依此类推，其后序遍历为：依此类推，其后序遍历为：GDBHIEFCA。ADCBGEFHIDRL根结点根结点左子树左子树右子树右子树cDcLcRcAcIcHcGcFcEcDcCcB6.2.1 问题的提出问题的提出后序遍历二叉树的步骤如下：后序遍历二叉树的步骤如下：if 二叉树为空二叉树为空 then 遍历结束遍历结束else （1）后序访问左子树）后序访问左子树 （2）后序访问右子树）后序访问右子树 （3）访问当前结点）访问当前结点6.2.1 问题的提出问题的提出二叉树遍历过程示意图二叉树遍历过程示意图 A A B B E

44、 E D D C CABCDEA AC CB BD DC CE EA AA AB BD DE EC CE EB BD D先序：先序：ABDECABDEC中序：中序：DBEACDBEAC后序：后序：DEBCADEBCA遍历练习遍历练习ADCBGFIJEH先序：先序：ABDGEHCFIJABDGEHCFIJ中序：中序：DGBEHACIFJDGBEHACIFJ后序：后序：GDHEBIJFCAGDHEBIJFCA遍历练习遍历练习 已知某二叉树的先序序列为已知某二叉树的先序序列为:abdgcefh，中序序，中序序列为列为:dgbaechf，求其后序序列，求其后序序列先序先序a a b d g c e f

45、 h b d g c e f h中序中序d g b d g b a a e c h f e c h fa a b b d g d g c c e f h e f ha a b b d d g g c c e e f f h hd g d g b b a a e e c c h f h fabced d g g b ab a e e c c h h f f根根右右根根根根左左左左左左右右根根根根根根右右左左dfgh遍历练习遍历练习 已知某二叉树的后序序列为已知某二叉树的后序序列为:gdbehfca:gdbehfca，中序序列，中序序列为为:dgbaechf:dgbaechf，求其先序序列，求其先

46、序序列后序后序g d b e h f c g d b e h f c a a中序中序d g b d g b a a e c h f e c h fg d g d b b e h f e h f c c a ag g d d b b e e h h f f c c a ad g d g b b a a e e c c h f h fabced d g g b ab a e e c c h h f f根根右右根根根根左左左左左左右右根根根根根根右右左左dfgh6.2.2 遍历算法描述遍历算法描述 先序递归算法：先序递归算法：/先序遍历以先序遍历以T为根指针的二叉树为根指针的二叉树 void Pre

47、order(BiTree T，void(*visit)(BiTree)if(T)/T=NULL时，二叉树为空树，不做任何操作时，二叉树为空树，不做任何操作 visit(T);/通过函数指针通过函数指针*visit访问根结点，访问根结点，以便灵活完成相应的操作以便灵活完成相应的操作 Preorder(T-lchild,visit);/先序遍历左子树先序遍历左子树 Preorder(T-rchild,visit);/先序遍历右子树先序遍历右子树 6.2.2 遍历算法描述遍历算法描述 中序递归算法：中序递归算法：/中序遍历以中序遍历以T为根指针的二叉树为根指针的二叉树 void Inorder(Bi

48、Tree T，void(*visit)(BiTree)if(T)/T=NULL时，二叉树为空树，不做任何操作时，二叉树为空树，不做任何操作 Inorder(T-lchild,visit);/中序遍历左子树中序遍历左子树 visit(T);/通过函数指针通过函数指针*visit访问根结点，访问根结点，以便灵活完成相应的操作以便灵活完成相应的操作 Inorder(T-rchild,visit);/中序遍历右子树中序遍历右子树 6.2.2 遍历算法描述遍历算法描述 后序递归算法：后序递归算法：/后序遍历以后序遍历以T为根指针的二叉树为根指针的二叉树 void Postorder(BiTree T，v

49、oid(*visit)(BiTree)if(T)/T=NULL时，二叉树为空树，不做任何操作时，二叉树为空树，不做任何操作 Postorder(T-lchild,visit);/后序遍历左子树后序遍历左子树 Postorder(T-rchild,visit);/后序遍历右子树后序遍历右子树 visit(T);/通过函数指针通过函数指针*visit访问根结点，访问根结点，以便灵活完成相应的操作以便灵活完成相应的操作 6.2.2 遍历算法描述遍历算法描述 堆栈遍历算法：堆栈遍历算法：typedef enum Travel=1,Visit=0 TaskType;/为为Travel时工作状态是遍历，为

50、时工作状态是遍历，为Visit时是访问时是访问typedef struct BiTree ptr;/指向二叉树结点的指针指向二叉树结点的指针 TaskType task;/任务的性质任务的性质SElemType;/栈元素的类型定义栈元素的类型定义6.2.2 遍历算法描述遍历算法描述 先序堆栈算法：先序堆栈算法：void PreOrder_iter(BiTree BT，void(*visit)(BiTree)/利用栈实现中序遍历二叉树，利用栈实现中序遍历二叉树，T为指向二叉树的根结点的头指针为指向二叉树的根结点的头指针 InitStack(S);e.ptr=BT;e.task=Travel;/e