二叉树的存储与遍历

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 -6.2.1 二叉树的定义

3、二叉树的定义 -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: 非完全二叉树存储非完全二叉树存储ABCDEF 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 142511437注意：注意：1）对于一棵二叉树，若采用顺序存储）对于一棵二叉树，若采用顺序存储时，对完全二叉树，比较方便；对非完全二时，对完全二叉树，比较方便；对非完全二叉树，

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

6、问元素的）可快速方便地访问元素的双亲双亲和和左左右孩子右孩子。2 2、链式存储表示、链式存储表示1 1）二叉链表）二叉链表2 2）三叉链表）三叉链表ADEBCFrootlchild data rchild结点结构结点结构1) 1) 二叉链表二叉链表ADECBF例例1：typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;类型类型定义定义root2 2）三叉链表）三叉链表lchild data parent rchild结

7、点结构结点结构例例2：对例：对例1 CA F E D B typedef struct TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 struct TriTNode *parent; /双亲指针双亲指针 TriTNode, *TriTree;类型类型定义定义例例3： 链式存储结构示例链式存储结构示例ACFEDBADBCEF A BCDEF 二叉链表二叉链表三叉链表三叉链表 注意：注意：对于一棵二叉树对于一棵二叉树, ,若采用二叉链若采用二叉链表存表存储储时时, ,当二叉树

8、为当二叉树为非完全二叉树非完全二叉树时时, ,比比较方便较方便, ,若为若为完全二叉树完全二叉树时时, ,将会占用较多将会占用较多存存储储单元单元( (存放地址的指针存放地址的指针) )。 若一棵二叉树有若一棵二叉树有n n个结点个结点, ,采用采用二叉链二叉链表表作存作存储储结构时结构时, ,共有共有2n2n个指针域个指针域, ,其中其中只只有有n-1n-1个个指针指向左右孩子指针指向左右孩子, ,其余其余n+1n+1个指个指针为空针为空。?在二叉链表结构中的操作在二叉链表结构中的操作o 查询元素？查询元素？o 查询元素的后继？查询元素的后继？o 查询元素的前驱查询元素的前驱？ 这种存储结构

9、的特点是这种存储结构的特点是: 寻找孩子结点容易，双亲比较困难。寻找孩子结点容易，双亲比较困难。6.3.1 6.3.1 遍历二叉树遍历二叉树3 3、先左后右的遍历算法、先左后右的遍历算法 1 1、导入、导入2 2、先上后下的按层次遍历、先上后下的按层次遍历4 4、遍历二叉树的应用、遍历二叉树的应用 问题：问题：怎样在二叉树中查找具有某种特征的结点？怎样在二叉树中查找具有某种特征的结点？ 怎样对二叉树中全部结点逐一进行某种处理？怎样对二叉树中全部结点逐一进行某种处理？1 1、导入、导入遍历二叉树遍历二叉树：即如何按照某条搜索路径：即如何按照某条搜索路径巡访巡访二叉树二叉树中每个结点，使得每个结点

10、均被中每个结点，使得每个结点均被访问一次，而且仅访问一次，而且仅被访问一次。被访问一次。“访问访问”的含义可以很广，如：输出结点的信息，的含义可以很广，如：输出结点的信息，对结点进行统一的操作等。对结点进行统一的操作等。 对对“二叉树二叉树”而言，可以有两而言，可以有两条搜索路径：条搜索路径：先上后下先上后下的按层次遍历；先左先左（子树）后右后右（子树）的遍历； 从第一层开始，同一层从左到右。从第一层开始，同一层从左到右。n 例例1：如右图：如右图按层次遍历序列为：按层次遍历序列为：ABFCGDEHn 特点特点: :先被遍历的结点的孩子先于后遍先被遍历的结点的孩子先于后遍历的结点的孩子遍历。历

11、的结点的孩子遍历。BACDEFGHBACDEFGH2、先上后下先上后下的按层次层次遍历 根据二叉树的结构，分为三部分：根据二叉树的结构，分为三部分：n L 左子树左子树n D 根结点根结点n R 右子树右子树 遍历二叉树的方法：遍历二叉树的方法：n 先序遍历先序遍历 DLRn 中序遍历中序遍历 LDRn 后序遍历后序遍历 LRD 由于其中的左右子树也是二叉树，属于递归由于其中的左右子树也是二叉树，属于递归结构，所以常常借助递归算法实现。结构，所以常常借助递归算法实现。DLR3 3、先左后右先左后右的遍历算法的遍历算法n 若二叉树为空，则空操作；若二叉树为空，则空操作；n 否则，否则，p访问根结

12、点；访问根结点；p先序先序遍历左子树；遍历左子树；p先序先序遍历右子树。遍历右子树。DLRDLR1）先序）先序遍历算法遍历算法D L RAD L RD L RBDCD L R先序先序遍历序列：遍历序列：A B D C例例2: 先序遍历先序遍历ADBCvoid Preorder ( BiTree T ) if ( T ) /如果二叉树不为空如果二叉树不为空 printf( T - data) ; /输出根结点输出根结点 Preorder ( T - lchild ) ; /先序遍历左子树先序遍历左子树 Preorder ( T - rchild ) ; /先序遍历右子树先序遍历右子树 递归算法描

13、述递归算法描述 n 若二叉树为空，则空操作；若二叉树为空，则空操作；n 否则，否则，p中序中序遍历左子树；遍历左子树；p访问根结点；访问根结点；p中序中序遍历右子树。遍历右子树。DLRDLR2）中序）中序遍历算法遍历算法L D RBL D RL D RADCL D R中序中序遍历序列：遍历序列：B D A C例例3: 中序遍历中序遍历ADBC递归算法描述递归算法描述 void Inorder ( BiTree T ) if ( T ) /如果二叉树不为空如果二叉树不为空 Inorder ( T - lchild ) ; /中序遍历左子树中序遍历左子树 printf( T - data) ; /

14、输出根结点输出根结点 Inorder ( T - rchild ) ; /中序遍历右子树中序遍历右子树 n 若二叉树为空，则空操作；若二叉树为空，则空操作；n 否则，否则，p后序后序遍历左子树；遍历左子树；p后序后序遍历右子树。遍历右子树。p访问根结点；访问根结点；DLRDLR3）后序）后序遍历算法遍历算法 L R DL R DL R DADCL R D后序后序遍历序列：遍历序列：D B C A例例4: 后序遍历后序遍历BADBCvoid Postorder ( BiTree T ) if ( T ) /如果二叉树不为空如果二叉树不为空 Postorder ( T - lchild ) ; /

15、后序遍历左子树后序遍历左子树 Postorder ( T - rchild ) ; /后序遍历右子树后序遍历右子树 printf( T - data) ; /输出根结点输出根结点 递归算法描述递归算法描述 inorder(子树子树); printf();inorder(子树子树);ABCDEFT参数参数T是结点是结点(1)调用调用inorder(); printf();inorder(子树子树);参数参数T是结点是结点输出输出()调用调用inorder(); printf();inorder();参数参数T是结点是结点输出输出()返回返回()返回返回输出输出()调用调用参数参数T是结点是结点i

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

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

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

19、用1 1）统计二叉树中结点的个数）统计二叉树中结点的个数分析分析结点的个数为：结点的个数为： 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

20、LeafCount ( BiTree T) if ( T=0 ) return 0; else if ( T-lchild=0 & T-rchild=0 ) return 1; 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(D

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

22、针。 Status CreateBiTree(BiTree &T) scanf(&ch); 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算法：算法：先序先序中序中序中序中序后序后序都可以唯一的都可以唯一的确

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

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

25、列的最后一个是根最后一个是根，这是解题的突，这是解题的突破口。破口。步骤：步骤：后序序列的最后一个是根后序序列的最后一个是根 在中序序在中序序列中标出根，分成左右子树列中标出根，分成左右子树 在后序序列中标在后序序列中标出左右子树出左右子树( (根据结点个数即可根据结点个数即可) ) 分别对左右分别对左右子树的后序和中序序列重复以上步骤直至完成。子树的后序和中序序列重复以上步骤直至完成。例例3: 设二叉树的中序序列为设二叉树的中序序列为BDCEAGHF，后序序列为后序序列为DECBHGFA，画出此二叉树，画出此二叉树。BACDEFGH6.3.2 6.3.2 线索二叉树线索二叉树o 何谓线索二叉

26、树？何谓线索二叉树？o 线索链表的遍历算法线索链表的遍历算法o 如何建立线索链表？如何建立线索链表？1、何谓线索二叉树？何谓线索二叉树？遍历二叉树的结果是，求得结点的一线性序遍历二叉树的结果是，求得结点的一线性序列，对非线性结构进行线性化操作。列，对非线性结构进行线性化操作。ABCDEFGHK例如:先序序列先序序列: 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指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”A B C D E F G H K D C B E lchil

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