《二叉树的存储与遍历.ppt》由会员分享，可在线阅读，更多相关《二叉树的存储与遍历.ppt（65页珍藏版）》请在金锄头文库上搜索。
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结点结构结点结构例例2：
7、对例：对例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特点特点: :先被遍历的结点的孩子先于后遍历先被遍历的结点的孩子先于后遍历的结点的孩子遍历的结点的孩子遍历。BACDEFGHBAC
11、DEFGH2、先上后下先上后下的按层次层次遍历 根据二叉树的结构，分为三部分：根据二叉树的结构，分为三部分：nL 左子树左子树nD 根结点根结点nR 右子树右子树 遍历二叉树的方法：遍历二叉树的方法：n先序遍历先序遍历 DLRn中序遍历中序遍历 LDRn后序遍历后序遍历 LRD 由于其中的左右子树也是二叉树，属于递归由于其中的左右子树也是二叉树，属于递归结构，所以常常借助递归算法实现。结构，所以常常借助递归算法实现。DLR3 3、先左后右先左后右的遍历算法的遍历算法n若二叉树为空，则空操作；若二叉树为空，则空操作；n否则，否则，p访问根结点；访问根结点；p先序先序遍历左子树；遍历左子树；p先序
12、先序遍历右子树。遍历右子树。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 ) ; /先序遍历右子树先序遍历右子树 递归算法描述递归算法描述 n若二叉树为空，则空操作；若二叉树为空，
13、则空操作；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) ; /输出根结点输出根结点 Inorder ( T - rchil
14、d ) ; /中序遍历右子中序遍历右子树树 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 ) ; /后序遍历左子树后序遍历左子树 Postorder ( T - r
15、child ) ; /后序遍历右子树后序遍历右子树 printf( T - data) ; /输出根结点输出根结点 递归算法描述递归算法描述 inorder(子树子树); printf();inorder(子树子树);ABCDEFT参数参数T是结点是结点(1)调调用用inorder(); printf();inorder(子树子树);参数参数T是结点是结点输出输出()调调用用inorder(); printf();inorder();参数参数T是结点是结点输出输出()返返回回()返返回回输出输出()调调用用参数参数T是结点是结点inorder(); printf();inorder(子树子树)
16、;输出输出()调调用用参数参数T是结点是结点inorder(子树子树); printf();inorder();参数参数T是结点是结点inorder(); printf();inorder();输出输出()调调用用()返返回回输出输出()返返回回()返返回回例例5：中序遍历递归调用过程：中序遍历递归调用过程算法分析：算法分析：以上遍历二叉树中的基以上遍历二叉树中的基本操作是本操作是“访问结点访问结点”，不论按哪一不论按哪一种次序进行遍历，对含有种次序进行遍历，对含有n n个结点的个结点的二叉树，其时间复杂度均为二叉树，其时间复杂度均为O(n)O(n)，所所需辅助空间为遍历过程中需辅助空间为遍历
17、过程中栈的最大容栈的最大容量量，即树的深度，最坏情况下为，即树的深度，最坏情况下为n n, ,则则空间复杂度也为空间复杂度也为O(nO(n) )。 思考：思考：1.1.先序先序序列和序列和中序中序序列相同的二叉树序列相同的二叉树? ? 2.2.中序中序序列和序列和后序后序序列相同的二叉树序列相同的二叉树? ? 3.3.先序先序序列和序列和后序后序序列相同的二叉树序列相同的二叉树? ?思考：思考： 1.1.先序先序序列和序列和中序中序序列相同的二叉树有：序列相同的二叉树有： 空二叉树空二叉树/ /任一结点均无左孩子的非空二叉树任一结点均无左孩子的非空二叉树 2.2.中序中序序列和序列和后序后序序
18、列相同的二叉树有：序列相同的二叉树有： 空二叉树空二叉树/ /任一结点均无右孩子的非空二叉树任一结点均无右孩子的非空二叉树 3.3.先序先序序列和序列和后序后序序列相同的二叉树有：序列相同的二叉树有：空二叉树空二叉树/ /只有一个结点只有一个结点1 1）统计二叉树中结点的个数）统计二叉树中结点的个数3 3）求二叉树的深度）求二叉树的深度4 4）建立二叉树的存储结构）建立二叉树的存储结构5 5）由给定序列确定二叉树）由给定序列确定二叉树2 2）统计二叉树中叶子结点的个数）统计二叉树中叶子结点的个数4. 遍历二叉树的应用遍历二叉树的应用1 1）统计二叉树中结点的个数）统计二叉树中结点的个数分析分析
19、结点的个数为：结点的个数为： 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 ( BiTree T) if ( T=0 )
20、 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(Depth(T-lchild), Depth(T-rchild); 空树空
21、树只含根结点的二叉树只含根结点的二叉树以字符以字符“ ”表示表示以字符串以字符串“A A ”表示表示4 4）建立二叉树）建立二叉树的存储结构的存储结构A分析：分析：以字符串的形式定义一棵二叉树以字符串的形式定义一棵二叉树: : 根根 左子树左子树 右子树右子树以下列字符串表示：以下列字符串表示：A(B(,C(,),D(, )一般的二叉树：一般的二叉树：ABCD例例1：A B C D E G F ADBCFEGA AB B C C D E G F 按按照照先先序序顺顺序序输输入入建建立立二二叉叉树树，用用空空格格代表空指针。代表空指针。 Status CreateBiTree(BiTree &T
22、) 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 何谓线索二叉树？何谓线索二叉树？o 线索链表的遍历算法线索链表的遍历算法o 如何建立线索链表？如何建立线
26、索链表？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 lchildltagdatartagrchild0 lchild 域指向左孩子1 lchild 域指向
27、结点的前驱ltag=0 rchild 域指向右孩子1 rchild 域指向结点的后继rtag=结点结构如下：结点结构如下：包含包含 “线索线索” 的存储结构，称作的存储结构，称作 “线索链线索链表表”。加上线索的二叉树称之为加上线索的二叉树称之为线索二叉树线索二叉树，对，对二叉树以某种次序遍历使其变为线索二叉二叉树以某种次序遍历使其变为线索二叉树的过程叫做树的过程叫做线索化线索化。中序线索二叉树NULLACFEDBNULLA00E 11C 01D 11F 11B 00NULLA中序线索链表中序线索链表3、如何建立线索链表？、如何建立线索链表？方方法：法：在遍历过程中修改空指针、在遍历过程中修改
28、空指针、思路：思路：先写出遍历序列，再画线索。先写出遍历序列，再画线索。步骤：步骤： 1 1）标出必要的空指针（前驱）标出必要的空指针（前驱左指针；后继左指针；后继右右 指针，要点：指针，要点：“不要多标，也不要少标不要多标，也不要少标”）。）。 2 2）写出对应的遍历序列（前序，中序或后序）。）写出对应的遍历序列（前序，中序或后序）。 3 3）对照遍历结果画线索。）对照遍历结果画线索。ABDEGCFHNULLNULL例例: : 画出下面二叉树的中序线索二叉树画出下面二叉树的中序线索二叉树中序遍历序列：中序遍历序列：D B E G A F H CD B E G A F H C前序线索树上找前驱
29、和后继找前驱：找前驱： 困难困难找后继找后继： 若结点有左孩子，则左孩子若结点有左孩子，则左孩子是后继；否则，是后继；否则，rchild指向后继。指向后继。中序线索树上找前驱和后继 中序的前驱和后继都往上指向祖先中序的前驱和后继都往上指向祖先找前驱：找前驱： 若左标记为若左标记为1，则，则lchild指向其前驱；否指向其前驱；否则，其前驱是其左子树上按中序遍历的最后则，其前驱是其左子树上按中序遍历的最后一个结点。一个结点。找后继找后继： 若右标记为若右标记为1，则，则rchild指向其后继；否指向其后继；否则，其后继是其右子树上按中序遍历的第一则，其后继是其右子树上按中序遍历的第一个结点。个结
30、点。后序线索树上找前驱和后继找前驱：找前驱： 若结点有右子孩子，则右孩子是若结点有右子孩子，则右孩子是其前驱；否则，其前驱；否则，lchild指向其前驱。指向其前驱。找后继找后继： 困难，需要知道其双亲。困难，需要知道其双亲。课堂总结课堂总结主要内容：主要内容：二叉链表存储结构；遍历二叉树的二叉链表存储结构；遍历二叉树的递归算法及其应用，包括：写遍历序列，统计递归算法及其应用，包括：写遍历序列，统计（叶）结点个数，二叉树的深度，根据给定序（叶）结点个数，二叉树的深度，根据给定序列画出二叉树等，线索二叉树。列画出二叉树等，线索二叉树。重点难点重点难点：遍历二叉树的递归算法及其应用遍历二叉树的递归算法及其应用。2.2.设二叉树的中序序列为设二叉树的中序序列为DBGEAFHC,DBGEAFHC,后序后序序列为序列为DGEBHFCADGEBHFCA，画出此二叉树。，画出此二叉树。1.1.请给出下面二叉树的先序序列，中序序请给出下面二叉树的先序序列，中序序列和后序序列。列和后序序列。作业作业ABCDEGHF
