二叉树的存储与遍历.ppt

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

2、定义和基本术语 6.2 二叉树 -6.2.1 二叉树的定义 -6.2.2 二叉树的性质,【课题导入】,回顾线性表的存储方法？,顺序存储 链式存储,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 SqBiTree bt;,6.2.3 二叉树的存储结构,1. 顺序存储结构 约定用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素。,例1: 完全二叉树存储,例2: 非完全二叉树存储,A,B,C,D,E,F,A B D 0 C 0 E 0 0 0 0

3、 0 0 F,1 2 3 4 5 6 7 8 9 10 11 12 13 14,2,5,1,14,3,7,注意：1）对于一棵二叉树，若采用顺序存储时，对完全二叉树，比较方便；对非完全二叉树，将会浪费大量存储单元。,2）最坏的非完全二叉树是只有右分支,设高度为K,则需占用2K-1个存储单元,而实际只有k个元素,实际只需k个存储单元。,因此，对于非完全二叉树，不宜采用顺序存储结构。,?,顺序结构存储二叉树的优点,1）存储时，元素的位置(下标+1)对应其在完全二叉树中的序号。 2）可快速方便地访问元素的双亲和左右孩子。,2、链式存储表示,1）二叉链表,2）三叉链表,A,D,E,B,C,F,root,

4、lchild data rchild,结点结构,1) 二叉链表,例1：,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,类型定义,root,2）三叉链表,lchild data parent rchild,结点结构,例2：对例1,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNo

5、de *parent; /双亲指针 TriTNode, *TriTree;,类型定义,例3： 链式存储结构示例,二叉链表,三叉链表,注意：对于一棵二叉树,若采用二叉链表存储时,当二叉树为非完全二叉树时,比较方便,若为完全二叉树时,将会占用较多存储单元(存放地址的指针)。 若一棵二叉树有n个结点,采用二叉链表作存储结构时,共有2n个指针域,其中只有n-1个指针指向左右孩子,其余n+1个指针为空。,?,?,在二叉链表结构中的操作,查询元素？ 查询元素的后继？ 查询元素的前驱？,这种存储结构的特点是: 寻找孩子结点容易，双亲比较困难。,6.3.1 遍历二叉树,3、先左后右的遍历算法,1、导入,2、先

6、上后下的按层次遍历,4、遍历二叉树的应用,问题：怎样在二叉树中查找具有某种特征的结点？ 怎样对二叉树中全部结点逐一进行某种处理？,1、导入,遍历二叉树：即如何按照某条搜索路径巡访二叉树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结点的信息，对结点进行统一的操作等。,对“二叉树”而言，可以有两条搜索路径：,先上后下的按层次遍历； 先左（子树）后右（子树）的遍历；,从第一层开始，同一层从左到右。 例1：如右图 按层次遍历序列为： ABFCGDEH 特点:先被遍历的结点的孩子先于后遍历的结点的孩子遍历。,B,A,C,D,E,F,G,H,2、先上后下的按层

7、次遍历,根据二叉树的结构，分为三部分： L 左子树 D 根结点 R 右子树 遍历二叉树的方法： 先序遍历 DLR 中序遍历 LDR 后序遍历 LRD 由于其中的左右子树也是二叉树，属于递归结构，所以常常借助递归算法实现。,3、先左后右的遍历算法,若二叉树为空，则空操作； 否则， 访问根结点； 先序遍历左子树； 先序遍历右子树。,D,L,R,1）先序遍历算法,D L R,D L R,D L R,D L R,先序遍历序列：A B D C,例2: 先序遍历,void Preorder ( BiTree T ) if ( T ) /如果二叉树不为空 printf( T - data) ; /输出根结点

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

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

10、树); printf(); inorder(子树);,参数T是结点,inorder(); printf(); inorder(子树);,参数T是结点,输出,inorder(); printf(); inorder();,参数T是结点,输出,()返回,()返回,输出,参数T是结点,inorder(); printf(); inorder(子树);,输出,参数T是结点,inorder(子树); printf(); inorder();,参数T是结点,inorder(); printf(); inorder();,输出,()调用,()返回,输出,()返回,()返回,例5：中序遍历递归调用过程,算法分

11、析：以上遍历二叉树中的基本操作是“访问结点”，不论按哪一种次序进行遍历，对含有n个结点的二叉树，其时间复杂度均为O(n)，所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n,则空间复杂度也为O(n)。,思考： 1.先序序列和中序序列相同的二叉树? 2.中序序列和后序序列相同的二叉树? 3.先序序列和后序序列相同的二叉树?,思考： 1.先序序列和中序序列相同的二叉树有： 空二叉树/任一结点均无左孩子的非空二叉树 2.中序序列和后序序列相同的二叉树有： 空二叉树/任一结点均无右孩子的非空二叉树 3.先序序列和后序序列相同的二叉树有： 空二叉树/只有一个结点,1）统计二叉树中结点的个数

12、,3）求二叉树的深度,4）建立二叉树的存储结构,5）由给定序列确定二叉树,2）统计二叉树中叶子结点的个数,4. 遍历二叉树的应用,1）统计二叉树中结点的个数,分析,结点的个数为： 0; 1; 1+L; 1+R; 1+L+R,简化： 可合并成。,?,?,?,?,?,算法： int NodeCount ( BiTree T ) if (T =0 ) return 0; else return 1+NodeCount(T-lchild) +NodeCount(T-rchild); ,2）统计二叉树中叶子结点的个数,分析,叶子结点的个数为： 0; 1; L; R; L+R,简化：可合并成。,?,?,?

13、,?,?,算法： int LeafCount ( BiTree T) if ( T=0 ) return 0; else if ( T-lchild=0 ,3）求二叉树的深度,分析,二叉树的深度为： 0; 1; L+1; R+1; max(L,R)+1,简化： 可合并成。,?,?,?,?,?,算法： int Depth(BiTree T ) if (T=0 ) return 0; else return 1+max(Depth(T-lchild), Depth(T-rchild); ,空树,只含根结点的二叉树,以字符“ ”表示,以字符串“A ”表示,4）建立二叉树的存储结构,分析：以字符串的形

14、式定义一棵二叉树: 根 左子树 右子树,以下列字符串表示：,A(B(,C(,),D(, ),一般的二叉树：,例1：A B C D E G F ,A,D,B,C,F,E,G,A,B,C,D,E,G,F,按照先序顺序输入建立二叉树，用空格代表空指针。,Status CreateBiTree(BiTree / CreateBiTree,算法：,先序 中序 中序 后序,都可以唯一的确定一棵二叉树。,先序 后序,不能唯一的确定一棵二叉树。,5）由给定序列确定二叉树,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,（1）由二叉树的

15、先序和中序序列建二叉树,分析：先序序列的第一个是根，这是解题的突破口。 步骤：先序序列的第一个是根 在中序序列中标出根，分成左右子树 在先序序列中标出左右子树(根据结点个数即可) 分别对左右子树的先序和中序序列重复以上步骤直至完成。,先序序列,中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,例2:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,（2）由二叉树的中序和后序序列建二叉树,分析：后序序列的最后一个是根，这是解题的突破口。 步骤：后序序列的最后一个是根 在中序序列中标出根，

16、分成左右子树 在后序序列中标出左右子树(根据结点个数即可) 分别对左右子树的后序和中序序列重复以上步骤直至完成。,例3: 设二叉树的中序序列为BDCEAGHF，后序序列为DECBHGFA，画出此二叉树。,6.3.2 线索二叉树,何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？,1、何谓线索二叉树？,遍历二叉树的结果是，求得结点的一线性序列，对非线性结构进行线性化操作。,A,B,C,D,E,F,G,H,K,例如:,先序序列: 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,指向该线性序列中的“前驱”和 “

17、后继” 的指针，称作“线索”,A B C D E F G H K, D ,C , B,E ,0 lchild 域指向左孩子 1 lchild 域指向结点的前驱,ltag=,0 rchild 域指向右孩子 1 rchild 域指向结点的后继,rtag=,结点结构如下：,包含 “线索” 的存储结构，称作 “线索链表”。 加上线索的二叉树称之为线索二叉树，对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。,中序线索二叉树,NULL,中序线索链表,3、如何建立线索链表？,方法：在遍历过程中修改空指针、 思路：先写出遍历序列，再画线索。 步骤： 1）标出必要的空指针（前驱左指针；后继右 指针，要点：“不要多标，也不要少标”）。 2）写出对应的遍历序列（前序，中序或后序）。 3）对照遍历结果画线索。,A,B,D,E,G,C,F,H,NULL,NULL,例: 画出下面二叉树的中序线索二叉树,中序遍历序列：D B E G A F H C,前序线索树上找前驱和后继,找前驱： 困难,找后继： 若结点有左孩子，则左孩子是后继；否则，rchild指向后继。,中序线索树上找前驱和后继,中序的前驱和后继都往上指向祖先,找前驱： 若左标记为1，则lchild指向其前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。,找后继： 若右标记为1