第六章叉与二叉树

1、1 6.1 树的有关概念树的有关概念6.2 二叉树二叉树6.3 二叉树的遍历二叉树的遍历6.4 遍历的应用遍历的应用6.5 线索二叉树线索二叉树6.6 树和森林树和森林6.7 树及应用树及应用2 本章重点难点重点重点：(1)二叉树的定义、结构特点和性质；二叉树的定义、结构特点和性质；(2)ADT二二叉树的设计和实现，二叉树存储结构的特点，三种遍历叉树的设计和实现，二叉树存储结构的特点，三种遍历方式的递归和非递归算法。方式的递归和非递归算法。(3)二叉树的线索化过程和二叉树的线索化过程和算法；算法；(4)最优二叉树的特性及建立最优二叉树和哈夫最优二叉树的特性及建立最优二叉树和哈夫曼编码的方法。曼

2、编码的方法。难点难点：二叉树的线索化算法；设计解决与树或二叉树：二叉树的线索化算法；设计解决与树或二叉树相关的应用问题的有效算法。相关的应用问题的有效算法。 3 6.1 树的有关概念树的有关概念6.2 二叉树二叉树6.3 二叉树的遍历二叉树的遍历6.4 遍历的应用遍历的应用6.5 线索二叉树线索二叉树6.6 树和森林树和森林6.7 树及应用树及应用4 6.1 树的有关概念树的有关概念1. 树的概念树的概念2. 树的应用树的应用3. 树的表示树的表示4. 树的有关术语树的有关术语5 树形结构是一种重要的非线性结构。树是树形结构是一种重要的非线性结构。树是n个结点的有限集合，个结点的有限集合，在任

3、一棵非空树中：在任一棵非空树中：（1）有且仅有一个称为根的结点。）有且仅有一个称为根的结点。（2）其余结点可分为）其余结点可分为m个互不相交的集合，而且这些集合中的每个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。一集合都本身又是一棵树，称为根的子树。说明：说明：树是递归结构，在树的定义中又用到了树的概念树是递归结构，在树的定义中又用到了树的概念 J JI IA AC CB BD DH HG GF FE EK KL LM Mp 树的概念树的概念 6.1 树的有关概念树的有关概念6 p 树的概念树的概念 6.1 树的有关概念树的有关概念数据对象数据对象 D：D是具有相同

4、特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D为空集，则称为空树为空集，则称为空树 。 否则否则: (1) 在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root； (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互个互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为根root的子树。的子树。 数据关系数据关系 R：ADT Tree7 p 树的概念树的概念 6.1 树的有关概念树的有关概念基本操作基本操作 P：ADT Tree查查 找找

5、类类 插插 入入 类类删删 除除 类类 数据对象数据对象 D： 数据关系数据关系 R：8 p 树的基本操作树的基本操作P 6.1 树的有关概念树的有关概念 Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为

6、空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历9 p 树的基本操作树的基本操作P 6.1 树的有关概念树的有关概念插入类：插入类：InitTree(&T) / 初始化置空树初始化置空树 CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树10 p 树的基本

7、操作树的基本操作P 6.1 树的有关概念树的有关概念删除类：删除类： ClearTree(&T) / 将树清空将树清空 DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树11 T=A, B, C, D, E, F, G, H, I, J，K，L，MA是根，其余结点可以划分为是根，其余结点可以划分为3个个互不相交的集合互不相交的集合： T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J，M这些集合中的每一集合都本身又是一棵树，它们是这些

8、集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的概念树的概念 12 从逻辑结构看：从逻辑结构看：树中只有根结点没有前趋；其余结点有零个或多个后继；树中只有根结点没有前趋；其余结点有零个或多个后继；除根外，其余结点都有且仅一个前趋；都存在唯一条从根到该除根外，其余结点都有且仅一个前趋；都存在唯一条从根到该结点的路径；结点的路径；树是一种分枝结构树是一种分枝结构 （除了一个称为根的结点外）每个元素都有（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或

9、多个直接后继。且仅有一个直接前趋，有且仅有零个或多个直接后继。J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的概念树的概念 13 6.1 树的有关概念树的有关概念p 树的概念树的概念 线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点( (无前驱无前驱) )最后一个数据元素最后一个数据元素 ( (无后继无后继) )多个叶子结点多个叶子结点 ( (无后继无后继) ) 其它数据元素其它数据元素( (一个前驱、一个后继一个前驱、一个后继) ) 其它数据元素其它数据元素( (一个前驱

10、、多个后继一个前驱、多个后继) )14 家族族谱：设某家庭有家族族谱：设某家庭有13个成员个成员A、B、C、D、E、F、G、H、I、J，K，L，M他们之间的关系可下图所示的树表示：他们之间的关系可下图所示的树表示： 单位行政机构的组织关系单位行政机构的组织关系1）树可表示具有分枝结构关系的对象）树可表示具有分枝结构关系的对象J JI IA AC CB BD DH HG GF FE EK KL LM M例例例例6.1 树的有关概念树的有关概念p 树的应用树的应用 15 2）树是常用的数据组织形式）树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为了便有些应用中数据元素之间

11、并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。于管理和使用数据，将它们用树的形式来组织。C文件夹文件夹1 文件夹文件夹2 文件文件1 文件文件2文件夹文件夹11 文件夹文件夹12 文件文件11 文件文件12 计算机的文件系统计算机的文件系统 不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件是用树文件系统，所有的文件是用树的形式来组织的。的形式来组织的。例例6.1 树的有关概念树的有关概念p 树的应用树的应用 16 （1 1）树形表示法）树形表示法ABEKLFCGDHMJI（2 2）凹入表示法）凹入表示法J JI IA AC CB BD DH

12、 HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的表示树的表示 17 （3 3）嵌套集合表示法）嵌套集合表示法 （文氏图）（文氏图）AEDHJIKLMFGCBJ JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的表示树的表示 18 （4 4）广义表表示法）广义表表示法(A(A）第一层）第一层( (A(A(B, C, DB, C, D) ) 第二层第二层(A(A(B B( (E,FE,F), ), C C( (G G), ), D D( (H,I,JH,I,J) ) 第三层第三层(A(A(B B( (E

13、(E(K,LK,L),F),F), ), C C( (G G), ), D D( (H(H(M M),I,J),I,J) ) 第四层第四层J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的表示树的表示 19 结点层结点层：根结点的层定义为：根结点的层定义为1，其它依此类推；，其它依此类推；树的深度树的深度：树中最大的结点层：树中最大的结点层结点的度结点的度：结点子树的个数：结点子树的个数树的度树的度： 树中最大的结点度。树中最大的结点度。叶子结点叶子结点：也叫终端结点，是度为：也叫终端结点，是度为 0 的结点；的结点；树的度为

14、树的度为3树的深度为树的深度为4第第1层层第第3层层第第2层层第第4层层J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的有关术语树的有关术语 20 分枝结点：分枝结点：度不为度不为0的结点；的结点；有序树：有序树：子树有序的树，如：家族树；子树有序的树，如：家族树；无序树：无序树：不考虑子树的顺序；不考虑子树的顺序；森林：森林：互不相交的树集合；森林和树之间的联系是：一棵树去掉互不相交的树集合；森林和树之间的联系是：一棵树去掉根根 ，其子树构成一个森林；一个森林增加一个根结点成为树。，其子树构成一个森林；一个森林增加一个根结

15、点成为树。J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的有关术语树的有关术语 21 树是一种分枝结构的对象，在树的概念中，对每一树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，个结点孩子的个数没有限制，因此树的形态多种多样，本节我们主要讨论一种最简单的树本节我们主要讨论一种最简单的树二叉树。二叉树。6.2 二叉树二叉树 A A F F G G E E D D C C B B22 6.2.1 6.2.1 二叉树的概念二叉树的概念 6.2.2 6.2.2 二叉树的性质二叉树的性质 6

16、.2.3 6.2.3 二叉树的存储结构二叉树的存储结构6.2 二叉树二叉树23 6.2.1 二叉树的概念二叉树的概念说明：说明：二叉树中每个结点最多有两棵子树；即二叉树二叉树中每个结点最多有两棵子树；即二叉树每个结每个结点度小于等于点度小于等于2 2; ;左、右子树不能颠倒左、右子树不能颠倒有序树有序树; ;二叉树是二叉树是递归结构递归结构，在二叉树的定义中又用到了二叉，在二叉树的定义中又用到了二叉树的概念树的概念; ; A A F F G G E E D D C C B B二叉树二叉树或为空树，或由根及两颗不相交的左子树、或为空树，或由根及两颗不相交的左子树、右子树构成，并且右子树构成，并且

17、左、右子树本身也是二叉树左、右子树本身也是二叉树。24 A A F F G G E E D D C C B B(a) F F A A G G E E D D B B C C(b)二叉树是有左右之分的6.2.1 二叉树的概念二叉树的概念25 p 二叉树的基本形态二叉树的基本形态(a)空树(b)仅有根(c) 右子树空(d) 左子树空(e) 左、右子树均在6.2.1 二叉树的概念二叉树的概念26 应用举例 用二叉树表示计算表达式用二叉树表示计算表达式 a+b*(c-d)-e/f e e d d c c b b f f a a + + * * / / - - - -例例6.2.1 二叉树的概念二叉树的

18、概念27 6.2.1 6.2.1 二叉树的概念二叉树的概念 6.2.2 6.2.2 二叉树的性质二叉树的性质 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构6.2 二叉树二叉树28 证明：最多结点数为各层结点个数相加，即证明：最多结点数为各层结点个数相加，即 1+2+4+21+2+4+2k-1k-1=2=2k k-1-1性质性质2 2 深度为深度为k k的二叉树的二叉树有有个结点。个结点。性质性质1 1 在二叉树的第在二叉树的第i(i1)i(i1)层上层上有有个结点。个结点。 证明：用数学归纳法就可以证明。证明：用数学归纳法就可以证明。ABCDEFGIHJ k k层二叉树层二叉树6.

19、2.2 二叉树的性质二叉树的性质29 p 两种特殊的二叉树两种特殊的二叉树 A A G G F F E E D D C C B B(a)(a)K=3K=3的满二叉树的满二叉树满二叉树：满二叉树：如果深度为如果深度为k k的二叉树，有的二叉树，有2 2k k-1-1个结点则称为满二叉树；个结点则称为满二叉树；完全二叉树：二叉树中所含的二叉树中所含的 n n 个结点和满二叉树中编号为个结点和满二叉树中编号为1 1至至n n的的 结点结点一一对应一一对应。 A A E E D D C C B B(b)(b)(b)(b)完全二叉树 G G A A E E D D C C B B(c)(c)(c) (c

20、) 不是不是完全二叉树完全二叉树结论：满二叉树一定是完全二叉树，反之不一定6.2.2 二叉树的性质二叉树的性质30 证明：设所求完全二叉树的深度为证明：设所求完全二叉树的深度为k 由性质由性质2 2和完全二叉树的定义知：和完全二叉树的定义知： 2k-1 1-1 1n2k-1 1 性质性质3 3 具有具有n n个结点的个结点的完全二叉树的深度完全二叉树的深度为为 loglog2 2n n +1 +1 由此可以推出：由此可以推出：2k-1 1 n2k取对数得：取对数得： k-1 1log2nk由于由于k为整数，故有为整数，故有k-1 1= log2n 即：即： k= log2n +1 1 性质性质

21、2:2:深度为深度为k k的二叉树最多有的二叉树最多有2 2k k-1-1个结点个结点 A A E E D D C C B B E E D D D Dk层的最多结点数层的最多结点数k-1-1层的最多结点数层的最多结点数6.2.2 二叉树的性质二叉树的性质31 性质性质4 4 对任意二叉树对任意二叉树T T，如果度数为，如果度数为0 0结点数为结点数为n n0 0, ,度数为度数为1 1结点数为结点数为n n1 1, ,度数为度数为2 2结点数为结点数为n n2 2，则，则n n0 0=n=n2 2+1+1。 证明：二叉树证明：二叉树T T的的结点总数结点总数 n=nn=n0 0+n+n1 1+

22、n+n2 2 （1 1） 注意：注意：n1 1生成生成n1 1*1个节点，个节点，n2 2生成生成n2 2*2个节点，个节点， 根结点不由任何结点产生根结点不由任何结点产生由于分支结点是由度为由于分支结点是由度为1 1和度为和度为2 2的结点生成的的结点生成的 即即分支结点总数分支结点总数b=b=n1+2*n2 （3 3）二叉树的二叉树的分支结点总数分支结点总数 b=n-1 b=n-1 （2 2） 由由(1)(2)(3)(1)(2)(3)得得 求得：求得：n n0 0=n=n2 2+1+1ABCDEFGIHJ6.2.2 二叉树的性质二叉树的性质32 性质性质5:5:若对含若对含 n n 个结点

23、的完全二叉树从上到下且从左个结点的完全二叉树从上到下且从左至右进行至右进行 1 1 至至 n n 的编号，则对完全二叉树中任意一个的编号，则对完全二叉树中任意一个编号为编号为 i i 的结点的结点: :(1) (1) 若若 i=1i=1，则该结点是二叉树的根，无双亲，否则，则该结点是二叉树的根，无双亲，否则， 编号为编号为 i/2i/2 的结点为其的结点为其双亲双亲结点；结点；(3) (3) 若若 2i+1n2i+1n，则该结点无右孩子结点，否则，编号为，则该结点无右孩子结点，否则，编号为 2i+1 2i+1 的结点为其的结点为其右孩子右孩子结点。结点。(2) (2) 若若 2in2in，则该

24、结点无左孩子，否则，编号为，则该结点无左孩子，否则，编号为 2i2i的的 结点为其结点为其左孩子左孩子结点；结点； 2i+2 2i+2 i/2 2i+12i+1 2i2i i+1i+1 i i6.2.2 二叉树的性质二叉树的性质33 编号编号i=4i=4双亲为双亲为 i/2i/2 =2 =2左子树为左子树为2i=82i=8右子树为右子树为2i+1=92i+1=9i=1 只有根结点只有根结点编号编号i=5i=5双亲为双亲为 i/2i/2 =2 =2左子树为左子树为2i=10 2i=10 右子树为右子树为2i+1=112i+1=11i=8,i=8,2in2in无左子树无左子/p>

25、 10 11 12 13 146.2.2 二叉树的性质二叉树的性质34 6.2.1 二叉树的概念二叉树的概念 6.2.2 二叉树的性质二叉树的性质 6.2.3 二叉树的存储结构二叉树的存储结构6.2 二叉树二叉树35 p二叉树的链式存储表示二叉树的链式存储表示p 二叉树的顺序存储表示二叉树的顺序存储表示6.2.3 二叉树的存储结构二叉树的存储结构36 性质性质5:5:若对含若对含 n n 个结点的完全二叉树从上到下且从左至右个结点的完全二叉树从上到下且从左至右进行进行 1 1 至至 n n 的编号，则对完全二叉树中任意一个编号为的编号，则对完全二叉树中任意一个编号为 i i 的结点的结点: :

26、通过性质5把非线性结构轻易转化成了线性结构。 2i+2 2i+2 i/2 2i+12i+1 2i2i i+1i+1 i i6.2.3 二叉树的存储结构二叉树的存储结构37 (1)(1)完全（或满）二叉树完全（或满）二叉树ABCDEFGIHJ采用采用一维数组一维数组，按，按层序顺序层序顺序依依次存储二叉树的每一个结点。次存储二叉树的每一个结点。如下图所示：如下图所示：p 二叉树的顺序存储表示二叉树的顺序存储表示利用性质利用性质5 5实现实现线性结构线性结构和和非线性结构非线性结构的灵活转换。的灵活转换。 2i+2 2i+2 i/2 2i+12i+1 2i2i i+1i+1 i iA B C D

27、E F G1 2 3 4 5 6 7 8 9 10H IJ6.2.3 二叉树的存储结构二叉树的存储结构38 (2)(2)一般二叉树一般二叉树A B C 0E 0G1 2 3 4 5 6 7 8 9 1000J通过通过虚设虚设部分结点，使其变成相应的部分结点，使其变成相应的完全二叉树完全二叉树。ABCEGJABC0E0G00Jp 二叉树的顺序存储表示二叉树的顺序存储表示6.2.3 二叉树的存储结构二叉树的存储结构39 (3)(3)特殊的二叉树特殊的二叉树说明：说明：顺序存储方式对于畸形二叉树，浪费较大空间顺序存储方式对于畸形二叉树，浪费较大空间p 二叉树的顺序存储表示二叉树的顺序存储表示6.2.

28、3 二叉树的存储结构二叉树的存储结构ABCJ40 二叉链表存储：二叉链表存储：二叉链表中每个结点包含三个域：数据域、左指针域、右指针域二叉链表中每个结点包含三个域：数据域、左指针域、右指针域 typedef typedef Struct nodeStruct node DataType data; DataType data; Struct nodeStruct node * *lch,lch,* *rch;rch; BinTNode; BinTNode;lchrchdataC 语言的类型描述如下语言的类型描述如下: :p 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结构二

29、叉树的存储结构41 二叉链表图示二叉链表图示 D D A A C C E E F F B B root A A F F E E D D C C B B二叉树二叉树n 个结点的二叉树中，有多少个空链接域？p 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结构二叉树的存储结构42 性质性质6 6：n n 个结点的二叉树中，共有个结点的二叉树中，共有 n+1n+1 个空指针域。个空指针域。证：证：n n个结点总的指针域数个结点总的指针域数2n 2n 除了根结点外，其余除了根结点外，其余n-1n-1个结点个结点都是由指针域指出的结点；都是由指针域指出的结点； 所以，剩余的结点数即所以

30、，剩余的结点数即空指针域个数空指针域个数为：为：2n-2n-（n-1n-1）=n+1 =n+1 二叉链表的缺点二叉链表的缺点是很难找到结点的双亲是很难找到结点的双亲二叉链表图示二叉链表图示 D D A A C C E E F F B B rootp 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结构二叉树的存储结构43 三叉链表（三叉链表（带双亲指针的二叉链表带双亲指针的二叉链表）: :三叉链表中每个结点三叉链表中每个结点包含四个域：数据域、左指针域、右指针域、包含四个域：数据域、左指针域、右指针域、双亲指针域双亲指针域typedef typedef Struct nodeS

31、truct node DataType data; DataType data; Struct nodeStruct node * *lch,lch,* *rch,rch,* *parent;parent;lch data rch parent结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :p 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结构二叉树的存储结构44 A A F F E E D D C C B BA AB BD DF FE EC Crootlch data rch parentp 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结

32、构二叉树的存储结构45 二叉树的生成的递归算法二叉树的生成的递归算法bitree *creat() bitree *t; t=(bitree*)malloc(sizeof(bitree); t-data=x; t-lch=creat(); t-rch=creat(); return t;p 二叉树的生成二叉树的生成6.2.3 二叉树的存储结构二叉树的存储结构46 6.3.1 二叉树的遍历方法二叉树的遍历方法 6.3.2 遍历的递归算法遍历的递归算法 6.3.3 遍历的非递归算法遍历的非递归算法6.3 二叉树的遍历二叉树的遍历47 遍历遍历：按某种搜索路径：按某种搜索路径访问访问二叉树的每个结点

33、，而且每个二叉树的每个结点，而且每个结点仅被访问一次。结点仅被访问一次。访问访问：含义很广，可以是对结点的各种处理，如修改结点：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据等。数据、输出结点数据等。遍历遍历是各种数据结构最基本的操作，许多其它的操作可以是各种数据结构最基本的操作，许多其它的操作可以在遍历基础上实现。在遍历基础上实现。 6.3 二叉树的遍历二叉树的遍历48 “ “遍历遍历”是任何类型均有的操作：是任何类型均有的操作：对线性结构而言，只有一条搜索路径对线性结构而言，只有一条搜索路径( (因为每个结点均只因为每个结点均只有一个后继有一个后继) )；二叉树是非线性结构

34、，则二叉树是非线性结构，则存在如何遍历存在如何遍历即按什么样的即按什么样的搜索搜索路径路径遍历的问题。遍历的问题。 如何访问二叉树的每个结点，如何访问二叉树的每个结点， 而且每个结点仅被访问一次？而且每个结点仅被访问一次？6.3 二叉树的遍历二叉树的遍历49 对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：先上后下先上后下的按层次遍历；的按层次遍历；先左先左（子树）（子树）后右后右（子树）的遍历；（子树）的遍历；先右先右（子树）（子树）后左后左（子树）的遍历（子树）的遍历。6.3 二叉树的遍历方法二叉树的遍历方法50 二叉树由根、左子树、右子树三部分组成二叉树由根、左子

35、树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：令：L L：遍历左子树遍历左子树 T T：访问根结点访问根结点 R R：遍历右子树遍历右子树 有六种遍历方法：有六种遍历方法： T T L L R R，L L T T R R，L L R R T T， T T R R L L，R R T T L L，R R L L T T 约定先左后右约定先左后右, ,有三种遍历方法：有三种遍历方法： T T L L R R、L L T T R R、L L R R T T ，分别称分别称为为 先序遍历、中序遍历、后序遍历先序遍历

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

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

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

39、示p后序遍历（后序遍历（ L L T T R R ） A A F F G G E E D D C C B B例例6.3 二叉树的遍历方法二叉树的遍历方法54 d d e e c c b b f f a a + + * * / / - - - - 先序遍历、中序遍历、后序遍历下图所示的二叉树先序遍历、中序遍历、后序遍历下图所示的二叉树 后序后序 a,b,c,d,-,a,b,c,d,-,* *,+,+,e,f,/,e,f,/,- - 中序中序 a,+,b,a,+,b,* *,c,-,d,c,-,d, ,- -,e,/,f,e,/,f 先序先序 - -,+,+,a,a,* *,b,-,c,d,b,-

40、,c,d,/,e,f,/,e,f例例6.3 二叉树的遍历方法二叉树的遍历方法55 6.3 二叉树的遍历二叉树的遍历 6.3.1 二叉树的遍历算法二叉树的遍历算法 6.3.2 遍历的递归算法遍历的递归算法 6.3.3 遍历的非递归算法遍历的非递归算法56 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；上面先序遍历的定义等价于：上面先序遍历的定义等价于：若二叉树为空，结束若二叉树为空，结束 基本项基本项（也叫终止项）（也叫终止项）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访

41、问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树；）先序遍历右子树；6.3.2 遍历的递归算法遍历的递归算法p先序遍历（先序遍历（T T L L R R）的定义的定义57 void prev (BinTree T) if (T) visit(T-data)； prev(T-lch); prev(T-rch); 先序序列为先序序列为 + * a b c / d e称为前缀表达式称为前缀表达式 e e a a + + * * / / / d d / - -T T b b c c a a* *(b-c)+d/e(b-c)+d/e6.3.2 遍历的递归算法遍历的递归算

42、法p先序遍历递归算法先序遍历递归算法58 void Mid (BinTree T) if (T) Mid(T-lch); visit( T-data)； Mid(T-rch); 中序序列为中序序列为 a * b c+ d / e称为中缀表达式称为中缀表达式a a* *(b-c)+d/e(b-c)+d/e e e a a + + * * / / / d d / - -T T b b c c 6.3.2 遍历的递归算法遍历的递归算法p中序遍历递归算法中序遍历递归算法59 void Post(BinTree T) if (T) Post(T-lch); Post(T-rch); visti( T-d

43、ata)； 后序序列为后序序列为 a b c * d e / + 称为后缀表达式称为后缀表达式a a* *(b-c)+d/e(b-c)+d/e e e a a + + * * / / / d d / - -T T b b c c 6.3.2 遍历的递归算法遍历的递归算法p后序遍历递归算法后序遍历递归算法60 6.3 二叉树的遍历二叉树的遍历 6.3.1 二叉树的遍历算法二叉树的遍历算法 6.3.2 遍历的递归算法遍历的递归算法 6.3.3 遍历的非递归算法遍历的非递归算法61 对每个结点，在访问完后，沿其左链一直访问下来，直到左链为空对每个结点，在访问完后，沿其左链一直访问下来，直到左链为空，

44、这时，所有已被访问过的结点进栈。然后结点出栈，对于每个出，这时，所有已被访问过的结点进栈。然后结点出栈，对于每个出栈结点，即表示该结点和其左子树已被访问结束，应该访问该结点栈结点，即表示该结点和其左子树已被访问结束，应该访问该结点的右子树。的右子树。（1 1）当前指针指向根结点。）当前指针指向根结点。（2 2）打印当前结点，当前指针指向其左孩子并进栈，重复（）打印当前结点，当前指针指向其左孩子并进栈，重复（2 2），），直到左孩子为直到左孩子为NULLNULL；（3 3）依次退栈，将当前指针指向右孩子；）依次退栈，将当前指针指向右孩子；（4 4）若栈非空或当前指针非）若栈非空或当前指针非NUL

45、LNULL，执行（执行（2 2）；否则结束。）；否则结束。递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，效率不高，故有时考虑非递归算法。效率不高，故有时考虑非递归算法。6.3.3 遍历的非递归算法遍历的非递归算法1 先序遍历（先序遍历（T L R）的非递归算法的非递归算法62 void prev (NODE *root) NODE *p, *nodeMAX; int top=0; p=root; do while( p!=NULL) visit(t-data); nodetop=p;top+; p=p-lch; if (

46、top0) top - -; p=nodetop; p=p-rch; while(top0|p!=NULL); d d b b e e a a * * - - / / c c + +p 先序遍历的非递归算法先序遍历的非递归算法6.3.3 遍历的非递归算法遍历的非递归算法63 d d b b a a * * - - / / c c + + e erootrootp pnode toptopprintf(“%c,”, root-data);+ +nodetop=p;top+;toptopp=p-lch;p p* *toptopp pa atoptopp pif (top0)top - -;p=no

47、detop;p=p-rch;p p- -p pb bp ptop - -; p=nodetop; p=p-rch;p pp pp pc cp pp pp p/ /top+;d d6 65 54 43 32 21 10 0p pp p6.3.3 遍历的非递归算法遍历的非递归算法64 BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lch ) Push(S, T); T = T-lch; return T; d d b b e e a a * * - - / / c c + +p 中序遍历的非递归算法中序遍

48、历的非递归算法6.3.3 遍历的非递归算法遍历的非递归算法65 p 中序遍历的非递归算法中序遍历的非递归算法6.3.3 遍历的非递归算法遍历的非递归算法void Inorder_I(BiTree T, void (void Inorder_I(BiTree T, void (* *visit)visit) (TelemType& e) (TelemType& e) Stack Stack * *S;S; t = t = GoFarLeftGoFarLeft(T, S);(T, S); / / 找到最左下的结点找到最左下的结点 while(t)while(t) visit(t-d

49、ata);visit(t-data); if (t-rch) if (t-rch) t = t = GoFarLeft(t-rch, S); GoFarLeft(t-rch, S); else if ( !StackEmpty(S ) else if ( !StackEmpty(S ) / / 栈不空时退栈栈不空时退栈 t = Pop(S);t = Pop(S); else t = NULL; else t = NULL; / 栈空表明遍历结束栈空表明遍历结束 / while / while/ Inorder_I / Inorder_I 66 6.4 遍历的应用遍历的应用 遍历是二叉树的基本操

50、作：二叉树许多操遍历是二叉树的基本操作：二叉树许多操作可在遍历过程中完成，本节再举几个二叉树作可在遍历过程中完成，本节再举几个二叉树遍历应用实例。遍历应用实例。67 6.4.1 遍历的基本应用遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价二叉树的相似与等价6.4 遍历的应用遍历的应用68 求二叉树的叶子数。求二叉树的叶子数。算法思想：采用任何遍历方法，遍历时判断访问的结点是不是叶子，算法思想：采用任何遍历方法，遍历时判断访问的结点是不是叶子，若是则叶子数加若是则叶子数加1 1。int countleaf(bitree t ,

51、int num) if(t!=NULL) if(t-lch=NULL) &(t- rch)=NULL) num+; num=countleaf(t-lch,num); num=countleaf(t-rch,num); return num;例例6.4.1 遍历的基本应用遍历的基本应用69 求二叉树的深度求二叉树的深度算法思想：从第一层的根结点开始往下递推可得算法思想：从第一层的根结点开始往下递推可得到。使用二叉树的前序或后序遍历的递归或非递归算法都可求得。下到。使用二叉树的前序或后序遍历的递归或非递归算法都可求得。下面给出后序遍历求二叉树深度的递归算法面给出后序遍历求二叉树深度的递归

52、算法：Int treedepth(bitree *t) int h,lh,rh; if(t=NULL) h=0; else lh=treedepth(t-lch); rh=treedepth(t-rch); if(lh=rh) h=lh+1; else h=rh+1; return h; 例例6.4.1 遍历的基本应用遍历的基本应用70 6.4.1 遍历的基本应用遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价二叉树的相似与等价6.4. 遍历的应用遍历的应用71 问题：问题：给定一个遍历序列，能否唯一确定一棵二给定一个遍历序列

53、，能否唯一确定一棵二叉树？例如：先序序列为叉树？例如：先序序列为ABCD,ABCD,其二叉树的结构是什么？其二叉树的结构是什么？答案是答案是不唯一不唯一6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 A A C C B B D D A A D D C C B B A A C C D D B Bp二叉树的遍历与存储结构之间的转化二叉树的遍历与存储结构之间的转化72 p构造二叉树构造二叉树 给定某两种遍历序列能否唯一确定一棵二叉树？给定某两种遍历序列能否唯一确定一棵二叉树？ 给定中序和后序给定中序和后序 给定中序和前序给定中序和前序 给定先序和后序给定先序和后序不能不能唯一确定

54、一棵二叉树唯一确定一棵二叉树唯一确定一棵二叉树唯一确定一棵二叉树唯一确定一棵二叉树唯一确定一棵二叉树关键关键（1 1）确定二叉树的根结点；）确定二叉树的根结点； （2 2）结点的左右次序。）结点的左右次序。6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用73 给定二叉树先序和中序遍历序列，如何构造二叉树？给定二叉树先序和中序遍历序列，如何构造二叉树？ 先序：先序：1 2 4 6 3 5 7 81 2 4 6 3 5 7 8 中序：中序：2 6 4 1 3 7 5 82 6 4 1 3 7 5 81前前 246中中264前前3578中中3758例例左左2前前 46中中64右右4

55、61前前3578中中3758246p构造二叉树构造二叉树6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用74 后序遍历序列：a,b,c,d,-,a,b,c,d,-,* *,+,e,f,/,-,+,e,f,/,-根据给定的遍历次序构造二叉树根据给定的遍历次序构造二叉树中序遍历序列：中序遍历序列：a,+,b,a,+,b,* *,c,-,d,-,e,/,f,c,-,d,-,e,/,f作业作业p构造二叉树构造二叉树6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用75 e e d d c c b b f f a a + + * * / / - - - -先序先序:-,

56、+,a,:-,+,a,* *,b,-,c,d,b,-,c,d,/,e,f,/,e,fp构造二叉树构造二叉树6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用76 结论：结论：p“遍历遍历”是二叉树各种操作的基础；是二叉树各种操作的基础；p可以在遍历过程中对结点进行各种操作，可以在遍历过程中对结点进行各种操作，对于一棵已知树可求结点的双亲；对于一棵已知树可求结点的双亲；求结点的孩子结点；求结点的孩子结点；判定结点所在层次；判定结点所在层次；树的深度；树的深度；生成二叉树生成二叉树6.3.26.3.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 77 6.4 遍历的应用

57、遍历的应用 6.4.1 遍历的基本应用遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价二叉树的相似与等价78 p二叉树的相似与等价的含义二叉树的相似与等价的含义两株二叉树具有两株二叉树具有相同结构相同结构指：指： （1）它们都是空的）它们都是空的 ； （2）它们都是非空的，且左右子树分别具有相同结构。）它们都是非空的，且左右子树分别具有相同结构。 “形状形状”相相同同6.4.3 二叉树的相似与等价二叉树的相似与等价79 p判断两株二叉树是否等价判断两株二叉树是否等价int EQUAL( t1 , t2 )BTREE t1 ,

58、t2 ; int x ; x = 0 ; if ( ISEMPTY(t1) & ISEMPTY(t2) ) x = 1 ; else if ( !ISEMPTY( t1 ) & ! ISEMPTY( t2) ) if ( DATA( t1 ) = DATA( t2 ) ) if ( EQUAL( LCHILD( t1 ) , LCHILD( t2 ) ) ) x= EQUAL( RCHILD( t1) , RCHILD( t2) ) return( x ) ; /* EQUAL */6.4.3 二叉树的相似与等价二叉树的相似与等价80 p二叉树的复制二叉树的复制BTREE CO

59、PY( BTREE oldtree ) BTREE temp ; if ( oldtree != NULL ) temp = new Node ; temp - lch = COPY( oldtree-lch ) ; temp - rch = COPY( oldtree-rch ) ; temp - data = oldtree-data ; return ( temp ); return ( NULL ) ; 6.4.3 二叉树的相似与等价二叉树的相似与等价81 6.5 线索二叉树线索二叉树 6.5.1 线索二叉树的表示线索二叉树的表示 6.5.2 二叉树的线索化二叉树的线索化 6.5.3

60、线索二叉树的遍历线索二叉树的遍历82 6.5.1 线索二叉树的表示线索二叉树的表示 6.5.2 二叉树的线索化二叉树的线索化 6.5.3 线索二叉树的遍历线索二叉树的遍历6.5 线索二叉树线索二叉树83 6.5 线索二叉树线索二叉树二叉链表是一种单向链接结构二叉链表是一种单向链接结构，从一个结点出发，沿着指，从一个结点出发，沿着指针走向只能到达其子孙结点，却无法返回其祖先结点。针走向只能到达其子孙结点，却无法返回其祖先结点。正像线性链表可以从单向链表发展到双向链表一样，正像线性链表可以从单向链表发展到双向链表一样，二叉二叉链表也可以采用双向链表链表也可以采用双向链表。遍历二叉树遍历二叉树就是按一定的规则将二叉树中的结点排列成一就是按一定的规则将二叉树中的结点排列成一个线性序列，即个线性