数据结构第六章树和二叉树.ppt
《数据结构第六章树和二叉树.ppt》由会员分享,可在线阅读,更多相关《数据结构第六章树和二叉树.ppt(69页珍藏版)》请在三一文库上搜索。
1、,1数据的逻辑结构,2、数据的存储结构,3、数据的运算:检索、排序、插入、删除、修改等。,A 线性结构,B 非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,第六章 树和二叉树,6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.6 赫夫曼树及其应用 6.6.1 最优二叉树(赫夫曼树) 6.6.2 赫夫曼编码,树形结构
2、是一类重要的非线性结构。树形结构是结点之间有分支,并具有层次关系的结构。它非常类似于自然界中的树。,树形结构 结点间具有分层次的连接关系,6.1 树的定义和基本术语,树(Tree)是n(n0)个结点的有限集合T,它满足如下条件: 有且仅有一个称为根(Root)的结点。 其余结点可划分为m(m=0)个互不相交的有限集合T1 ,T2,Tm,其中每个集合又是一棵树,并称其为根的子树(SubTree)。 这是一个递归定义。有时n=0也称为空树。,树的表示方法,1)树形图法 2)嵌套集合法 3)广义表形式 4)凹入表示法,( A(B, C(E,F), D(G) ) ),线性结构 (一对一关系) 树结构(
3、一对多关系) 第一个数据元素(无前驱) 根结点(无前驱) 最后一个数据元素(无后继) 多个终端结点(无后继) 其它数据元素 树中其它结点 (一个前驱、一个后继) (一个前驱、多个后继),树形结构和线性结构的比较,树结构的基本术语,结点(node)表示树中的元素,包括数据元素及若干指向其子树的分支。 结点的度(degree)结点拥有的子树数。 叶子(leaf)或终端结点度为0的结点。 分支结点度大于零的结点。 树的度树中所有结点的度的最大值。 孩子(child)结点的子树的根。 双亲(parents)孩子结点的上层结点。 兄弟(sibling)同一双亲的孩子。 堂兄弟其双亲在同一层的结点互为堂兄
4、弟。 结点的层次(level)从根结点算起,根为第一层,它的孩子为第二层。 深度(depth)树中结点的最大层次数。 森林(forest)m(m0)棵互不相交的树的集合。,树的抽象数据类型定义:,ADT Tree 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:若D为空集,则称为空树; 若D仅含一个数据元素,则R为空集,否则RH,H是如下二元关系: (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)若Droot,则存在Droot的一个划分D1, D2, ., Dm (m0),对任意jk(1j,km)有DjDk= ,且对任意 的i(1im),唯一存在数据元素
5、xiDi,有 H; (3)对应于Droot的划分,H, 有唯一的一个划分H1 , H2 ,., Hm (m0),对任意jk (1j,km)有HjHk= ,且对任意的i(1im),Hi 是Di上 的二元关系,(Di ,Hi)是一棵符合本定义的树,称为根root的子 树。,树的抽象数据类型定义-基本操作(之一),InitTree(&T); 操作结果:构造空树T。 DestroyTree (&T) ; 初始条件:树T存在。 操作结果:销毁树T。 CreateTree (&T,definition ) ; 初始条件: definition给出树T的定义。 操作结果:按definition构造树T。 C
6、learTree(&T ) ; 初始条件:树T存在。 操作结果:将树T清为空树。,树的抽象数据类型定义-基本操作(之二),TreeEmpty(T) 初始条件:树T存在。 操作结果:若T为空树,则返回TURE,否则FALSE。 TreeDepth(T) 初始条件:树T存在。 操作结果:返回T的深度。 Root(T ) 初始条件:树T存在。 操作结果:返回T的根。 Value(T, cur_e) ; 初始条件:树T存在, cur_e是T中某个结点。 操作结果:返回cur_e的值。,树的抽象数据类型定义-基本操作(之三),Assign(T,cur_e,value) 初始条件:树T存在,cur_e是T
7、中某个结点。 操作结果:结点cur_e赋值 为value 。 Parent(T, cur_e ) 初始条件:树T存在,cur_e是T中某个结点。 操作结果:若cur_e是T的非根结点,则返回它的双亲,否则 函数值为“空”。 LeftChild(T, cur_e ) 初始条件:树T存在,cur_e是T中某个结点。 操作结果:若cur_e是T的非叶子结点,则返回它的最左孩子,否则返 回 “空”。 RightSibling(T, cur_e ) 初始条件:树T存在,cur_e是T中某个结点。 操作结果:若cur_e有右兄弟,则返回它的右兄弟,否则函数值为 “空”。,树的抽象数据类型定义-基本操作(之
8、四),InsertChild(&T,&p,i,c); 初始条件:树T存在,p指向T中某个结点,1ip所指结点的度1,非空树c与T不相交。 操作结果:插入c为T中p指结点的第i棵子树。 DeleteChild (&T,&p,i ) ; 初始条件:树T存在,p指向T中某个结点,1ip指结点的度。 操作结果:删除T中p所指结点的第i棵子树。 TraverseTree ( T,Visit() ) ; 初始条件:树t存在, Visit是对结点操作的应用函数。 操作结果:按某种次序对T的每个结点调用函数Visit ()一次且至多一次。一旦Visit ()失败,则操作失败。 ADT Tree,6.2 二叉树
9、,二叉树的定义:二叉树是n(n0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 二叉树的特点: 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分,且其次序不能任意颠倒,二叉树的五种基本形态:,空二叉树,只有一个根结点 的二叉树,右子树为空 的二叉树,左子树为空 的二叉树,左、右子树均 非空的二叉树,注意:二叉树中子树是有左右之分的,即使只有一棵子树,或为左子树,或为右子树,这不是二叉树,这是二叉树,6.2.2 二叉树的性质,性质1:在二叉树的第i层上至多有2i-1个结点(i1)。 性质2:深度为k的二叉树至多
10、有2k-1个结点 (k1)。 性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。,几种特殊形态的二叉树,满二叉树 定义:深度为k且有2k-1个结点的二叉树 特点:每一层上的结点数都是最大结点数 完全二叉树 定义:深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。 特点: 叶子结点只可能在层次最大的两层上出现 对任一结点,若其右分支下子孙的最大层次为L,则其左分支下子孙的最大层次必为L 或L+1 说明:满二叉树是完全二叉树,反之不成立; 对于完全二叉树,若某结点无左孩子,则必无右孩子
11、, 该结点为叶结点。,性质4:具有n个结点的完全二叉树的深度为log2n +1 性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1in),有: (1) 如果i=1,则结点i是二叉树的根,无双亲;如果i1,则其双亲是i/2 (2) 如果2in,则结点i无左孩子;如果2in,则其左孩子是2i (3) 如果2i+1n,则结点i无右孩子;如果2i+1n,则其右孩子是2i+1,6.2.3 二叉树的存储结构,顺序存储结构 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。,下
12、标 0 1 2 3 4 5 6 7 8 9 10 11,对完全二叉树而言,顺序存储结构既简单又节省存储空间。 一般的二叉树采用顺序存储结构时,虽然简单,但易造成存储空间的浪费。 (最坏的情况下,一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间),链式存储结构,typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指针 BiTNode,*BiTree;,链式存储结构示例,注意: 一个二叉链表由根指针root惟一确定。若二叉树为空,则root=NULL;若结点的某个孩子不存在,则相应的
13、指针为空。 具有n个结点的二叉链表中,共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子,其余的n+1个指针域为空。,基本操作的函数原型说明(一),Status CreateBiTree(BiTree /采用二叉链表存储结构,Visit是对结点操作的应用函数 /先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。 /一旦Visit( ) 失败,则操作失败。,基本操作的函数原型说明(二),Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数。 /中序遍历
14、二叉树T,一旦Visit( ) 失败,则操作失败。 Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数。 /后序遍历二叉树T,一旦Visit( ) 失败,则操作失败。 Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e); /采用二叉链表存储结构,Visit是对结点操作的应用函数。 /层序遍历二叉树T,一旦Visit( ) 失败,则操作失败。,6.3 遍历二叉树,按某条搜索路径巡访二叉树中
15、每个结点,使得每个结点均被访问一次,而且仅被访问一次。,假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树,遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右,则只有前三种情况,分别规定为: DLR先(根)序遍历, LDR中(根)序遍历, LRD后(根)序遍历。,先序遍历二叉树的操作定义,若二叉树为空,则空操作;否则 (1)访问根结点; (2)先序遍历左子树; (3)先序遍历右子树。 A B C D F E G,中序遍历二叉树的操作定义,若二叉树为空,则空操作;否则 (1)中序遍历左子树; (2)访问根结点; (3)中序遍历右子树。 C B D
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第六 二叉
链接地址:https://www.31doc.com/p-2157216.html