数据结构第六章树和二叉树.ppt

上传人:牧羊曲112 文档编号:5738460 上传时间:2023-08-15 格式:PPT 页数:62 大小:237KB
返回 下载 相关 举报
数据结构第六章树和二叉树.ppt_第1页
第1页 / 共62页
数据结构第六章树和二叉树.ppt_第2页
第2页 / 共62页
数据结构第六章树和二叉树.ppt_第3页
第3页 / 共62页
数据结构第六章树和二叉树.ppt_第4页
第4页 / 共62页
数据结构第六章树和二叉树.ppt_第5页
第5页 / 共62页
点击查看更多>>
资源描述

《数据结构第六章树和二叉树.ppt》由会员分享,可在线阅读,更多相关《数据结构第六章树和二叉树.ppt(62页珍藏版)》请在三一办公上搜索。

1、,第六章 树和二叉树,第一节 树的类型定义,A 为“根”T1、T2和T3都是一棵树,称为A的子树。称根和子树根之间的连线为“分支”结点分支的个数定义为“结点的度”,如结点B的度为2,D 的度为3。树中所有结点度的最大值定义为“树的度”。称度为零的结点为“叶子”或“终端结点”所有度不为零的结点被称作分支结点,基本定义,森林为 m(m0)棵互不相交的树的集合。树的深度定义为树中叶子结点所在最大层次数。称根结点为子树根的双亲。称子树根为根结点的孩子“根的所有子树根互为“兄弟”。有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序,不得互换,则称为有序树,否则称为无序树。,树的抽象数据类型:,

2、ADT Tree 数据对象:D是具有相同特性的数据元素的集合。数据关系:若 D 为空集,则称为空树;若 D 中仅含一个数据元素,则关系R为空集;否则 R=H,(1)在D中存在唯一的称为根的数据元素 root,它在关系H下无前驱;(2)当n1时,其余数据元素可分为 m(m0)个互不相交的(非空)有限集 T1,T2,Tm,其中每一个子集本身又是一棵符合本定义的树,称为根 root 的子树,每一棵子树的根 xi 都是根 root 的后继,即 H,i=1,2,m。,基本操作:结构初始化InitTree(初始条件:树 T 存在。操作结果:销毁树 T。,引用型操作TreeEmpty(T);初始条件:树 T

3、 存在。操作结果:若 T 为空树,则返回 TRUE,否则返回 FALSE。TreeDepth(T);初始条件:树T存在。操作结果:返回T的深度。Root(T);初始条件:树 T 存在。操作结果:返回 T 的根。Value(T,cur_e);初始条件:树 T 存在,cur_e 是 T 中某个结点。操作结果:返回 cur_e 的值。,Parent(T,cur_e);初始条件:树 T 存在,cur_e 是 T 中某个结点。操作结果:若 cur_e 是T的非根结点,则返回它的双亲,否则返回空。LeftChild(T,cur_e);初始条件:树 T 存在,cur_e 是 T 中某个结点。操作结果:若 c

4、ur_e 是T的非叶子结点,则返回它的最左孩子,否则返回空。RightSibling(T,cur_e);初始条件:树 T 存在,cur_e 是 T 中某个结点。操作结果:若 cur_e 有右兄弟,则返回它的右兄弟,否则返回空。TraverseTree(T,visit();初始条件:树T存在,visit 是对结点操作的应用函数。操作结果:按某种次序对 T 的每个结点调用函数 visit()一次且至多一次。一旦 visit()失败,则操作失败。,加工型操作Assign(T,cur_e,value);初始条件:树T存在,cur_e 是 T 中某个结点。操作结果:结点 cur_e 赋值为 value。

5、ClearTree(初始条件:树 T 存在,p 指向 T 中某个结点,1ip 指结点的度。操作结果:删除 T 中 p 所指结点的第 i 棵子树。ADT Tree,树和线性结构对照:,第二节 二叉树类型,定义:二叉树是另一种树形结构。它与树形结构的区别是:(1)每个结点最多有两棵子树;(2)子树有左右之分。二叉树也可以用递归的形式定义。即:二叉树是n(n0)个结点的有限集合。当n=0时,称为空二叉树;当n0时,有且仅有一个结点为二叉树的根,其余结点被分成两个互不相交的子集,一个作为左子集,另一个作为右子集,每个子集又是一个二叉树。,二叉树的5种形态:,(a),(b),(c),(d),(e),6.

6、2.1 二叉树的类型定义,ADT BinaryTree 数据对象:D 是具有相同特性的数据元素的集合。数据关系:若 D 为空集,称 BinaryTree 为空二叉树;否则 关系 R=H:(1)在 D 中存在唯一的称为根的数据元素 root,它在关系 H 下无前驱;(2)D 中其余元素必可分为两个互不相交的子集 L 和 R,每一个子集都是一棵符合本定义的二叉树,并分别为 root 的左子树和右子树。如果左子树 L 不空,则必存在一个根结点,它是 root 的左后继(H),如果右子树 R 不空,则必存在一个根结点 为 root 的右后继(H)。,基本操作P:结构初始化InitBiTree(初始条件

7、:二叉树 T 存在。操作结果:销毁二叉树 T。,引用型操作BiTreeEmpty(T);初始条件:二叉树 T 存在。操作结果:若T为空二叉树,则返回 TRUE,否则返回 FALSE。BiTreeDepth(T);初始条件:二叉树 T 存在。操作结果:返回 T 的深度。Root(T);初始条件:二叉树 T 存在。操作结果:返回 T 的根。Value(T,e);初始条件:二叉树 T 存在,e 是 T 中某个结点。操作结果:返回 e 的值。,Parent(T,e);初始条件:二叉树 T 存在,e 是 T 中某个结点。操作结果:若e是T的非根结点,则返回它的双亲,否则返回空。LeftChild(T,e

8、);初始条件:二叉树 T 存在,e 是 T 中某个结点。操作结果:返回 e 的左孩子。若 e 无左孩子,则返回空。RightChild(T,e);初始条件:二叉树 T 存在,e 是 T 中某个结点。操作结果:返回 e 的右孩子。若 e 无右孩子,则返回空。LeftSibling(T,e);初始条件:二叉树 T 存在,e 是 T 中某个结点。操作结果:返回 e 的左兄弟。若 e 是其双亲的左孩子或无左兄弟,则返回空。,RightSibling(T,e);初始条件:二叉树 T 存在,e 是 T 的结点。操作结果:返回 e 的右兄弟。若 e 是其双亲的右孩子或无右兄弟,则返回空。PreOrderTr

9、averse(T,visit();初始条件:二叉树 T 存在,visit 是对结点操作的应用函数。操作结果:先序遍历 T,对每个结点调用函数 visit 一次且仅一次。一旦 visit()失败,则操作失败。InOrderTraverse(T,vsit();初始条件:二叉树 T 存在,visit 是对结点操作的应用函数。操作结果:中序遍历 T,对每个结点调用函数 Visit 一次且仅一次。一旦 visit()失败,则操作失败。PostOrderTraverse(T,visit();初始条件:二叉树T存在,visit 是对结点操作的应用函数。操作结果:后序遍历 T,对每个结点调用函数 visit

10、一次且仅一次。一旦 visit()失败,则操作失败。,LevelOrderTraverse(T,visit();初始条件:二叉树 T 存在,visit 是对结点操作的应用函数。操作结果:层序遍历 T,对每个结点调用函数 visit 一次且仅一次。一旦 visit()失败,则操作失败。加工型操作ClearBiTree(初始条件:二叉树 T 存在,e 是 T 中某个结点。操作结果:结点 e 赋值为 value。,InsertChild(初始条件:二叉树 T 存在,p 指向 T 中某个结点,LR 为 0 或 1。操作结果:根据 LR 为 0 或 1,删除 T 中 p 所指结点的左或右子树。ADT B

11、inaryTree,6.2.2 二叉树的几个特性,一、在二叉树的第 i 层上至多有 2i-1 个结点(i1)。二、深度为k的二叉树中至多含有 2k-1 个结点,(k1)。三、对任何一棵二叉树 T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1,若二叉树中所有的分支结点的度数都为2,且叶子结点都在同一层次上,则称这类二叉树为满二叉树。假如一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为1至 n 的结点一、一对应,则称这类二叉树为完全二叉树。,第三节 二叉树的存储表示,6.3.1 顺序存储结构 二叉树的顺序存储结构的定义如下:const MAXSIZE=100;/暂定

12、二叉树中结点数的最大值为100typedef struct ElemType*data;/存储空间基址(初始化时分配空间)int nodeNum;/二叉树中结点数 SqBiTree;/二叉树的顺序存储结构,6.3.2 链式存储结构,二叉树的二叉链表存储表示typedef struct BiTNode ElemType data;struct BiTNode*Lchild,*Rchild;/左、右孩子指针*BiTree;,二叉树的三叉链表存储表示,typedef struct TriTNode ElemType data;struct BiTNode*Lchild,*Rchild;/左、右孩子指

13、针struct BiTNode*parent;/双亲指针*TriTree;,二叉树的双亲链表存储表示,typedef struct BPTNode/结点结构ElemType data;int*parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNode,第四节 二叉树的遍历,“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。由于二叉树中每个结点都有两个后继,则可以有三条搜索路径:1)先左(子树)后右(子树);2)先右(子树)后左(子树);3)按层次从上到下。,6.4.1 先左后右的遍历 6-4-1遍历.swf,G H,D E F,B C,A,先序序列:

14、ABDGCEFH中序序列:DGBAECHF后序序列:GDBEHFCA,先序遍历递归算法,void PreOrder(BTree BT)if(BT)Visit(BT);PreOrder(BT-Lchild);PreOrder(BT-Rchild);6-4-2-1.swf,中序遍历递归算法,void InOrder(BTree BT)if(BT)InOrder(BT-Lchild);Visit(BT);InOrder(BT-Rchild);6-4-2-2.swf,后序遍历递归算法,void PostOrder(BTree BT)if(BT)PostOrder(BT-Lchild);PostOrde

15、r(BT-Rchild);Visit(BT);6-4-2-3.swf,按层次遍历二叉树,按层次遍历该二叉树的序列为:ABCDEFGH,二叉树用链式存储结构表示时,按层遍历的算法实现(1)访问根结点,并将根结点入队;(2)当队列不空时,重复下列操作:从队列退出一个结点;若其有左孩子,则访问左孩子,并将其左孩子入队;若其有右孩子,则访问右孩子,并将其右孩子入队;,void LevelOrder(BTree*BT)if(!BT)exit;InitQueue(Q);p=BT;/初始化 Visite(p);EnQueue(/处理右孩子,建立二叉树,void CreateBiTree(BiTree/递归建

16、(遍历)右子树 6-4-6.swf,统计二叉树中叶子结点的个数,void CountLeaf(BiTree T,int/if,求二叉树的深度,void BiTreeDepth(BiTree T,int level,int 6-4-3求二叉树的深度.swf,复制二叉树,生成一个二叉树的结点的算法:BiTNode*GetTreeNode(TElemType item,BiTNode*lptr,BiTNode*rptr)/生成一个其元素值为 item,左指针为 lptr,右指针为 rptr 的结点T=new BiTNode;T-data=item;T-Lchild=lptr;T-Rchild=rpt

17、r;return T;,后序遍历复制二叉树的操作为:BiTNode*CopyTree(BiTNode*T)/已知二叉树的根指针为 T,本算法返回它的复制品的根指针if(!T)return NULL;/复制一棵空树if(T-Lchild)newlptr=CopyTree(T-Lchild);/复制(遍历)左子树else newlptr=NULL;if(T-Rchild)newrptr=CopyTree(T-Rchild);/复制(遍历)右子树else newrptr=NULL;newnode=GetTreeNode(T-data,newlptr,newrptr);/生成根结点return new

18、node;6-4-5后序遍历复制.swf,在二叉树上查询某个结点,void locate(BiTree T,ElemType x,BiTree,中序遍历(非递归),InitStack(S);Push(S,T);/根入栈while(!StackEmpty(S)while(GetTop(S,p),表达式的二叉树,二叉树的线索链表,将在二叉树中每个结点(除第一个和最后一个外)的直接前驱和直接后继保存起来。这种信息是在遍历的动态过程中产生的,如果将这些信息在第一次遍历时就保存起来,则在以后再次需要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。typedef enum PointerT

19、ype Link=0,Thread=1;/定义指针类型,以 Link 表示指针,Thread 表示线索typedef struct BiThrNodeElemType data;struct BiThrNode*Lchild,*Rchild;/左右指针PointerType LTag,RTag;/左右指针类型标志*BiThrTree;,在线索链表中添加了一个头结点,头结点的左指针指向二叉树的根结点,其右线索指向中序序列中的最后一个结点,以中序线索链表为存储结构的中序遍历,void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(ElemType e)/

20、T 指向中序线索链表中的头结点,头结点的左指针 Lchild 指向二叉树的根结点,头结点的右线索 Rchild 指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历,对树中每个元素调用函数 Visit 进行访问操作p=T-Lchild;/p 指向二叉树的根结点while(p!=T)/空树或遍历结束时,p=Theadwhile(p-LTag=Link)p=p-Lchild;Visit(p-data);/访问其左子树为空的结点while(p-RTag=Thread/p 进至其右子树根,p=T-Lchild;/p 指向二叉树的根结点while(p!=T)/空树或遍历结束时,p=Theadwh

21、ile(p-LTag=Link)p=p-Lchild;Visit(p-data);/访问其左子树为空的结点while(p-RTag=Thread/p 进至其右子树根 6-5-1.swf,线索链表的生成,void InThreading(BiThrTree p,BiThrTree/对右子树进行线索化,void InOrderThreading(BiThrTree/建非空树的头结点的右线索 6-5-2.swf,树和森林的存储表示 1 树的双亲表示法,const MAX_TREE_SIZE=100;typedef struct/结点结构ElemType data;int parent;/双亲位置域

22、PTNode;typedef struct/树结构PTNode nodesMAX_TREE_SIZE;int r,n;/根的位置和结点数 PTree;,2 树的孩子表示法,树的孩子链表存储表示typedef struct CTNode/孩子结点int child;struct CTNode*next;*ChildPtr;typedef struct ElemType data;/结点的数据元素ChildPtr firstchild;/孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;,

23、3 树和森林的孩子兄弟表示法,存储表示 typedef struct CSNodeElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;firstchild 指向该结点的第一个子树根结点,nextsibling 指向它的下一个兄弟结点。,树的孩子-兄弟链表,森林的孩子-兄弟链表,森林和二叉树的转换,森林二叉树 6-6-1.swf,二叉树森林 6-6-2.swf,树的遍历,一、先根(次序)遍历树 若树不空,则先访问根结点,然后依次从左到右先根遍历根的各棵子树;ABEHIJCDFGK 6-7-3.swf,二、后根(次序

24、)遍历树若树不空,则先依次从左到右后根遍历根的各棵子树,然后访问根结点;HIJEBCFKGDA 6-7-4.swf,森林的遍历,一、先序遍历森林 若森林不空,则可依下列次序进行遍历(1)访问森林中第一棵树的根结点;(2)先序遍历第一棵树中的子树森林;(3)先序遍历除去第一棵树之后剩余的树构成的森林。二、中序遍历森林 若森林不空,则可依下列次序进行遍历:(1)中序遍历第一棵树中的子树森林;(2)访问森林中第一棵树的根结点;(3)中序遍历除去第一棵树之后剩余的树构成的森林。,求森林的深度,森林的深度=Max每一棵树的深度树的深度=其子树森林的深度+1int Depth_Tree(CSTree T)/T 是以孩子-兄弟链表存储的森林的头指针,返回该森林的深度if(!T)return 0;else dep=0;/初始化森林的深度为0p=T;/指针 p 指向第一棵树的根while(p)d=Depth_Tree(p-firstchild);/返回*p 的子树森林的深度if(d+1dep)dep=d+1;/求各棵树的深度的最大值 p=p-nextsibling;/指针 p 移向下一棵树的根 return dep;,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号