二叉树的存储与遍历 (1)

1、 【学习目标【学习目标】 1.熟练熟练掌握掌握二叉链表二叉链表存储结构；存储结构； 2.熟练熟练掌握掌握遍历二叉树的递归遍历二叉树的递归算法，并能够实现二叉树的算法，并能够实现二叉树的其它其它 操作操作； 3.了解按层次遍历二叉树的算法，能够熟练写出给定二叉树的了解按层次遍历二叉树的算法，能够熟练写出给定二叉树的 各种遍历序列各种遍历序列，会根据给定的遍历序列，会根据给定的遍历序列画出二叉树画出二叉树。 4. 理解二叉树线索化的实质理解二叉树线索化的实质是建立结点与其在相应序列中的前是建立结点与其在相应序列中的前 驱或后继之间的直接联系。了解二叉树的线索化过程以及在中驱或后继之间的直接联系。了

2、解二叉树的线索化过程以及在中 序线索化树上找给定结点的前驱和后继的方法。序线索化树上找给定结点的前驱和后继的方法。能够熟练地画能够熟练地画 出给定二叉树的各种线索。出给定二叉树的各种线索。 【重点难点【重点难点】 遍历二叉树的递归算法及其应用遍历二叉树的递归算法及其应用 ，二叉树线索化，二叉树线索化 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构 6.3.1 6.3.1 遍历二叉树遍历二叉树 6.3.2 6.3.2 线索二叉树线索二叉树 【教学内容【教学内容】 【内容回顾【内容回顾】 6.1 6.1 树的定义和基本术语树的定义和基本术语 6.2 6.2 二叉树二叉树 -6.2.1 -

3、6.2.1 二叉树的定义二叉树的定义 -6.2.2 -6.2.2 二叉树的性质二叉树的性质 【课题导入【课题导入】 回顾线性表的存储方法回顾线性表的存储方法？ 顺序存储顺序存储 链式存储链式存储 #define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点号单元存储根结点 SqBiTree bt; 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构 1. 1. 顺序存储结构顺序存储结构 约定用约定用一组地址连续的一组地址连续的存储单元依次自上存储单元依

4、次自上 而下，自左至右存储而下，自左至右存储完全二叉树完全二叉树上的结点元素。上的结点元素。 例例1: 完全二叉树存储完全二叉树存储 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1 1 8 8 9 9 1010 4 4 5 5 2 2 6 6 7 7 3 3 例例2: 非完全二叉树存储非完全二叉树存储 A B C D E F A B D 0 C 0 E 0 0 0 0 0 0 F 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 5 1 14 3 7 注意：注意：1）对于一棵二叉树，若采用顺序存储）对于一棵二叉树，若采用顺序存储 时，对

5、完全二叉树，比较方便；对非完全二时，对完全二叉树，比较方便；对非完全二 叉树，将会浪费大量存储单元。叉树，将会浪费大量存储单元。 2 2）最坏的非完全二叉树是最坏的非完全二叉树是只有右分支只有右分支, ,设设 高度为高度为K K, ,则需占用则需占用2 2K K-1-1个存储单元个存储单元, ,而实而实 际只有际只有k k个元素个元素, ,实际只需实际只需k k个存储单元。个存储单元。 因此，对于因此，对于非完全非完全二叉树，不宜采用二叉树，不宜采用 顺序存储结构。顺序存储结构。 ? 顺序结构存储二叉树的优点顺序结构存储二叉树的优点 1 1）存储时，元素的）存储时，元素的位置位置( (下标下标

6、+1)+1)对应对应 其在完全二叉树中的序号。其在完全二叉树中的序号。 2 2）可快速方便地访问元素的）可快速方便地访问元素的双亲双亲和和左左 右孩子右孩子。 2 2、链式存储表示、链式存储表示 1 1）二叉链表）二叉链表 2 2）三叉链表）三叉链表 A D E B C F root lchild data rchild 结点结构结点结构 1) 1) 二叉链表二叉链表 A D EC B F 例例1： typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针

7、BiTNode, *BiTree; 类型类型定义定义 root 2 2）三叉链表）三叉链表 lchild data parent rchild 结点结构结点结构 例例2：对例：对例1 C A F E D B typedef struct TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 struct TriTNode *parent; /双亲指针双亲指针 TriTNode, *TriTree; 类型类型定义定义 例例3： 链式存储结构示例链式存储结构示例 A C FE D B

8、 A D BC EF A BC DEF 二叉链表二叉链表三叉链表三叉链表 注意：注意：对于一棵二叉树对于一棵二叉树, ,若采用二叉链若采用二叉链 表存表存储储时时, ,当二叉树为当二叉树为非完全二叉树非完全二叉树时时, ,比比 较方便较方便, ,若为若为完全二叉树完全二叉树时时, ,将会占用较多将会占用较多 存存储储单元单元( (存放地址的指针存放地址的指针) )。 若一棵二叉树有若一棵二叉树有n n个结点个结点, ,采用采用二叉链二叉链 表表作存作存储储结构时结构时, ,共有共有2n2n个指针域个指针域, ,其中其中只只 有有n-1n-1个个指针指向左右孩子指针指向左右孩子, ,其余其余n+

9、1n+1个指个指 针为空针为空。 ? 在二叉链表结构中的操作在二叉链表结构中的操作 o 查询元素？查询元素？ o 查询元素的后继？查询元素的后继？ o 查询元素的前驱查询元素的前驱？ 这种存储结构的特点是这种存储结构的特点是: 寻找孩子结点容易，双亲比较困难。寻找孩子结点容易，双亲比较困难。 6.3.1 6.3.1 遍历二叉树遍历二叉树 3 3、先左后右的遍历算法、先左后右的遍历算法 1 1、导入、导入 2 2、先上后下的按层次遍历、先上后下的按层次遍历 4 4、遍历二叉树的应用、遍历二叉树的应用 问题：问题：怎样在二叉树中查找具有某种特征的结点？怎样在二叉树中查找具有某种特征的结点？ 怎样对

10、二叉树中全部结点逐一进行某种处理？怎样对二叉树中全部结点逐一进行某种处理？ 1 1、导入、导入 遍历二叉树遍历二叉树：即如何按照某条搜索路径：即如何按照某条搜索路径巡访巡访二叉树二叉树 中每个结点，使得每个结点均被中每个结点，使得每个结点均被访问一次，而且仅访问一次，而且仅 被访问一次。被访问一次。 “访问访问”的含义可以很广，如：输出结点的信息，的含义可以很广，如：输出结点的信息， 对结点进行统一的操作等。对结点进行统一的操作等。 对对“二叉树二叉树”而言，可以有两而言，可以有两 条搜索路径：条搜索路径： 先上后下先上后下的按层次遍历； 先左先左（子树）后右后右（子树） 的遍历； 从第一层开

11、始，同一层从左到右。从第一层开始，同一层从左到右。 n 例例1：如右图：如右图 按层次遍历序列为：按层次遍历序列为： ABFCGDEH n 特点特点: :先被遍历的结点的孩子先于后遍先被遍历的结点的孩子先于后遍 历的结点的孩子遍历。历的结点的孩子遍历。 B A C DE F G H B A C DE F G H 2、先上后下先上后下的按层次层次遍历 根据二叉树的结构，分为三部分：根据二叉树的结构，分为三部分： n L 左子树左子树 n D 根结点根结点 n R 右子树右子树 遍历二叉树的方法：遍历二叉树的方法： n 先序遍历先序遍历 DLR n 中序遍历中序遍历 LDR n 后序遍历后序遍历

12、LRD 由于其中的左右子树也是二叉树，属于递归由于其中的左右子树也是二叉树，属于递归 结构，所以常常借助递归算法实现。结构，所以常常借助递归算法实现。 D L R 3 3、先左后右先左后右的遍历算法的遍历算法 n 若二叉树为空，则空操作；若二叉树为空，则空操作； n 否则，否则， p访问根结点；访问根结点； p先序先序遍历左子树；遍历左子树； p先序先序遍历右子树。遍历右子树。 D L R D L R 1）先序）先序遍历算法遍历算法 D L R A D L R D L R B D C D L R 先序先序遍历序列：遍历序列：A B D C 例例2: 先序遍历先序遍历 A D B C void

13、Preorder ( BiTree T ) if ( T ) /如果二叉树不为空如果二叉树不为空 printf( T - data) ; /输出根结点输出根结点 Preorder ( T - lchild ) ; /先序遍历左子树先序遍历左子树 Preorder ( T - rchild ) ; /先序遍历右子树先序遍历右子树 递归算法描述递归算法描述 n 若二叉树为空，则空操作；若二叉树为空，则空操作； n 否则，否则， p中序中序遍历左子树；遍历左子树； p访问根结点；访问根结点； p中序中序遍历右子树。遍历右子树。 D L R D L R 2）中序）中序遍历算法遍历算法 L D R B

14、L D R L D R A D C L D R 中序中序遍历序列：遍历序列：B D A C 例例3: 中序遍历中序遍历 A D B C 递归算法描述递归算法描述 void Inorder ( BiTree T ) if ( T ) /如果二叉树不为空如果二叉树不为空 Inorder ( T - lchild ) ; /中序遍历左子树中序遍历左子树 printf( T - data) ; /输出根结点输出根结点 Inorder ( T - rchild ) ; /中序遍历右子树中序遍历右子树 n 若二叉树为空，则空操作；若二叉树为空，则空操作； n 否则，否则， p后序后序遍历左子树；遍历左子树

15、； p后序后序遍历右子树。遍历右子树。 p访问根结点；访问根结点； D L R D L R 3）后序）后序遍历算法遍历算法 L R D L R D L R D A D C L R D 后序后序遍历序列：遍历序列：D B C A 例例4: 后序遍历后序遍历 B A D B C void Postorder ( BiTree T ) if ( T ) /如果二叉树不为空如果二叉树不为空 Postorder ( T - lchild ) ; /后序遍历左子树后序遍历左子树 Postorder ( T - rchild ) ; /后序遍历右子树后序遍历右子树 printf( T - data) ; /

16、输出根结点输出根结点 递归算法描述递归算法描述 inorder(子树子树); printf(); inorder(子树子树); A BC DE F T 参数参数T是结点是结点 (1)调用调用 inorder(); printf(); inorder(子树子树); 参数参数T是结点是结点 输出输出 ()调用调用 inorder(); printf(); inorder(); 参数参数T是结点是结点 输出输出 ()返回返回 ()返回返回 输出输出 ()调用调用 参数参数T是结点是结点 inorder(); printf(); inorder(子树子树); 输出输出 ()调用调用 参数参数T是结点是

17、结点 inorder(子树子树); printf(); inorder(); 参数参数T是结点是结点 inorder(); printf(); inorder(); 输出输出 ()调用调用 ()返回返回 输出输出 ()返回返回 ()返回返回 例例5：中序遍历递归调用过程：中序遍历递归调用过程 算法分析：算法分析：以上遍历二叉树中的基以上遍历二叉树中的基 本操作是本操作是“访问结点访问结点”，不论按哪不论按哪 一种次序进行遍历，对含有一种次序进行遍历，对含有n n个结点个结点 的二叉树，其时间复杂度均为的二叉树，其时间复杂度均为O(n)O(n)， 所需辅助空间为遍历过程中所需辅助空间为遍历过程中

18、栈的最栈的最 大容量大容量，即树的深度，最坏情况下，即树的深度，最坏情况下 为为n n, ,则空间复杂度也为则空间复杂度也为O(nO(n) )。 思考：思考： 1.1.先序先序序列和序列和中序中序序列相同的二叉树序列相同的二叉树? ? 2.2.中序中序序列和序列和后序后序序列相同的二叉树序列相同的二叉树? ? 3.3.先序先序序列和序列和后序后序序列相同的二叉树序列相同的二叉树? ? 思考：思考： 1.1.先序先序序列和序列和中序中序序列相同的二叉树有：序列相同的二叉树有： 空二叉树空二叉树/ /任一结点均无左孩子的非空二叉树任一结点均无左孩子的非空二叉树 2.2.中序中序序列和序列和后序后序

19、序列相同的二叉树有：序列相同的二叉树有： 空二叉树空二叉树/ /任一结点均无右孩子的非空二叉树任一结点均无右孩子的非空二叉树 3.3.先序先序序列和序列和后序后序序列相同的二叉树有：序列相同的二叉树有： 空二叉树空二叉树/ /只有一个结点只有一个结点 1 1）统计二叉树中结点的个数）统计二叉树中结点的个数 3 3）求二叉树的深度）求二叉树的深度 4 4）建立二叉树的存储结构）建立二叉树的存储结构 5 5）由给定序列确定二叉树）由给定序列确定二叉树 2 2）统计二叉树中叶子结点的个数）统计二叉树中叶子结点的个数 4. 遍历二叉树的应用遍历二叉树的应用 1 1）统计二叉树中结点的个数）统计二叉树中

20、结点的个数 分析分析 结点的个数为：结点的个数为： 0; 1; 1+L; 1+R; 1+L+R 简化：简化： 可合并成可合并成。 LLRR ? 算法：算法： int NodeCount ( BiTree T ) if (T =0 ) return 0; else return 1+NodeCount(T-lchild) +NodeCount(T-rchild); 2 2）统计二叉树中叶子结点的个数）统计二叉树中叶子结点的个数 分析分析 叶子结点的个数为：叶子结点的个数为： 0; 1; L; R; L+R 简化：简化：可合并成可合并成。 LLRR ? 算法：算法： int LeafCount (

21、 BiTree T) if ( T=0 ) return 0; else if ( T-lchild=0 else return LeafCount(T-lchild) +LeafCount(T-rchild); 3 3）求二叉树的深度）求二叉树的深度 分析分析 二叉树的深度为：二叉树的深度为： 0; 1; L+1; R+1; max(L,R)+1 简化：简化： 可合并成可合并成。 LLRR ? 算法：算法： int Depth(BiTree T ) if (T=0 ) return 0; else return 1+max(Depth(T-lchild), Depth(T-rchild);

22、空树空树 只含根结点的二叉树只含根结点的二叉树 以字符以字符“ “ ”表示表示 以字符串以字符串“A A ”表示表示 4 4）建立二叉树）建立二叉树的存储结构的存储结构 A 分析：分析：以字符串的形式定义一棵二叉树以字符串的形式定义一棵二叉树: : 根根 左子树左子树 右子树右子树 以下列字符串表示：以下列字符串表示： A(B(,C(,),D(, ) 一般的二叉树：一般的二叉树： A B C D 例例1：A B C D E G F A D B C FE G ABC D E G F 按照按照先序先序顺序输入顺序输入 建立二叉树，用建立二叉树，用空空 格格代表空指针。代表空指针。 Status C

23、reateBiTree(BiTree if (ch= ) T = NULL; else T=(BiTNode *)malloc(sizeof(BiTNode); if (!T) exit(OVERFLOW); T-data = ch; / 生成根结点生成根结点 CreateBiTree(T-lchild); / 构造左子树构造左子树 CreateBiTree(T-rchild); / 构造右子树构造右子树 return OK; / CreateBiTree 算法：算法： 先序先序 中序中序 中序中序 后序后序 都可以唯一的都可以唯一的 确定一棵二叉确定一棵二叉 树。树。 先序先序 后序后序 不

24、能唯一的确定不能唯一的确定 一棵二叉树。一棵二叉树。 A B A C B C 5 5）由给定序列确定二叉树）由给定序列确定二叉树 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，如果同时 已知二叉树的中序序列“cbdaegf”， 则会如何？ （1）由二叉树的先序和中序序列建二叉树）由二叉树的先序和中序序列建二叉树 o 分析：先序序列的分析：先序序列的第一个是根第一个是根，这是解题的，这是解题的 突破口。突破口。 o 步骤：步骤：先序序列的第一个是根先序序列的第一个是根 在中序在中序 序列中标出根，分成左右子树序列中标出根，分成左右子树 在先序序在先序序 列中标出左右子树列中标出

25、左右子树( (根据结点个数即可根据结点个数即可) ) 分别对左右子树的先序和中序序列重复以上分别对左右子树的先序和中序序列重复以上 步骤直至完成。步骤直至完成。 先序序列先序序列 中序序列中序序列左子树左子树 左子树左子树 右子树右子树 右子树右子树 根根 根根 a b c d e f g c b d a e g f 例例2:2: a a b b c c d d e e f f g g a b cd e f g 先序序列先序序列 中序序列中序序列 后序序列后序序列左子树左子树 右子树右子树 根根 中序序列中序序列左子树左子树右子树右子树根根 （2）由二叉树的中序和后序序列建二叉树）由二叉树的中

26、序和后序序列建二叉树 分析：后序序列的分析：后序序列的最后一个是根最后一个是根，这是解题的突，这是解题的突 破口。破口。 步骤：步骤：后序序列的最后一个是根后序序列的最后一个是根 在中序序在中序序 列中标出根，分成左右子树列中标出根，分成左右子树 在后序序列中标在后序序列中标 出左右子树出左右子树( (根据结点个数即可根据结点个数即可) ) 分别对左右分别对左右 子树的后序和中序序列重复以上步骤直至完成。子树的后序和中序序列重复以上步骤直至完成。 例例3: 设二叉树的中序序列为设二叉树的中序序列为BDCEAGHF， 后序序列为后序序列为DECBHGFA，画出此二叉树，画出此二叉树。 B A C

27、 DE F G H 6.3.2 6.3.2 线索二叉树线索二叉树 o 何谓线索二叉树？何谓线索二叉树？ o 线索链表的遍历算法线索链表的遍历算法 o 如何建立线索链表？如何建立线索链表？ 1、何谓线索二叉树？何谓线索二叉树？ 遍历二叉树的结果是，求得结点的一线性序遍历二叉树的结果是，求得结点的一线性序 列，对非线性结构进行线性化操作。列，对非线性结构进行线性化操作。 A B C D E F G HK 例如: 先序序列先序序列: A B C D E F G H K 中序序列中序序列: : B D C A H G K F E 后序序列后序序列: : D C B H K G F E A 指向该线性序

28、列中的“前驱”和 “后继” 的指针指针，称作“线索线索” A B C D E F G H K D C B E lchildltagdatartagrchild 0 lchild 域指向左孩子 1 lchild 域指向结点的前驱 ltag= 0 rchild 域指向右孩子 1 rchild 域指向结点的后继 rtag= 结点结构如下：结点结构如下： 包含包含 “线索线索” 的存储结构，称作的存储结构，称作 “线索链线索链 表表”。 加上线索的二叉树称之为加上线索的二叉树称之为线索二叉树线索二叉树，对，对 二叉树以某种次序遍历使其变为线索二叉二叉树以某种次序遍历使其变为线索二叉 树的过程叫做树的过程叫做线索化线索化。 中序线索二叉树 NULL A C FED B NULL A 00 E 11 C 01 D 11F 11 B 00 NULL A 中序线索链表中序线索链表 3、如何建立线索链表？、如何建立线索链表？ 方方法：法：在遍历过程中修改空指针、在遍历过程中修改空指针、 思路：思路：先写出遍历序列，再画线索。先写出遍历序列，再画线索。 步骤：步骤： 1 1）标出必要的空指针（前驱）标出必要的空指针（前驱左指针；后继左指针；后继右右 指针，要点：指针，要点：“不要多标，也不要少标不要多标，也不要少标”）。）。 2 2）写出对应的遍