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

1、计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6引言：引言： 树型构造是一类重要的非线性构造。树型构造是结点之间有树型构造是一类重要的非线性构造。树型构造是结点之间有分支，且具有层次关系的构造，非

2、常类似于自然界中的树。分支，且具有层次关系的构造，非常类似于自然界中的树。 树构造在客观世界大量存在。例如家谱、行政组织机构都可树构造在客观世界大量存在。例如家谱、行政组织机构都可用树笼统地表示。用树笼统地表示。 树在计算机领域中也有着广泛的运用：树在计算机领域中也有着广泛的运用： 在编译程序中，用树来表示源程序的语法构造；在编译程序中，用树来表示源程序的语法构造； 在数据库系统中，可用树来组织信息；在数据库系统中，可用树来组织信息； Windows操作系统中对磁盘文件的管理。操作系统中对磁盘文件的管理。 计算机与软件学院（计算机与软件学院（School of Computer and Sof

3、tware）Nanjing University of Information Science & TechnologyChap6教师教师学生学生其他人员其他人员20072007级级 20212021级级 20212021级级20212021级级南信大南信大数理院数理院计算机院计算机院语院语院叶子叶子根根子树子树计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6 第六章第六章 树和二叉树树和二叉树6.1 6.1

4、树的定义和根本术语树的定义和根本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.5 6.5 哈夫曼树及运用哈夫曼树及运用计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6树的定义、术语、操作树的定义、术语、操作二叉树定义、性质、操作二叉树定义、性质、操作二叉树的存储构造二叉树的存储构造( (重点重点) )顺序存储、链接存储顺序存储、链接存储线

5、索二叉树线索二叉树( (难点难点) )特殊的链接存储构造特殊的链接存储构造二叉树二叉树运算运算递归递归遍历遍历非递归非递归遍历遍历二叉树遍历二叉树遍历( (重点重点) )二叉树二叉树其他运算其他运算树的存储构造树的存储构造森林与二叉树的转换森林与二叉树的转换树和森林的遍历树和森林的遍历二叉树二叉树运用运用哈夫曼树哈夫曼树及其运用及其运用( (重点、重点、难点难点) )内容及重、难点内容及重、难点6.16.16.26.26.26.26.36.36.36.36.46.46.56.5计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing U

6、niversity of Information Science & TechnologyChap66.1 6.1 树的定义与术语树的定义与术语一、树的定义一、树的定义 树是由树是由n (n n (n 0) 0)个结点组成个结点组成的有限集合。假设的有限集合。假设n = 0n = 0，称为空树；，称为空树；假设假设n 0n 0，那么：，那么： 有一个特定的元素称之为根有一个特定的元素称之为根(root)(root)的结点，的结点， 除根以外的其他结点划分为除根以外的其他结点划分为m m (m (m 0) 0)个互不相交的有限集合个互不相交的有限集合T1, , T1, , TmTm，每个

7、集合又是一棵树，并且称之为，每个集合又是一棵树，并且称之为根的子树根的子树(subTree)(subTree)。计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6A只需根结点的树只需根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子子树树例：例：计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information

8、 Science & TechnologyChap6ACGBDEFKLHMIJ1树中只需根结点没有前趋；树中只需根结点没有前趋；2除根外，其他结点都有且仅一个前趋；除根外，其他结点都有且仅一个前趋；3树的结点，可以有零个或多个后继；树的结点，可以有零个或多个后继；4除根外的其他结点，都存在独一条从根到该结点的途径。除根外的其他结点，都存在独一条从根到该结点的途径。( (非空非空) )树构造特点：树构造特点：计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science

9、 & TechnologyChap6线性构造线性构造树型构造树型构造第一个数据元素第一个数据元素( (无前驱无前驱) ) 根结点 (无前驱)最后一个数据元素最后一个数据元素( (无后继无后继) )多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & Te

10、chnologyChap6ABCDEFGHIJKLM树形表示树形表示( A( B(E(K,L), F ), C(G), D(H(M), I, J) )广义表二、树的表示方法二、树的表示方法 I JFKLGMCCDBEA文氏图文氏图凹入表凹入表计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6 结点结点(node) 结点的度结点的度(degree) 结点的子树个数结点的子树个数 分支分支(branch)结点结点 度不为度不

11、为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结点结点L的双亲：的双亲

12、：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6 祖先祖先(ancestor)结点结点 结点的祖先是从根到该结点所经结点的祖先是从根到该结点所经分支上的一切结点分支上的一切结点 . 子孙子孙(descendant)结点结点 以某结点为根的子树中的任一结以某结点为根的子树中的任一结点都为该结点的子孙点都为该结点的子孙. 结点的层次结点的层次(level) 根结点

13、的层数为根结点的层数为1，其他结点的，其他结点的层数为双亲结点的层数加层数为双亲结点的层数加1 树的高度树的高度(depth) 树中结点的最大层数树中结点的最大层数 树的度树的度(degree)树的根本术语树的根本术语( (续续) )ABCDEFGHIJKLM结点结点K的祖先：的祖先：A,B,E结点结点B的子孙：的子孙：E,F,K,L树的度：树的度：3树的高度：树的高度：4结点结点A的层次：的层次：1结点结点M的层次：的层次：4计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information

14、Science & TechnologyChap6根本术语续：根本术语续：计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6树的运算分树的运算分3 3大类：大类：第一类：查找类第一类：查找类遍历树中每个结点、求树的形状如树高度遍历树中每个结点、求树的形状如树高度、判树空、判树空查找满足某种特定关系的结点查找满足某种特定关系的结点, ,如查找根结如查找根结点等点等第二类，插入类第二类，插入类包括初始化空树、构造树、

15、在树的当前结点包括初始化空树、构造树、在树的当前结点上插入一个新结点等；上插入一个新结点等；第三类，删除类第三类，删除类包括清空树、销毁树、删除树中结点。包括清空树、销毁树、删除树中结点。四、树的根本操作四、树的根本操作P118P118计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6五、树的笼统数据类型定义五、树的笼统数据类型定义 ADT Tree数据对象数据对象D：由：由n个具有一样特性的元素构个具有一样特性的元素构

16、成的集合成的集合数据关系数据关系R： 假设假设D为空集，那么称为空树为空集，那么称为空树 。 否那否那么么: (1) 在在D中存在独一的称为根的数据元素中存在独一的称为根的数据元素root; (2) 当当n1时时,其他结点可分为其他结点可分为m (m0)个个互不相交的有限集互不相交的有限集T1, T2, , Tm,其中每其中每一棵子集本身又是一棵符合本定义的树一棵子集本身又是一棵符合本定义的树,称称为根为根root的子树的子树. 根本操作根本操作P：Root(T) / 求树的根结点求树的根结点 Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur

17、_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 CreateTree(&T, definition) / 构造树构造树InitTree(&T) / 初始化置空树初始化置空树 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6TreeEmpty(T) / 断定树能否为空树断定树能否为空树 TreeDepth(T) /

18、求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历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棵子树棵

19、子树 ADT Tree计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap66.2 6.2 二叉树二叉树6.2.1 二叉树的定义二叉树的定义 二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。ABCDEFGHK根结点左子树右子树阐明阐明1二叉树中每个结点最多有两棵子树二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于；二叉树每个结点度小于等于2；2左、右子树不能颠倒左、右子树不能颠

20、倒有序树；有序树；3二叉树是递归构造。二叉树是递归构造。计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6LRLR二叉树的五种根本形状二叉树的五种根本形状计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6 问题： 1.只需两个结点的二叉树有几种不同

21、的形状？2.只需只需3个结点的二叉树有几种不同形状？分别画出来。个结点的二叉树有几种不同形状？分别画出来。 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6 二叉树的根本操作二叉树的根本操作查找类查找类插入类插入类删除类删除类 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSi

22、bling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);ClearBiTree(&T); DestroyBiTr

23、ee(&T);DeleteChild(T, p, LR);计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6性质性质1 假设二叉树的层次从假设二叉树的层次从1开场开场, 那么在二叉树的第那么在二叉树的第 i 层最层最多有多有 2i-1 个结点。个结点。(i 1) 证明用数学归纳法证明用数学归纳法性质性质2 高度为高度为 k 的二叉树最多有的二叉树最多有 2k-1个结点。个结点。(k 1) 证明用求等比级数前证明用

24、求等比级数前k项和的公式项和的公式 20 + 21 + 22 + + 2k-1 = 2k-16.2.2 二叉树的性质二叉树的性质计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6性质性质3 对任何一棵二叉树对任何一棵二叉树, 假设其叶结点有假设其叶结点有 n0 个个, 度为度为2的非叶结点有的非叶结点有 n2 个个, 那么有那么有 n0n21证明：证明：1、结点总数为度为、结点总数为度为0的结点加上度为的结点加上度为1的

25、的结点再加上度为结点再加上度为2的结点：的结点： n = n0 + n1 + n22、另一方面，二叉树中、另一方面，二叉树中1度结点有一个孩度结点有一个孩子，子，2 度结点有二个孩子，根结点不是任度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：何结点的孩子，因此，结点总数为：n = n1 + 2n2 + 13、两式相减，得到：、两式相减，得到： n0 = n2 + 1 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & Technolog

26、yChap6定义定义2 完全二叉树完全二叉树(Complete Binary Tree) 假设设二叉树的高度为假设设二叉树的高度为h，那么共有，那么共有h层。层。除第除第h层外，其它各层层外，其它各层(1 h-1)的结点数都到的结点数都到达最大个数，第达最大个数，第h层从左向右延续有假设干结层从左向右延续有假设干结点，这就是完全二叉树。点，这就是完全二叉树。定义两种特殊的二叉树：定义两种特殊的二叉树：计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science &

27、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计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6&完全二叉树的特点：完全二叉树的特点：&1除最后一层外，每一层都取最大结点数，除

28、最后一层外，每一层都取最大结点数，最后一层结点都有集中在该层最左边的假设干最后一层结点都有集中在该层最左边的假设干位置。位置。&2叶子结点只能够在层次最大的两层出现。叶子结点只能够在层次最大的两层出现。&3对任一结点，假设其右分支下的子孙的对任一结点，假设其右分支下的子孙的最大层次为最大层次为L，那么其左分支下的子孙的最大，那么其左分支下的子孙的最大层次为层次为L或或L+1。&满二叉树的特点：每一层都拥有最多结点数满二叉树的特点：每一层都拥有最多结点数计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing Un

29、iversity of Information Science & TechnologyChap6 思索：思索： 满二叉树与完全二叉树的有何异同满二叉树与完全二叉树的有何异同点？点？ 满二叉树一定是一棵完全二叉树，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二反之完全二叉树不一定是一棵满二叉树。叉树。 满二叉树的叶子结点全部在最底层满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分，而完全二叉树的叶子结点可以分布在最下面两层。布在最下面两层。计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing Uni

30、versity of Information Science & TechnologyChap61231145891213671014151231145891267101234567123456计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6性质性质4 具有具有n个结点的完全二叉树的高度个结点的完全二叉树的高度 为为 +1。n2log1log,log122nkkknk取为整数证明：证明：设深度为设深度为k，根据

31、二叉树性质，根据二叉树性质2知：知：2k-1-1n2k-1 ，即：，即：2k-1 n 2k，于是有：，于是有：计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6当当i1,结点结点i为根结点，无双亲结为根结点，无双亲结点，否那么其双亲为点，否那么其双亲为 ;假设假设2in,结点结点i无左子女无左子女;否那么否那么其左子女为其左子女为2i;假设假设2i1n,结点结点i无右子女无右子女;否否那么其右子女为那么其右子女为2i1。

32、2i性质性质5 对具有对具有n个结点的完全二叉树进展编号个结点的完全二叉树进展编号按层次从左到右编号可以反映二叉树按层次从左到右编号可以反映二叉树结点之间的关系结点之间的关系 。ii+1 2i2i12i22i32i计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap61243568910711121314151617例：例：i=8,i=8,其双亲为其双亲为4 4号结点。号结点。i=18i=18，那么，那么9 9号号结点无左子

33、女结点无左子女。i=14i=14，那么，那么7 7号结点的左子号结点的左子女为女为1414号结点号结点。i=19i=19，那么，那么9 9号号结点无右子女结点无右子女。i=15i=15，那么，那么7 7号结点的右子号结点的右子女为女为1515号结点号结点。计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6 顺序存储构造顺序存储构造 链接存储构造链接存储构造 二叉链表二叉链表 三叉链表三叉链表6.2.3 二叉树的存储二叉树

34、的存储计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6一、顺序存储构造一、顺序存储构造 用一组延续的存储单元存储二叉树的用一组延续的存储单元存储二叉树的结点数据。结点数据。 要求：必需把二叉树中的一切结点，要求：必需把二叉树中的一切结点，按照一定的次序排成为一个线性序列，按照一定的次序排成为一个线性序列，结点在这个序列中的相互位置能反映结点在这个序列中的相互位置能反映出结点之间的逻辑关系。出结点之间的逻辑关系。计算机与

35、软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6二叉树的顺序存储例如：二叉树的顺序存储例如：ABCABC12312345AB#C12345ABC123对于完全二叉树，结点的层次序列反映了整个二叉树的构造。对于完全二叉树，结点的层次序列反映了整个二叉树的构造。对于普通二叉树，那么要经过添加虚结点将其扩展为完全二叉树。对于普通二叉树，那么要经过添加虚结点将其扩展为完全二叉树。计算机与软件学院（计算机与软件学院（School of

36、Computer and Software）Nanjing University of Information Science & TechnologyChap61A2B3C4# #5D6E7F8#9#10G11H二叉树的顺序存储例如：二叉树的顺序存储例如：计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6 思索：思索： 对如下一棵二叉树采用顺序存储构造，对如下一棵二叉树采用顺序存储构造，需求添加几个空结点需求添

37、加几个空结点?计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6 小结：小结： 对于完全二叉树：对于完全二叉树： 结点编号完全可反映出该二叉树中结点之间结点编号完全可反映出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编号的逻辑关系，可将此类二叉树中结点的编号与数组下标建立一一对应关系，所以采用顺与数组下标建立一一对应关系，所以采用顺序存储构造较好。序存储构造较好。 对于普通的二叉树：对于普通的二叉树： 需求添加需

38、求添加 “虚结点，使之成为一棵完全二虚结点，使之成为一棵完全二叉树，此时仍可用顺序存储构造表示这棵二叉树，此时仍可用顺序存储构造表示这棵二叉树。叉树。 但这样能够呵斥空间浪费，最坏情况是：深但这样能够呵斥空间浪费，最坏情况是：深度为度为k且只需且只需k个结点的单支树，需求长度为个结点的单支树，需求长度为2k1的空间。的空间。计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6ABCDFEGH二、二、 二叉树的链式存储构造二

39、叉树的链式存储构造结点构造的设计结点构造的设计二叉链表结点构造二叉链表结点构造三叉链表结点构造三叉链表结点构造计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6二叉链表二叉链表typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指针左右孩子指针 BiTNode , *BiTree; lchild data rchild A

40、BCDEFG在在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结点包含三个域：数据域、左指针域、右指针域结点包含三个域：数据域、左指针域、右指针域 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6三叉链表三叉链表typedef struct BiTNode

41、 TElemType data; struct BiTNode *lchild,*rchild,*parent; BiTNode , *BiTree ;lchild data parent rchildABCDEFG A B C D E F G结点包含四个域：数据域、双亲指针域、左指针域、右指针域结点包含四个域：数据域、双亲指针域、左指针域、右指针域计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap66.3 6.3 遍历二

42、叉树和线索二叉树遍历二叉树和线索二叉树遍历定义：遍历定义： 指按照某种顺序访问二叉树中的每个指按照某种顺序访问二叉树中的每个结点，并且使每个结点被访问一次且仅结点，并且使每个结点被访问一次且仅一次。一次。6.3.1 遍历二叉树遍历二叉树n遍历操作使非线性构造线性化。遍历操作使非线性构造线性化。 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6遍历的顺序遍历的顺序RT、L、R分别代表访问根结点、遍历左子树、遍历分别代表访

43、问根结点、遍历左子树、遍历右子树右子树R遍历方式有遍历方式有6种：种：RTLR、 TRL、LTR、 RTL、 LRT 、RLT 。RTLR先序遍历先序遍历;RLTR中序遍历中序遍历;RLRT后序遍历后序遍历; 按深度遍历按深度遍历 按广度遍历按广度遍历( (层序遍历层序遍历) )：从上到下、从左：从上到下、从左到右。到右。 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6ADBCT L RAT L RT L RBDCT

44、 L R先序遍历序列：先序遍历序列：A B D C先序遍历先序遍历: :先序遍历先序遍历 T L R假设二叉树非空假设二叉树非空1访问根结点访问根结点2先序遍历左子树先序遍历左子树3先序遍历右子树先序遍历右子树计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6ADBCL T RBL T RL T RADCL T R中序遍历序列：中序遍历序列：B D A C中序遍历中序遍历L T R假设二叉树非空假设二叉树非空1中序遍历左

45、子树中序遍历左子树2访问根结点访问根结点3中序遍历右子树中序遍历右子树中序遍历中序遍历: :计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6ADBC L R TL R TL R TADCL R T后序遍历序列：后序遍历序列： D B C AB后序遍历后序遍历L R T假设二叉树非空假设二叉树非空1后序遍历左子树后序遍历左子树2后序遍历右子树后序遍历右子树3访问根结点访问根结点后序遍历后序遍历: :计算机与软件学院（计算

46、机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6先序：先序：a * bc def 中序：中序：ab * cdef 后序：后序：abcd * ef计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6( (一一) )二叉树遍历的递归算法二叉树遍历的递归算法先序遍历的定义等价

47、于：先序遍历的定义等价于：假设二叉树为空，终了假设二叉树为空，终了 根本项终止条件根本项终止条件假设二叉树非空假设二叉树非空 递归项递归项 1 1访问根结点；访问根结点； 2 2先序遍历左子树先序遍历左子树 3 3先序遍历右子树；先序遍历右子树；1、先序遍历递归算法、先序遍历递归算法(采用二叉链表采用二叉链表) Status PreOrderTraverse (BiTree T,Status (*visit)(TElemType e) /*功能功能:先序遍历二叉树先序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的处置方法为对结点的处置方法*/ if (T) /假设根结点

48、不空假设根结点不空 if(visit(T-data) /访问根结点访问根结点 if (PreOrderTraverse(T-lchild,visit) /先先序遍历根的左子树序遍历根的左子树 if(PreOrderTraverse(T-rchild,visit) /先序遍历根的右子树先序遍历根的右子树 return OK; 主程序主程序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前

49、往前往T左是空前往左是空前往pre(T R);T左是空前往左是空前往T右是空前往右是空前往T左是空前往左是空前往T右是空前往右是空前往pre(T R);先序序列：先序序列：A B D C计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6BACEDGF先序遍历序列：先序遍历序列： A B DEG C FABDEGCF递归调用递归调用前往前往计算机与软件学院（计算机与软件学院（School of Computer and S

50、oftware）Nanjing University of Information Science & TechnologyChap62、中序遍历递归算法、中序遍历递归算法Status InOrderTraverse (BiTree T,Status (*visit)(TElemType e) /*功能功能:中序遍历二叉树中序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的处置方法为对结点的处置方法*/ if (T) /假设根结点不空假设根结点不空 if (InOrderTraverse(T-lchild,visit) /中序遍中序遍历根结点的左子树历根结点的左子

51、树 if(visit(T-data) /访问根结点访问根结点 if(InOrderTraverse(T-rchild,visit) /中序中序遍历根结点的右子树遍历根结点的右子树 return OK; 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap63、后序遍历递归算法、后序遍历递归算法Status PostOrderTraverse (BiTree T,Status (*visit)(TElemType e) /*功

52、能功能:后序遍历二叉树后序遍历二叉树;参数参数:T为二叉树的根为二叉树的根,visit为对结点的处置方法为对结点的处置方法*/ if (T) /假设根结点不空假设根结点不空 if (PostOrderTraverse(T-lchild,visit) /后序后序遍历根结点的左子树遍历根结点的左子树 if(PostOrderTraverse(T-rchild,visit) /后序后序遍历根结点的右子树遍历根结点的右子树 if(visit(T-data) /访问根结点访问根结点 return OK; 计算机与软件学院（计算机与软件学院（School of Computer and Software）

53、Nanjing University of Information Science & TechnologyChap6( (二二) ) 二叉树遍历的非递归算法二叉树遍历的非递归算法 递归算法逻辑明晰、易懂；递归算法逻辑明晰、易懂； 但在实现时，由于函数调用栈层层但在实现时，由于函数调用栈层层叠加，效率不高，而采用非递归算法叠加，效率不高，而采用非递归算法可提高效率。可提高效率。 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & Technol

54、ogyChap6T: AT: BT: ET: G栈在先序遍历中的作用栈在先序遍历中的作用BACEDGFT先序遍历序列： A B DEGn栈用于存放已处置的根结点，以备在处置完该栈用于存放已处置的根结点，以备在处置完该结点的左子树后再处置其右子树结点的左子树后再处置其右子树计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6前序遍历的非递归算法根本思绪：前序遍历的非递归算法根本思绪：1)1)、访问当前结点初始时是根结点、访问

55、当前结点初始时是根结点2)2)、结点进栈，沿左指针查找左孩子。、结点进栈，沿左指针查找左孩子。3)3)、假设有左孩子，转第、假设有左孩子，转第1 1步。步。4)4)、假设无左孩子，判栈空？空那么终了。非空、假设无左孩子，判栈空？空那么终了。非空，栈顶结点出栈，栈顶结点出栈, ,转向右子树，转第转向右子树，转第1 1步。步。1 1、前序遍历的非递归算法、前序遍历的非递归算法计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6

56、1 1、前序遍历的非递归算法、前序遍历的非递归算法 运用一个栈运用一个栈S S，存放已处置的根结点，以，存放已处置的根结点，以备在处置完该结点的左子树后再处置其右子树备在处置完该结点的左子树后再处置其右子树。初始，栈为空。初始，栈为空。Status PreOrderTraverse (BiTree T,Status Status PreOrderTraverse (BiTree T,Status ( (* *visit)(TElemType e) visit)(TElemType e) /* *功能功能: :前序遍历二叉树前序遍历二叉树; ;参数参数:T:T为二叉树的为二叉树的根根,visit

57、,visit为对结点的处置方法为对结点的处置方法* */ / P=T; InitStack(S); / P=T; InitStack(S); /初始化栈初始化栈 while (p | (!StackEmpty(S) / while (p | (!StackEmpty(S) /二二叉树未处置完叉树未处置完 if (p) / if (p) /当前未遇空结点当前未遇空结点 if (!visit(p-data) if (!visit(p-data) /访问当前子树根结点访问当前子树根结点 return ERROR; / return ERROR; /访问当前子树根结点时出错访问当前子树根结点时出错 p

58、ush(S,p); / push(S,p); /结点压结点压栈栈 p=p-lchild; / p=p-lchild; /继续向左继续向左子树前进子树前进 else else pop(S,p); p=p-rchild; / pop(S,p); p=p-rchild; /弹出栈顶结点，处置其右子树弹出栈顶结点，处置其右子树 return OK; return OK; 计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6ABCD

59、E处置的数据项处置的数据项 栈栈S中内容中内容 p的指向的指向 空空 A A A B B AB C C ABC AB A D D AD A E E AE A 空空 p计算机与软件学院（计算机与软件学院（School of Computer and Software）Nanjing University of Information Science & TechnologyChap6BACEDGFTT: AT: BT: ET: G栈在中序遍历中的作用栈在中序遍历中的作用中序遍历序列：D B Gn栈用于保管当前结点的祖先结点栈用于保管当前结点的祖先结点计算机与软件学院（计算机与软件学院（S

60、chool of Computer and Software）Nanjing University of Information Science & TechnologyChap62 2、中序遍历的非递归算法、中序遍历的非递归算法Status InorderTraverse(BiTree Status InorderTraverse(BiTree T,Status(T,Status(* *visit)(TElemType e)visit)(TElemType e) InitStack(S); p=T; InitStack(S); p=T; while ( p | !StackEmpty(S) ) while ( p | !StackEmpty(S) ) if (p) / if (p) /未到达左子树末未到达左子树末端端 Push(S,p); / Push(S,p); /当前当前结点压栈结点压栈 p=p-lchild; / p=p-lchild; /继续继续向左子树前进向左子树前进 else / else /已到达左子树末端已到达左子树末端 Pop(S,p); / Pop(S,p); /弹出栈顶弹出栈顶 if(!visit(p-data) if(!visit(p-data) return ERROR; /return ERROR; /处置该结点处置该结