数据结构PPT教学课件-第六章 树和二叉树.ppt

《数据结构PPT教学课件-第六章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构PPT教学课件-第六章 树和二叉树.ppt（125页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6引言：引言：树型结构是一类重要的树型结构是一类重要的非线性非线性结构。树型结构是结点之间有分结构。树型结构是结点之间有分支，且具有层次关系的结构，支，且具有层次关系的结构，非常类似于自然界中的树。非常类似

2、于自然界中的树。树结构在客观世界大量存在。例如家谱、树结构在客观世界大量存在。例如家谱、行政组织机构行政组织机构都可用都可用树形象地表示。树形象地表示。树在计算机领域中也有着广泛的应用：树在计算机领域中也有着广泛的应用：在编译程序中，用树来表示源程序的语法结构；在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在数据库系统中，可用树来组织信息；Windows操作系统中对磁盘文件的管理。操作系统中对磁盘文件的管理。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationSci

3、ence&TechnologyChap6教师教师学生学生其他人员其他人员20072007级级 20082008级级 20092009级级20102010级级南信大南信大数理院数理院计算机院计算机院语院语院叶子叶子根根子树子树计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 第六章第六章 树和二叉树树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.36.3遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4

4、 6.4 树和森林树和森林6.6.5 5 哈夫曼树及应用哈夫曼树及应用计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6树的定义、术语、操作树的定义、术语、操作二叉树定义、性质、操作二叉树定义、性质、操作二叉树的存储结构二叉树的存储结构(重点重点)顺序存储、顺序存储、链接存储链接存储线索二叉树线索二叉树(难点难点)（特殊的链接存储结构）（特殊的链接存储结构）二叉树二叉树运算运算递归递归遍历遍历非递归非递归遍历遍历二叉树遍历二叉树遍历(重点重点)二叉

5、树二叉树其他运算其他运算树的存储结构树的存储结构森林与二叉树的转换森林与二叉树的转换树和森林的遍历树和森林的遍历二叉树二叉树应用应用哈夫曼树哈夫曼树及其应用及其应用(重点、重点、难点难点)内容及重、难点内容及重、难点6.16.26.26.36.36.46.5计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap66.1 6.1 树的定义与术语树的定义与术语一、树的定义一、树的定义 树是由树是由n(n 0)个结点组成的有限集合。如果个结点组成的有限集合。如

6、果n=0，称为，称为空树空树；如果；如果n0，则：，则：有一个特定的有一个特定的元素元素称之为称之为根根(root)的结点，的结点，除根以外的其他结点划分为除根以外的其他结点划分为m(m 0)个互不相交个互不相交的有限集合的有限集合T1,Tm，每个集合又是一棵树，并且称之，每个集合又是一棵树，并且称之为根的为根的子树子树(subTree)。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6A只有根结点的树只有根结点的树ABCDEFGHIJKLM有子

7、树的树有子树的树根根子树子树例：例：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ACGBDEFKLHMIJ1）树中只有根结点没有前趋；）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径。）除根外的其他结点，都存在唯一条从根到该结点的路径。(非空非空)树结构特点：树结构特点：

8、计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素(无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)计算机与软件学院（计算机与软件学院（SchoolofComputerandSo

9、ftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDEFGHIJKLM树形表示树形表示(A(B(E(K,L),F),C(G),D(H(M),I,J)广义表广义表二、树的表示方法二、树的表示方法 I JFKLGMCCDBEA文氏图文氏图凹入表凹入表计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6结点结点(node)结点的度结点的度(degree)结点的子树个数结点的子树个数

10、分支分支(branch)结点结点度不为度不为0的结点的结点根根(root)即根结点即根结点(没有前驱没有前驱)叶叶(leaf)结点结点度为度为0的结点的结点孩子孩子(child)结点结点双亲双亲(parent)结点结点兄弟兄弟(sibling)结点结点具有同一双亲的结点具有同一双亲的结点三、树的基本术语三、树的基本术语ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0分支结点：分支结点：A,B,C,D,E,H叶结点：叶结点：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结

11、点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6祖先祖先(ancestor)结点结点结点的祖先是从根到该结点所结点的祖先是从根到该结点所经分支上的所有结点经分支上的所有结点.子孙子孙(descendant)结点结点以某结点为根的子树中的任一以某结点为根的子树中的任一结点都为该结点的子孙结点都为该结点的子孙.结点的层次结点的层次(level)根结点的层数为根结点的层数

12、为1，其余结点，其余结点的层数为双亲结点的层数加的层数为双亲结点的层数加1树的高度树的高度(depth)树中结点的最大层数树中结点的最大层数树的度树的度(degree)树的基本术语树的基本术语(续续)ABCDEFGHIJKLM结点结点K的祖先：的祖先：A,B,E结点结点B的子孙：的子孙：E,F,K,L树的度：树的度：3树的高度：树的高度：4结点结点A的层次：的层次：1结点结点M的层次：的层次：4计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6n

13、n 有序树有序树子树的次序不能互换子树的次序不能互换n无序树无序树子树的次序可以互换子树的次序可以互换n森林（森林（Forest）m棵互不相交的树的集合棵互不相交的树的集合基本术语（续）：基本术语（续）：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6树的运算分树的运算分3 3大类：大类：第一类：第一类：查找类查找类遍历遍历树中每个结点、求树的状态（如树高度、判树空）树中每个结点、求树的状态（如树高度、判树空）查找查找满足某种特定关系的结点满足某

14、种特定关系的结点,如查找根结点等如查找根结点等第二类，第二类，插入类插入类包括初始化空树、构造树、在树的当前结点上插入一个新结包括初始化空树、构造树、在树的当前结点上插入一个新结点等；点等；第三类，第三类，删除类删除类包括清空树、销毁树、删除树中结点。包括清空树、销毁树、删除树中结点。四、树的基本操作（四、树的基本操作（P118P118）计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6五、树的抽象数据类型定义五、树的抽象数据类型定义ADTTree

15、数据对象数据对象D：由由n个具有相同特性的元素构成的集合个具有相同特性的元素构成的集合数据关系数据关系R：若若D为空集，则称为空树为空集，则称为空树。否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root;(2)当当n1时时,其余结点可分为其余结点可分为m(m0)个互不相交的有限集个互不相交的有限集T1,T2,Tm,其中每一棵子集本身又是一棵符合本定义的树其中每一棵子集本身又是一棵符合本定义的树,称为根称为根root的子树的子树.基本操作基本操作P：Root(T)/求树的根结点求树的根结点Value(T,cur_e)/求当前结点的元素值求当前结点的元素值Pare

16、nt(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子CreateTree(&T,definition)/构造树构造树InitTree(&T)/初始化置空树初始化置空树计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6TreeEmpty(T)/判定树是否为空树判定树是否为空树TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit(

17、)/遍历遍历Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟 ClearTree(&T)/清空树清空树DestroyTree(&T)/销毁树销毁树DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树ADTTree计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInfo

18、rmationScience&TechnologyChap66.2 6.2 二叉树二叉树6.2.1二叉树的定义二叉树的定义 二叉树或为空树，或是由一个根结点加上两棵分别称为二叉树或为空树，或是由一个根结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互不相交的互不相交的二叉树组成。二叉树组成。ABCDEFGHK根结点左子树右子树说明说明（1）二叉树中每个结点最多有两棵子树；二叉树每个）二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于结点度小于等于2；（2）左、右子树不能颠倒）左、右子树不能颠倒有序树；有序树；（3）二叉树是递归结构。）二叉树是递归结构。计算机与软件学院（计算机与软

19、件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6LRLR二叉树的五种基本形态二叉树的五种基本形态计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6问题：u1.只有两个结点的二叉树有几种不同的形态？2.只有只有3个结点的二叉树有几种不同形态？分别画出来。个结点的二叉树有几种不同形态？分别画出来。计算机与软件学院（计算机与软件学院（

20、SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6二叉树的基本操作二叉树的基本操作查找类查找类插入类插入类删除类删除类 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();Post

21、OrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6性质性质1若二叉树的

22、层次从若二叉树的层次从1开始开始,则在二叉树的第则在二叉树的第i 层最多有层最多有2i-1 个结点。个结点。(i 1)证明用数学归纳法证明用数学归纳法性质性质2高度为高度为k 的二叉树最多有的二叉树最多有2k-1个结点。个结点。(k 1)证明用求等比级数前证明用求等比级数前k k项和的公式项和的公式 2 20 0+2+21 1+2+22 2+2+2k-1k-1=2 2k k-1-16.2.2二叉树的性质二叉树的性质计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&Technol

23、ogyChap6性质性质3对任何一棵二叉树对任何一棵二叉树,如果其如果其叶结点叶结点有有n0个个,度为度为2的的非叶结点非叶结点有有n2个个,则有则有n0n21证明：证明：1、结点总数为度为、结点总数为度为0的结点加上度为的结点加上度为1的结点再加上度的结点再加上度为为2的结点：的结点：n=n0+n1+n22、另一方面，二叉树中、另一方面，二叉树中1度结点有一个孩子，度结点有一个孩子，2度结点度结点有二个孩子，根结点不是任何结点的孩子，因此，结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：总数为：n=n1+2n2+13、两式相减，得到：、两式相减，得到：n0=n2+1计算机与软件学

24、院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6定义定义1满二叉树满二叉树(FullBinaryTree)一棵深度为一棵深度为k且有且有2k-1个结点的二叉树个结点的二叉树。定义定义2完全二叉树完全二叉树(CompleteBinaryTree)若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层。除第层。除第h层外，其它各层层外，其它各层(1 h-1)的结点数都达到最大个的结点数都达到最大个数，第数，第h层从左向右连续有若干结点，这就是完层从左向右连续有

25、若干结点，这就是完全二叉树。全二叉树。定义两种特殊的二叉树：定义两种特殊的二叉树：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6 A A G G F F E E D D C C B BK=3的满二叉树的满二叉树 A A C C B BK=2的满二叉树的满二叉树 A A E E D D C C B B完全二叉树完全二叉树 A A G G F F E E D D C C B B计算机与软件学院（计算机与软件学院（SchoolofComputeran

26、dSoftware）NanjingUniversityofInformationScience&TechnologyChap6&完全二叉树的特点：完全二叉树的特点：（1）除最后一层外，每一层都取最大结点数，最后一）除最后一层外，每一层都取最大结点数，最后一层结点都有集中在该层最左边的若干位置。层结点都有集中在该层最左边的若干位置。（2）叶子结点只可能在层次最大的两层出现。）叶子结点只可能在层次最大的两层出现。（3）对任一结点，若其右分支下的子孙的最大层次为）对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次为，则其左分支下的子孙的最大层次为L或或L+1。&满二叉树的特点

27、：满二叉树的特点：每一层都拥有最多结点数每一层都拥有最多结点数计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6思考：思考：满二叉树与完全二叉树的有何异同点？满二叉树与完全二叉树的有何异同点？满二叉树一定是一棵完全二叉树，反之满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面完全二叉树的叶子结点可以

28、分布在最下面两层。两层。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap61231145891213671014151231145891267101234567123456计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6性质性质4 具有具有n个结点的完全二叉树的高度个结点的完全二叉树的高度为为+1。证

29、明：证明：设深度为设深度为k，根据二叉树性质，根据二叉树性质2知知：2k-1-1n2k-1，即即：2k-1n2k，于是有：于是有：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap61.当当i1,结点结点i为根结点，无双亲结为根结点，无双亲结点，否则其双亲为点，否则其双亲为 ;2.若若2in,结点结点i无左子女无左子女;否则其左否则其左子女为子女为2i;3.若若2i1n,结点结点i无右子女无右子女;否则否则其右子女为其右子女为2i1。性质性质5 对具

30、有对具有n个结点的完全二叉树进行编号（按层次从左到右）个结点的完全二叉树进行编号（按层次从左到右）编号可以反映二叉树结点之间的关系编号可以反映二叉树结点之间的关系。ii+1 2i2i12i22i3计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap61243568910711121314151617例：例：(1)(1)i=8,i=8,其双亲为其双亲为4 4号结点。号结点。(2)(2)i=18i=18，则，则9 9号结号结点无左子女。点无左子女。i=14

31、i=14，则，则7 7号结号结点的左子女为点的左子女为1414号结点。号结点。(3)(3)i=19i=19，则，则9 9号结号结点无右子女。点无右子女。i=15i=15，则，则7 7号结号结点的右子女为点的右子女为1515号结点。号结点。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6顺序存储结构顺序存储结构链接存储结构链接存储结构二叉链表二叉链表三叉链表三叉链表6.2.3二叉树的存储二叉树的存储计算机与软件学院（计算机与软件学院（Schoolo

32、fComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6一、顺序存储结构一、顺序存储结构 用一组用一组连续的连续的存储单元存储二叉树的结点数存储单元存储二叉树的结点数据。据。要求：要求：必须把二叉树中的所有结点，按照一定的必须把二叉树中的所有结点，按照一定的次序排成为一个线性序列，结点在这个序列中的相次序排成为一个线性序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。互位置能反映出结点之间的逻辑关系。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）N

33、anjingUniversityofInformationScience&TechnologyChap6二叉树的顺序存储示例：二叉树的顺序存储示例：ABCABC12312345AB#C12345ABC123对于完全二叉树，结点的层次序列反映了整个二叉树的结构。对于完全二叉树，结点的层次序列反映了整个二叉树的结构。对于一般二叉树，则要通过添加对于一般二叉树，则要通过添加虚结点虚结点将其扩充为完全二叉树。将其扩充为完全二叉树。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&Tec

34、hnologyChap61A2B3C4#5D6E7F8#9#10G11H二叉树的顺序存储示例：二叉树的顺序存储示例：计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6思考：思考：对如下一棵二叉树采用顺序存储结构，需要添加对如下一棵二叉树采用顺序存储结构，需要添加几个空结点几个空结点?计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&

35、TechnologyChap6小结：小结：对于完全二叉树对于完全二叉树：结点编号完全可反映出该二叉树中结点之间的逻辑关结点编号完全可反映出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编号与数组下标建立一系，可将此类二叉树中结点的编号与数组下标建立一一对应关系，所以采用顺序存储结构较好。一对应关系，所以采用顺序存储结构较好。对于一般的二叉树对于一般的二叉树：需要添加需要添加“虚虚”结点，使之成为一棵完全二叉树，此结点，使之成为一棵完全二叉树，此时仍可用顺序存储结构表示这棵二叉树。时仍可用顺序存储结构表示这棵二叉树。但这样可能造成空间浪费，但这样可能造成空间浪费，最坏情况最坏情况是：深度为

36、是：深度为k且只且只有有k个结点的单支树，需要长度为个结点的单支树，需要长度为2k1的空间。的空间。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ABCDFEGH二、二、二叉树的链式存储结构二叉树的链式存储结构结点结构的设计结点结构的设计二叉链表结点结构二叉链表结点结构三叉链表结点结构三叉链表结点结构计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformat

37、ionScience&TechnologyChap6二叉链表二叉链表typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针左右孩子指针BiTNode,*BiTree;lchild data rchild ABCDEFG在在n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针域个空指针域 AB C D E F G空指针个数：空指针个数：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1结点包含三个域：数据域、左指针域、右指针域结点包含三个域：数据域、左指针域、右指

38、针域 计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6三叉链表三叉链表typedefstruct BiTNode TElemTypedata;structBiTNode*lchild,*rchild,*parent;BiTNode,*BiTree;lchild data parent rchildABCDEFG A B C D E F G结点包含四个域：数据域、双亲指针域、左指针域、右指针域结点包含四个域：数据域、双亲指针域、左指针域、右指针域计

39、算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap66.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历定义遍历定义：指按照某种顺序访问二叉树中的每个结指按照某种顺序访问二叉树中的每个结点，并且使每个结点被访问一次且仅一次。点，并且使每个结点被访问一次且仅一次。6.3.1遍历二叉树遍历二叉树n遍历操作使非线性结构线性化遍历操作使非线性结构线性化。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）Na

40、njingUniversityofInformationScience&TechnologyChap6遍历的顺序遍历的顺序RT、L、R分别代表访问根结点、遍历左子树、遍历右分别代表访问根结点、遍历左子树、遍历右子树子树R遍历方式有遍历方式有6种：种：RTLR、TRL、LTR、RTL、LRT、RLT。TLR（先序遍历）（先序遍历）;LTR（中序遍历）（中序遍历）;LRT（后序遍历）（后序遍历）;按深度遍历按深度遍历 按广度遍历按广度遍历(层序遍历层序遍历)：从上到下、从左到右。：从上到下、从左到右。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）Nan

41、jingUniversityofInformationScience&TechnologyChap6ADBCTLRATLRTLRBDCTLR先序遍历序列：先序遍历序列：ABDC先序遍历先序遍历:先序遍历（先序遍历（TLR）若二叉树非空若二叉树非空（1）访问根结点）访问根结点（2）先序遍历左子树）先序遍历左子树（3）先序遍历右子树）先序遍历右子树计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ADBCLTRBLTRLTRADCLTR中序遍历序列：中

42、序遍历序列：BDAC中序遍历（中序遍历（LTR）若二叉树非空若二叉树非空（1）中序遍历左子树）中序遍历左子树（2）访问根结点）访问根结点（3）中序遍历右子树）中序遍历右子树中序遍历中序遍历:计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6ADBCLRTLRTLRTADCLRT后序遍历序列：后序遍历序列：DBCAB后序遍历（后序遍历（LRT）若二叉树非空若二叉树非空（1）后序遍历左子树）后序遍历左子树（2）后序遍历右子树）后序遍历右子树（3）访问根

43、结点）访问根结点后序遍历后序遍历:计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6先序：先序：a*bc def 中序：中序：ab*cdef 后序：后序：abcd*ef计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6(一一)二叉树遍历的递归算法二叉树遍历的递归算法先序遍历的定义等价于：先序遍历的定义等

44、价于：若二叉树为空，结束若二叉树为空，结束 基本项基本项（终止条件）（终止条件）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；1、先序遍历递归算法、先序遍历递归算法(采用二叉链表采用二叉链表)StatusPreOrderTraverse(BiTreeT,Status(*visit)(TElemTypee)/*功能功能:先序遍历二叉树先序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的为对结点的处理处理方法方法*/if(T)/若根结点不空若根结点不空if(vi

45、sit(T-data)/访问根结点访问根结点if(PreOrderTraverse(T-lchild,visit)/先序遍历根的左子树先序遍历根的左子树if(PreOrderTraverse(T-rchild,visit)/先序遍历根的右子树先序遍历根的右子树returnOK;主程序主程序Pre(T)返回返回返回返回pre(T R);返回返回返回返回pre(T R);ACBDTBvisit(B);pre(T L);BTAvisit(A);pre(T L);ATDvisit(D);pre(T L);DTCvisit(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是

46、空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：ABDC计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6BACEDGF先序遍历序列：先序遍历序列：A B DEG C FABDEGCF递归调用递归调用返回返回计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&Te

47、chnologyChap62、中序遍历递归算法、中序遍历递归算法StatusInOrderTraverse(BiTreeT,Status(*visit)(TElemTypee)/*功能功能:中序遍历二叉树中序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的处理方法为对结点的处理方法*/if(T)/若根结点不空若根结点不空if(InOrderTraverse(T-lchild,visit)/中序遍历根结点的左子树中序遍历根结点的左子树if(visit(T-data)/访问根结点访问根结点if(InOrderTraverse(T-rchild,visit)/中序遍历根结点的右

48、子树中序遍历根结点的右子树returnOK;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap63、后序遍历递归算法、后序遍历递归算法StatusPostOrderTraverse(BiTreeT,Status(*visit)(TElemTypee)/*功能功能:后序遍历二叉树后序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的处理方法为对结点的处理方法*/if(T)/若根结点不空若根结点不空if(PostOrderTraver

49、se(T-lchild,visit)/后序遍历根结点的左子树后序遍历根结点的左子树if(PostOrderTraverse(T-rchild,visit)/后序遍历根结点的右子树后序遍历根结点的右子树if(visit(T-data)/访问根结点访问根结点returnOK;计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6(二二)二叉树遍历的非递归算法二叉树遍历的非递归算法 递归算法逻辑清晰、易懂；递归算法逻辑清晰、易懂；但但在在实实现现时时，由由于

50、于函函数数调调用用栈栈层层层层叠叠加加，效效率不高，而采用非递归算法可提高效率。率不高，而采用非递归算法可提高效率。计算机与软件学院（计算机与软件学院（SchoolofComputerandSoftware）NanjingUniversityofInformationScience&TechnologyChap6T:AT:BT:ET:G栈在先序遍历中的作用栈在先序遍历中的作用BACEDGFT先序遍历序列：A B DEGn栈用于栈用于存放已处理的根结点，以备在处理完该存放已处理的根结点，以备在处理完该结点的左子树后再处理其右子树结点的左子树后再处理其右子树计算机与软件学院（计算机与软件学院（Sc