第五章java数据结构树和二叉树

1、1第五章 树和二叉树5.1 5.1 树的有关概念树的有关概念5.2 5.2 二叉树二叉树5.35.3 二叉树的遍历二叉树的遍历5.4 5.4 遍历的应用遍历的应用5.5 5.5 线索二叉树线索二叉树5.6 5.6 树和森林树和森林5.7 5.7 哈夫曼树及应用哈夫曼树及应用2第六章第六章 树和二叉树树和二叉树本章学习要点：本章学习要点： 熟练掌握熟练掌握二叉树的结构特点，二叉树的结构特点，了解了解相应的证明方法；相应的证明方法； 熟悉熟悉二叉树的各种存储结构的特点及使用范围；二叉树的各种存储结构的特点及使用范围； 熟练掌握熟练掌握各种序遍历的递归和非递归算法，各种序遍历的递归和非递归算法，了解

2、了解遍历过程中遍历过程中“栈栈” 的状态，并能的状态，并能灵活运用灵活运用遍历算法实现二叉树的其它各种运算；遍历算法实现二叉树的其它各种运算； 了解了解线索化的实质是建立结点与其在相应序列中的前驱或后继线索化的实质是建立结点与其在相应序列中的前驱或后继之之 间的直接联系，间的直接联系，熟练掌握熟练掌握在中序线索化树上找给定结点的前驱和在中序线索化树上找给定结点的前驱和 后继的方法；后继的方法； 熟悉熟悉树的各种存储结构及其特点；树的各种存储结构及其特点； 学会编写学会编写实现树的各种运算的算法；实现树的各种运算的算法； 了解了解最优树的特性，最优树的特性，掌握掌握建立最优树和哈夫曼编码的方法建

3、立最优树和哈夫曼编码的方法36.1 树的有关概念 5.15.1 树的有关概念树的有关概念1.1. 树的概念树的概念2. 2. 树的应用树的应用3.3. 树的表示树的表示树的有关术语树的有关术语5 树的基本操作树的基本操作45.1 树的有关概念1树的概念树的概念 树（树（Tree）是）是n（n 0）个结点的有限集合，在任一棵非空树）个结点的有限集合，在任一棵非空树(n0)中：中：（1）有且仅有一个称为根的结点。）有且仅有一个称为根的结点。（2）其余结点可分为）其余结点可分为m（m 0）个互不相交的集合，而且这些集合）个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。中的每

4、一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义树是递归结构，在树的定义中又用到了树的概念中又用到了树的概念J JI IA AC CB BD DH HG GF FE EK KL LM M从逻辑结构看：从逻辑结构看：1）树中只有根结点没有前趋；）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点）除根外的其他结点，都存在唯一条从根到该结点的路径；的路径；5）树是一种分枝结构）树是一种分枝结构 （除了一个称为根的结点外（除

5、了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。个或多个直接后继。55.1 树的有关概念例：下面的图是一棵树例：下面的图是一棵树T=A, B, C, D, E, F, G, H, I, JT=A, B, C, D, E, F, G, H, I, J，K K，L L，MMA A是根，其余结点可以划分为是根，其余结点可以划分为3 3个个互不相交的集合：互不相交的集合： T T1 1=B, E, F=B, E, F，K K，L , TL , T2 2=C, G , T=C, G , T3 3=D, H, I, J=D, H

6、, I, J，MM这些集合中的每一集合都本身又是一棵树，它们是这些集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。 例如例如 对于对于T T1 1，B B是根，其余结点可以划分为是根，其余结点可以划分为2 2个个互不相交的集合：互不相交的集合： T1111=E，K，L，T1212=F，T1111,T1212 是是B 的子树。的子树。J JI IA AC CB BD DH HG GF FE EK KL LM M65.1 5.1 树的有关概念树的有关概念2树的应用树的应用 1）树可表示具有分枝结构关系的对象）树可表示具有分枝结构关系的对象例例1家族族谱家族族谱 设某家庭有设某家庭有13个

7、成员个成员A、B、C、D、E、F、G、H、I、J，K，L，M他们之间的关系可下图所示的树表示：他们之间的关系可下图所示的树表示：例例2单位行政机构的组织关系：单位行政机构的组织关系：J JI IA AC CB BD DH HG GF FE EK KL LM M75.1 树的有关概念 2）树是常用的数据组织形式）树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。据，将它们用树的形式来组织。例例3 计算机的文件系统计算机的文件系统 不论是不论是DOS文件系统还是

8、文件系统还是window文件系统，所有的文件是用树的形式来组织文件系统，所有的文件是用树的形式来组织的。的。文件夹文件夹1 1 文件夹文件夹n n 文件文件1 1 文件文件2 2文件夹文件夹11 11 文件夹文件夹12 12 文件文件11 11 文件文件1212C C85.1 树的有关概念3 树的表示树的表示 1）图示表示）图示表示 2）二元组表示）二元组表示 3）嵌套集合表示）嵌套集合表示 4）凹入表示法（类似书的目录）凹入表示法（类似书的目录） 5）广义表表示）广义表表示（A A（B B（E E（K,LK,L）,F,F）,C,C（G G）,D,D（H H（M M）,I,J,I,J）) )）

9、广义表表示广义表表示ABEKLFCGDHMJI凹凹入入表表示示法法AEDHJIKLMFGC嵌套集合表示嵌套集合表示B9 5.1 树的有关概念树的树的 基本术语基本术语 树的结点：包含一个数据元素及若干指树的结点：包含一个数据元素及若干指向子树的分支；向子树的分支；孩子结点孩子结点(child)：结点的子树的根称为该结点：结点的子树的根称为该结点的孩子；的孩子；双亲结点双亲结点(parent)：B 结点是结点是A 结点的孩子，结点的孩子， 则则A结点是结点是B 结点的双亲；结点的双亲；兄弟结点兄弟结点(sibling)：同一双亲的孩子结点；：同一双亲的孩子结点；堂兄结点堂兄结点(cousin)：

10、其双亲在同一层上的结点；：其双亲在同一层上的结点；祖先结点祖先结点: 从根到该结点的所经分支上的所有结点从根到该结点的所经分支上的所有结点 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙J JI IA AC CB BD DH HG GF FE EK KL LM M10 5.1 树的有关概念树的树的 基本术语基本术语结点层结点层：根结点的层定义为：根结点的层定义为1；根的孩子为第二层结点，依此类推；根的孩子为第二层结点，依此类推树的深度树的深度：树中结点的最大层数，也称为树的高度：树中结点的最大层数，也称为树的高度结点的度结点的度

11、：结点具有的子树个数：结点具有的子树个数树的度树的度： 树中最大的结点度树中最大的结点度叶子结点叶子结点：也叫终端结点，是度为：也叫终端结点，是度为 0 的结点的结点分枝结点分枝结点：也叫非终端结点，是度不为：也叫非终端结点，是度不为0的结点的结点有序树有序树：子树有序的树，如：家族树；：子树有序的树，如：家族树； 最左边的子树的根成为第一个孩子最左边的子树的根成为第一个孩子,最右边的称为最后一个孩子最右边的称为最后一个孩子无序树无序树：不考虑子树的顺序；：不考虑子树的顺序；森林森林；互不相交的树的集合；森林和树之间的联系是：一棵树去；互不相交的树的集合；森林和树之间的联系是：一棵树去 掉根，

12、其子树构成一个森林；一个森林增加一个根结点成为树。掉根，其子树构成一个森林；一个森林增加一个根结点成为树。J JI IA AC CB BD DH HG GF FE EK KL LM M115.1 树的有关概念5 树的基本操作树的基本操作 树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1 1）initate (T)： T 树的初始化，置树的初始化，置T为空树为空树。包括建树。包括建树。2） root (T)： 求求T 树的根。树的根。3）parent (T , x ): 求求T 树中树中 x 结点的双亲结点。结

13、点的双亲结点。4）Child (T, x, i )： 求求 T 树中树中 x 结点的第结点的第 i 个孩子结点。个孩子结点。5）right_Sibling (T, x )： 求求T 树中树中 x 结点的右兄弟结点的右兄弟6）insert_Child (y, i, x )： 将根为将根为 x 的子树置为的子树置为 y 结点的第结点的第 i 个孩子个孩子7）del_child (x, i)： 删除删除 x 结点的第结点的第i 个孩子个孩子8）traverse (T)： 遍历遍历T树。按某个次序依次访问树中每一个结点，并使每个结树。按某个次序依次访问树中每一个结点，并使每个结 点都被访问且只被访问一

14、次。点都被访问且只被访问一次。9）clear (T)： 置置T为空树为空树 125. 2 二二 叉叉 树树 树是一种分枝结构的对象，在树的概念中，树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单形态多种多样，本章我们主要讨论一种最简单的树的树二叉树。二叉树。135.2 二 叉 树 5.2 5.2 二叉树二叉树一一 二叉树的概念二叉树的概念二二 二叉树的性质二叉树的性质三三 二叉树的存储结构二叉树的存储结构145.2 二 叉 树一一 二叉树的概念二叉树的概念1 1 二叉树的定义二叉树的定

15、义二叉树：二叉树： 或为空树，或由根及两颗不相交的左子树、右子树构成，并且或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。左、右子树本身也是二叉树。说明说明1 1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2;2 2）左、右子树不能颠倒）左、右子树不能颠倒有序树有序树; ;3 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念; ; A A F F G G E E D D C C B B155.2 二 叉 树 (a)(a)、

16、(b)(b)是不同的二叉树，是不同的二叉树， (a)(a)的左子树有四个结点的左子树有四个结点，(b)(b)的左子树有两个结点，的左子树有两个结点， A A F F G G E E D D C C B B(a)(a) A A G G E E D D B B C C F F(b)(b)165.2 二 叉 树 2 二叉树的基本形态二叉树的基本形态(a)(a)空树空树 (b)(b)仅有根仅有根(c) (c) 右子树空右子树空(e) (e) 左子树空左子树空(d) (d) 左、右子树均在左、右子树均在3个结点的树具有个结点的树具有2种基本形态种基本形态3个结点的二叉树具有个结点的二叉树具有5中基本形态

17、中基本形态175.2 二 叉 树3应用举例 可以用二叉树表示表达式 a+b*(c-d)-e/f e e d d c c b b f f a a + + * * / / - - - -185.2 二 叉 树二二 二叉树性质二叉树性质n性质性质1 1 二叉树第二叉树第i i层上至多层上至多2 2i-1i-1个结点（个结点（i=1)i=1) 证明：证明：( (采用数学归纳法采用数学归纳法) ) 当当i=1i=1时，只有时，只有1 1个根结点。显然个根结点。显然 2 21-11-1 =1 =1，命题成立。，命题成立。 假设对所有的假设对所有的j(1jj(1ji)i)命题成立，即第命题成立，即第j j层

18、上至多层上至多2 2j-1j-1个结点个结点; ; 现证明现证明j=ij=i时命题仍然成立。时命题仍然成立。 由归纳假设知，二叉树的由归纳假设知，二叉树的i-1i-1层至多有层至多有2 2i-2i-2个结点个结点又由二叉树的定义知，二叉树每个结点的度至多为又由二叉树的定义知，二叉树每个结点的度至多为2 2 第第i i层上的最大结点数目层上的最大结点数目=2=2* *第第i-1i-1层上的最大结点数目层上的最大结点数目=2=2* *2 2i-2i-2 = 2 = 2i-1i-1 故故j=ij=i时命题成立时命题成立 从而该命题成立。从而该命题成立。195.2 二 叉 树n 性质性质2 2 深度为

19、深度为k k的二叉树至多的二叉树至多2 2k k-1-1个结点（个结点（k=1)k=1)证明：深度为证明：深度为k k的二叉树的结点的最大数目的二叉树的结点的最大数目 每层结点的最大数目之和每层结点的最大数目之和2 20 0+2+21 1+2 2k-1k-12 2k k-1-1206.2 二叉树n 性质性质3 对任何一棵二叉树对任何一棵二叉树T，若其终端结点数目为，若其终端结点数目为n0,度为度为2的结点数目为的结点数目为n2，则，则n0=n2+1。证明：证明：设二叉树设二叉树T的总结点数目为的总结点数目为n,度为度为1的结点数目为的结点数目为n1， 则则 n=n0+ n1+ n2 (1) 又

20、由于二叉树又由于二叉树T中，除根结点以外，每个结点刚好有一个分支指向，中，除根结点以外，每个结点刚好有一个分支指向， 设设B为分支总数，则为分支总数，则 n=B+1 (2) 而二叉树的这些分支是由度为而二叉树的这些分支是由度为1和度为和度为2的结点产生，的结点产生， 则则 B=n1+ 2 n2 (3) 综上三式，可知综上三式，可知n0=n2+1成立。成立。思考思考 如果一棵树有如果一棵树有n1个度数为个度数为1的结点，的结点，n2个度数为个度数为2的结点，的结点， ，nm个度数为个度数为m的结点，则终端结点数的结点，则终端结点数n0= ？215.2 二 叉 树两种特殊的二叉树两种特殊的二叉树满

21、二叉树满二叉树：如果深度为：如果深度为k k的二叉树，有的二叉树，有2 2k k-1-1个结点则称为满二叉树；个结点则称为满二叉树； A A G G F F E E D D C C B B A A C C B BK=3K=3的满二叉树的满二叉树K=2K=2的满二叉树的满二叉树225.2 二 叉 树完全二叉树完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；且最下层结点都集中在该层的最左端，则称为完全二叉树； G G A A E E D D C C B B(c)(c) A A E E

22、 D D C C B B(b)(b)、(b)(b)完全二叉树(c) (c) 不是完全二叉树 A A(a)(a) G G F F E E D D C C B B235.2 二 叉 树下面是两个关于完全二叉树的性质下面是两个关于完全二叉树的性质 性质性质4 4 具有具有n n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为：trunc(logtrunc(log2 2 n)+1n)+1， trunc(x)trunc(x)为取整函数。为取整函数。证明：假设完全二叉树的深度为证明：假设完全二叉树的深度为k,k,则由性质则由性质2 2和完和完全二叉树的定义知：全二叉树的定义知：2 2k-1 k-1

23、-1-1 n 2n 2k k -1-1 ，即，即2 2k-1k-1nn 2 2k k对上式取对数有：对上式取对数有：k-1logk-1log2 2n nk k由于由于k k是整数，故是整数，故k= trunck= trunc（2 2n n）+1+1245.2 二叉树对完全二叉树的结点编号：对完全二叉树的结点编号：从上到下，每一层从左到右从上到下，每一层从左到右 性质性质5 5：在一棵有在一棵有n n个结点的完全二叉树中个结点的完全二叉树中, ,对于编号为对于编号为i(i(1 1in)的结点的结点: :1 1）当）当i=1i=1，结点，结点i i为根结点为根结点1 1）若有左孩子）若有左孩子(

24、(2i2in n) )，则左孩编号为，则左孩编号为2i2i2 2）若有右孩子）若有右孩子( (2i+12i+1n) )，则右孩子结点编号为，则右孩子结点编号为2i+12i+13 3）若有双亲，则双亲结点编号为）若有双亲，则双亲结点编号为trunc(i/2)trunc(i/2) A A F F E E D D C C B B1 12 23 34 45 56 6255.2二叉树 1 1 二叉树的顺序结构二叉树的顺序结构 /-二叉树的顺序存储表示二叉树的顺序存储表示- int MAX_TREE_SIZE 100Object treeMAX_TREE_SIZE存储方案存储方案： 用顺序存储结构存储一棵

25、二叉树时，必须首先对该树中每个用顺序存储结构存储一棵二叉树时，必须首先对该树中每个结点进行结点进行编号编号，树中各结点的编号应与等深度的满二叉树中对应，树中各结点的编号应与等深度的满二叉树中对应位置上结点的编号相同。位置上结点的编号相同。用一组连续的内存单元，按结点的用一组连续的内存单元，按结点的编号编号顺序依次存储二叉树的元素值。顺序依次存储二叉树的元素值。 三二叉树存贮结构三二叉树存贮结构265.2 二 叉 树例：例： 用一维数组用一维数组bt bt 存放一棵完全二叉树，将标号为存放一棵完全二叉树，将标号为 i i 的结点的的结点的数据元素存放在分量数据元素存放在分量 bti-1bti-1

26、中。存储位置隐含了树中的关系，树中的中。存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现的。例如，关系是通过完全二叉树的性质实现的。例如，bt5bt5（i=6)i=6)的双亲结点的双亲结点标号是标号是k=trunc(i/2)=3,k=trunc(i/2)=3,双亲结点所对应的数组分量双亲结点所对应的数组分量btk-1=bt2btk-1=bt2顺序结构图示顺序结构图示 A A F F E E D D C C B B1 12 23 34 45 56 6下标下标 0 1 2 3 4 5 6 7 m-10 1 2 3 4 5 6 7 m-1 A B C D E FA B C D E F编

27、号编号 1 2 3 4 5 6275.2 二 叉 树非完全二叉树的顺序结构非完全二叉树的顺序结构 按完全二叉树的形式补齐二叉树所缺少的那些结点，对二叉树结点编号按完全二叉树的形式补齐二叉树所缺少的那些结点，对二叉树结点编号, ,将二叉树原有的结点按编号存储到内存单元将二叉树原有的结点按编号存储到内存单元“相应相应”的位置上。但这种方式的位置上。但这种方式对于畸形二叉树，浪费较大空间。对于畸形二叉树，浪费较大空间。 A A F F G G E E D D C C B B8 81 16 67 72 24 45 53 31010 A A F F G G E E D D C C B B9 90 1 2

28、 3 4 5 6 7 8 9 10 m-10 1 2 3 4 5 6 7 8 9 10 m-1A B C D E 0 F 0 0 GA B C D E 0 F 0 0 G28讨论：讨论： 对于对于完全二叉树完全二叉树来说，二叉树中的结点的编号完全可以反映来说，二叉树中的结点的编号完全可以反映出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编出该二叉树中结点之间的逻辑关系，可将此类二叉树中结点的编号与数组下标建立一一对应关系，所以采用顺序存储结构较好。号与数组下标建立一一对应关系，所以采用顺序存储结构较好。 对于对于一般的二叉树一般的二叉树，则添加一些不存在的，则添加一些不存在的“空空”结

29、点，使之结点，使之成为一棵完全二叉树。将其每个结点与完全二叉树上的结点完全成为一棵完全二叉树。将其每个结点与完全二叉树上的结点完全对应，此时仍可用顺序存储结构表示这棵二叉树。可能造成空间对应，此时仍可用顺序存储结构表示这棵二叉树。可能造成空间浪费，最坏的情况是：深度为浪费，最坏的情况是：深度为k且只有且只有k个结点的单支树，需要长个结点的单支树，需要长为为2 2k k-1-1的数组空间。的数组空间。295.2 二 叉 树2 2 二叉链表二叉链表 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域二叉链表中每个结点包含三个域：数据域、左指针域、右指针域 A A F F E E D D C

30、C B Bclass Bnodeptint data; Bnodept lchild, rchlid;二叉链表图示 D D A A B B C C E E F F rchilddatalchild二叉链表结点二叉链表结点306.2 二 叉 树 A A F F E E D D C C B B3 3 三叉链表（便于找到结点的双亲）三叉链表（便于找到结点的双亲） 三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域右指针域class Bnodept int data; Bnodept lchild, rchild, pare

31、nt;ABDFECparentrchilddatalchild三叉链表结点31 5.3 5.3 二叉树的遍历二叉树的遍历 一一. . 二叉树的遍历方法二叉树的遍历方法 二二. . 遍历的递归算法遍历的递归算法 三三. . 遍历的非递归算法遍历的非递归算法325.3 二叉树的遍历遍历：遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。问一次。访问访问：含义很广，可以是对结点的各种处理：含义很广，可以是对结点的各种处理，如修改结点数据、输出，如修改结点数据、输出结点数据。结点数据。 遍历是各种数据结构最基本的操作，许多其他的操

32、作可以在遍历遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。基础上实现。 如何访问二叉树的每个结点，如何访问二叉树的每个结点， 而且每个结点仅被访问一次？而且每个结点仅被访问一次？335.3 二叉树的遍历二叉树的遍历方法二叉树的遍历方法 二叉树由二叉树由根根、左子树、左子树、右子树右子树三部分组成三部分组成 二叉树的遍历二叉树的遍历可以分解为：访问可以分解为：访问根根，遍历，遍历左子树左子树和和遍历遍历右子树右子树令：令：L L：遍历左子树：遍历左子树 T T：访问根结点访问根结点 R R：遍历右子树遍历右子树 约定先左后右约定先左后右, ,有三种遍历方法：有三种遍历方法：

33、 T T L L R R、L L T T R R、L L R R T T ，分别称为分别称为: : 先序遍历、中序遍历、后序遍历先序遍历、中序遍历、后序遍历 A A F F G G E E D D C C B B345.3 二叉树的遍历 先序遍历（先序遍历（T T L L R R） 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树）先序遍历右子树； 先序遍历序列：先序遍历序列：A,A,B,D,B,D,E E,G,G,C,FC,F A A F F G G E E D D C C B B例：先先序遍历右图所示的二

34、叉树序遍历右图所示的二叉树 （1 1）访问根结点）访问根结点A A （2 2）先序遍历左子树：）先序遍历左子树：即按即按 T T L L R R 的顺序遍历的顺序遍历左子树左子树 （3 3）先序遍历右子树：）先序遍历右子树：即按即按 T T L L R R 的顺序遍历的顺序遍历右子树右子树355.3 二叉树的遍历中序遍历（中序遍历（L L T T R R）若二叉树非空若二叉树非空（1 1）中序遍历左子树）中序遍历左子树（2 2）访问根结点）访问根结点（3 3）中序遍历右子树）中序遍历右子树 中序遍历序列：中序遍历序列： D,B,G,D,B,G,E E, ,A,A,C,FC,F A A F F

35、G G E E D D C C B B例：例：中序遍历右图所示的二叉树中序遍历右图所示的二叉树 （1 1）中序遍历左子树：即按）中序遍历左子树：即按 L L T T R R 的顺序遍历的顺序遍历左子树左子树 （2 2）访问根结点）访问根结点A A （3 3）中序遍历右子树：即按）中序遍历右子树：即按 L L T T R R 的顺序遍历的顺序遍历右子树右子树365.3 二叉树的遍历后序遍历（后序遍历（L L R R T T）若二叉树非空若二叉树非空（1 1）后序遍历左子树）后序遍历左子树（2 2）后序遍历右子树）后序遍历右子树（3 3）访问根结点）访问根结点 后序遍历序列：后序遍历序列： D,G

36、,D,G,E E,B,B,F,CF,C, ,A A例：后例：后序遍历右图所示的二叉树序遍历右图所示的二叉树 （1 1）后序遍历左子树：即按）后序遍历左子树：即按 L L R R T T 的顺序遍历的顺序遍历左子树左子树 （2 2）后序遍历右子树：即按）后序遍历右子树：即按 L L R R T T 的顺序遍历的顺序遍历右子树右子树 （3 3）访问根结点）访问根结点A A A A F F G G E E D D C C B B375.3 二叉树的遍历 - - e e d d c c b b f f a a + + * * / / - - 后序遍历序列：后序遍历序列：a,b,c,d,-,a,b,c,

37、d,-,* *,+,+,e,f,/,e,f,/,- - 中序遍历序列：中序遍历序列：a,+,b,a,+,b,* *,c,-,d,c,-,d,- -,e,/,f,e,/,f 先序遍历序列：先序遍历序列：- -, ,+,a,+,a,* *,b,-,c,d,b,-,c,d,/,e,f/,e,f例：先例：先序遍历、中序遍历、序遍历、中序遍历、后后序遍历下图所示的二叉树序遍历下图所示的二叉树385.3 二叉树的遍历 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；二二. . 遍历的递归算法遍历的递归算法

38、先序遍历（T T L L R R）的定义：上面先序遍历的定义等价于：上面先序遍历的定义等价于：若二叉树为空，结束若二叉树为空，结束 基本项基本项（也叫终止项）（也叫终止项）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；395.3 二叉树的遍历先序遍历递归算法先序遍历递归算法 void preorder (Bnodept root) if (root!=null) System.out.print(root.data)； preorder(root.lchild); preord

39、er(root.rchild); 先序序列为先序序列为 + * a b c / d e称为前缀表达式称为前缀表达式 a a + + * * / / / d d / - -rootroot e e b b c c a a* *(b-c)+d/e(b-c)+d/e405.3 二叉树的遍历2 中序遍历递归算法中序遍历递归算法 void inorder (Bnodept root) if (root!=null)inorder(root.lchild); System.out.printf( root.data)； inorder(root.rchild); 中序序列为中序序列为 a * b c+ d

40、 / e称为中缀表达式称为中缀表达式你能写出后序遍历递归算法了吧 a a + + * * / / / d d / - -rootroot e e b b c c a*(b-c)+d/e415.3 二叉树的遍历3 后序遍历递归算法后序遍历递归算法 void postorder (Bnodept root) if (root!=null)postorder(root.lchild); postorder(root.rchild); System.out.printf(root.data)； 后序序列为后序序列为 a b c * d e / + 称为后缀表达式称为后缀表达式 a a + + * *

41、/ / / d d / - -rootroot e e b b c c a a* *(b-c)+d/e(b-c)+d/e42二叉树的层次遍历 二叉树层次遍历：先访问根节点，再依次访问下层结点，二叉树层次遍历：先访问根节点，再依次访问下层结点，每层结点按从左至右的顺序访问，直至全部结点访问完每层结点按从左至右的顺序访问，直至全部结点访问完毕。毕。 其实现可以其实现可以借助队列借助队列来完成，算法如下：来完成，算法如下： 1.把根节点压入队列；把根节点压入队列； 2.如果队列非空，循环执行以下操作：如果队列非空，循环执行以下操作： 1.从队列中取出队头结点，访问该结点；从队列中取出队头结点，访问该

42、结点； 2.若该结点的左孩子结点非空，则将该结点的左孩子结点入队列；若该结点的左孩子结点非空，则将该结点的左孩子结点入队列； 3.若该结点的右孩子结点非空，则将该结点的右孩子结点入队列；若该结点的右孩子结点非空，则将该结点的右孩子结点入队列； 3.结束结束435.3 二叉树的遍历对二叉树的先序遍历对二叉树的先序遍历：先访问根结点，然后沿其左链一：先访问根结点，然后沿其左链一直访问下来，直到左链为空，最后再从左子树返回到根直访问下来，直到左链为空，最后再从左子树返回到根结点，最后访问其右子树。结点，最后访问其右子树。故需要借助于栈，将根结点进栈保存起来，将遍历其左故需要借助于栈，将根结点进栈保存

43、起来，将遍历其左子树的根结点进栈，。当左子树遍历完毕后，再子树的根结点进栈，。当左子树遍历完毕后，再从栈中取回根结点，再对其右子树进行遍历进栈操作。从栈中取回根结点，再对其右子树进行遍历进栈操作。三三. . 二叉树遍历的非递归算法二叉树遍历的非递归算法递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，效率不高，故有时考虑非递归算法。效率不高，故有时考虑非递归算法。 1 1 先序遍历（先序遍历（T L RT L R）的非递归算法。）的非递归算法。44先序遍历非递归算法步骤先序遍历非递归算法步骤: （1）初始化一个空栈）初始化一

44、个空栈 （2）当前指针指向根结点。将根结点指针进栈）当前指针指向根结点。将根结点指针进栈 （3）打印当前结点，当前指针指向其左孩子并进）打印当前结点，当前指针指向其左孩子并进栈，重复（栈，重复（3），直到左孩子为），直到左孩子为null （4）依次退栈，将当前指针指向其右孩子）依次退栈，将当前指针指向其右孩子 （5）若栈非空或当前指针非）若栈非空或当前指针非null，执行（，执行（3） （6）结束。）结束。455.3二叉树的遍历 d d b b a a * * - - / / c c + + e erootrootp pnode node 6 65 54 43 32 21 10 0toptop

45、System.out.print( root.data);+ +nodetop=p;top+;toptopp=p.lchild;p pSystem.out.print( root.data);* *nodetop=p;top+;toptopp=p.lchild;p pSystem.out.print( root.data) ;a anodetop=p;top+;toptopp=p.lchild;p pif (top0)top - -;toptopp=nodetop;p pp=p.rch;p ptoptopp pp pSystem.out.print( root.data) ;- -nodeto

46、p=p;top+;toptopp=p.lchild;p pb btoptopp ptop - -; p=nodetop; p=p.rch;toptopp ptoptopp pp pp pc cSystem.out.print( root.data)nodetop=p;top+;toptopp=p.lchild;p ptop - -;toptopp=nodetop;p pp=p.rchtoptopp pp p/ /toptopd dSystem.out. print(root.data);nodetop=p;top+; p=p.lchild;465.3 二叉树的遍历先序遍历的非递归算法先序遍历的

47、非递归算法void preorder2 (Bnodept root) Bnodept p, nodeMAX; int top=0; p=root; do while( p!=null) System.out.printf(p.data) ; nodetop=p;top+; p=p.lchild; if (top0) top - -; p=nodetop; p=p.rchild; while(top0|p!=null); d d b b e e a a * * - - / / c c + +475.4 遍历的应用 遍历是二叉树的基本操作：二叉树许多操作遍历是二叉树的基本操作：二叉树许多操作可在遍

48、历过程中完成，本节再例子举几个二叉可在遍历过程中完成，本节再例子举几个二叉树遍历应用实例。树遍历应用实例。485.4 遍历的应用例例1 编写编写 求二叉树的叶子结点个数的算法求二叉树的叶子结点个数的算法输入：输入：二叉树的二叉链表二叉树的二叉链表结果：结果：二叉树的叶子结点个数二叉树的叶子结点个数 F F D D A A B B C C E E rootrootint leaf(Bnodept root) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点为全局变量，用于累加二叉树的叶子结点 /的个数。的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的

49、个数本算法在先序遍历二叉树的过程中，统计叶子结点的个数 if(root=null) return 0;/空树时，空树时，n=0 else if(root.lchild= =null&root.rch= =null) return 1; /若若root所指点为叶子所指点为叶子, 则返回则返回1 return(leaf(root.lchild)+leaf(root.rchild); 与与先序遍历算法先序遍历算法比较一下比较一下！495.4 遍历的应用 例例2 建立二叉链表建立二叉链表 输入：输入：二叉树的先序序列二叉树的先序序列 结果：结果：二叉树的二叉链表二叉树的二叉链表 遍历操作访问二

50、叉树的每个结点，而且每个结点仅被访问一次。是遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用否可在利用遍历，建立遍历，建立二叉链表的所有结点并完成相应结点的链接？二叉链表的所有结点并完成相应结点的链接？基本思想：基本思想：输入（输入（在空子树处添加字符在空子树处添加字符* *的二叉树的）先序序列（设每个的二叉树的）先序序列（设每个元素是元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接相应结点的链接 A A F F E E D D C C B B*A B D A B D * * F F * *

51、 * * * * C E C E * * * * * *505.4 遍历的应用 输入输入（在空子树处添加空格字符的二叉树的）在空子树处添加空格字符的二叉树的）先序序列先序序列（设每个元素是（设每个元素是一个字一个字 符）符）按先序遍历的顺序，建立二叉链表按先序遍历的顺序，建立二叉链表，并将该二叉链表根结，并将该二叉链表根结点指针赋给点指针赋给root Bnodept create_tree(Bnodept root) char ch; Scanner sc=new Scanner(System.in); ch=(sc.nextLine().charAt(0); if (ch= = *) roo

52、t=null; / 若若ch= = * 则则root=null返回返回 else / 若若ch! = * root=new Bnodept() root.date = ch; / 建立（根）结点建立（根）结点 root.lchild=create_tree(root.lchild); /构造左子树链表，并将左子树根结点指针构造左子树链表，并将左子树根结点指针 赋给（根）结点赋给（根）结点 的左孩子域的左孩子域 root.rchild=create_tree(root.rchild); /构造右子树链表，并将右子树根结点指针构造右子树链表，并将右子树根结点指针 赋给（根）结点赋给（根）结点 的右

53、孩子域的右孩子域 return (root); 515.4 遍历的应用 D D A A B B C C E E F F T T 先序序列：先序序列：A B D F C EA B D F C E（在空子树处添加（在空子树处添加* *的二叉树的）先序序列：的二叉树的）先序序列： A B D F C E A B D F C E A A F F E E D D C C B B A A F F E E D D C C B B52 两点说明两点说明：1. 按先序次序输入二叉树中结点的值，用按先序次序输入二叉树中结点的值，用*表示空树，对每一表示空树，对每一个结点应当确定其左右子树的值（为空时必须用特定的空

54、字符占个结点应当确定其左右子树的值（为空时必须用特定的空字符占位），故执行此程序时，最好先在纸上画出你想建立的二叉树，每位），故执行此程序时，最好先在纸上画出你想建立的二叉树，每个结点的左右子树必须确定，若为空，则用特定字符标出，然后再个结点的左右子树必须确定，若为空，则用特定字符标出，然后再按先序输入这棵二叉树的字符序列；按先序输入这棵二叉树的字符序列；2. 为了简化程序的书写量，以及程序的清晰性，对结点的访问为了简化程序的书写量，以及程序的清晰性，对结点的访问以一条输出语句表示，若有更复杂的或多种访问，可以将结点的访以一条输出语句表示，若有更复杂的或多种访问，可以将结点的访问编写成函数，然

55、后通过函数的调用。读者若有兴趣，可自行编写。问编写成函数，然后通过函数的调用。读者若有兴趣，可自行编写。5.4 遍历的应用53 二叉排序树二叉排序树 或者为一棵空树，或为满足如下条件的二叉树或者为一棵空树，或为满足如下条件的二叉树 （1）若左子树非空，则左子树上所有结点的值均小于它）若左子树非空，则左子树上所有结点的值均小于它的根结点的值；的根结点的值； （2）若右子树非空，则右子树上所有结点的值均大于它）若右子树非空，则右子树上所有结点的值均大于它的根结点的值；的根结点的值； （3）它的左右子树也分别为二叉排序树。）它的左右子树也分别为二叉排序树。 建立过程示例建立过程示例v二叉树的建立二叉

56、树的建立2（建立二叉排序树（建立二叉排序树,P206）5.4 遍历的应用54输入序列输入序列45，12，37，3，53，100，24451253337100245.4 遍历的应用算法思想：算法思想： 设二叉排序树为设二叉排序树为b，新申请的结点为，新申请的结点为s。则则（1）若）若b是空树，将是空树，将s结点作为根结点；结点作为根结点；（2）若）若s.data等于等于b的根结点的数据域，的根结点的数据域，不作任何操作；不作任何操作；（3）若）若s.data小于小于b的根结点的数据域，的根结点的数据域，则将则将s插入到左子树中；插入到左子树中；（4）若）若s.data大于大于b的根结点的数据域，

57、的根结点的数据域，则将则将s插入到右子树中。插入到右子树中。55 void insert(Bnodept T,int x) if (T=null|T.data=x) return; /如果结点不存在或数据已存在如果结点不存在或数据已存在,返回返回 else if(xT.data) /将数据结点添加到左子树将数据结点添加到左子树 if (T.lchild=null) /左子树为空则创建左子树为空则创建Bnodept temp=new Bnodept();temp.data=x;temp.lchild=temp.rchild=null;T.lchild=temp;else insert(T.lch

58、ild,x); /否则递归调用否则递归调用 else /数据结点添加到右子树数据结点添加到右子树 if (T.rchild=null) /右子树为空则创建右子树为空则创建 Bnodept temp=new Bnodept();temp.data=x;temp.lchild=temp.rchild=null;T.rchild=temp;else insert(T.rchild,x); /否则递归调用否则递归调用 建立一棵二叉排序树建立一棵二叉排序树5.4 遍历的应用56 void CreateBiTree(Bnodept root) int x;Scanner sc=new Scanner(Sy

59、stem.in)x=sc.nextInt(); while (x!=-1)if(root=null) /如果根节点为空则创建根节点如果根节点为空则创建根节点 root =new Bnodept(); root.data=x; root.lchild=root.rchild=null;else insert(root,x); /否则插入排序数中否则插入排序数中 x=sc.nextInt(); 5.4 遍历的应用57小 结 1 1 二叉树：二叉树： 或为空树，或由根及两颗不相交的左子或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；树、右子树构成，并且左、右子树本身也

60、是二叉树； 2 2 二叉树即可以用顺序结构存储，也可用链式结构二叉树即可以用顺序结构存储，也可用链式结构存储；存储；3 3 遍历：按某种搜索路径访问二叉树的每个结点，每遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。个结点仅被访问一次。 二叉树的遍历可以分解为：访二叉树的遍历可以分解为：访问根，遍历问根，遍历左子树和左子树和遍历遍历右子树，本课程介绍了三种右子树，本课程介绍了三种遍历算法：遍历算法：先序遍历、中序遍历、后序遍历；先序遍历、中序遍历、后序遍历；58第五章 树和二叉树 5.5 5.5 线索二叉树线索二叉树 一.分析与设计分析与设计 二、线索二叉树上如何寻找结点的前驱和后继二、线索