第10讲树和二叉树的定义.ppt
《第10讲树和二叉树的定义.ppt》由会员分享,可在线阅读,更多相关《第10讲树和二叉树的定义.ppt(37页珍藏版)》请在三一文库上搜索。
1、第10讲 树和二叉树的定义,主讲人:陈红丽,对比树型结构和线性结构的结构特点,树的定义 树是n(n0)个结点的有限集合,在任一棵非空树中: (1)有且仅有一个称为根(root)的结点。 (2)其余结点可分为 m 个互不相交的集合,而且其中的每一个集合本身又是一棵树,称为根的子树。,A,B,C,D,E,F,G,H,I,J,M,K,L,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,树的基本术语,(从根到结点的)路径:,孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点,结点的层次:,
2、树的深度:,由从根到该结点所经分支和结点构成,假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,任何一棵非空树是一个二元组 Tree = (root,F) 其中:root 被称为根结点 F 被称为子树森林,森林:,是m(m0)棵互不相交的树的集合,有序树: 子树之间存在确定的次序关系。 无序树: 不考虑子树的顺序。,树的抽象数据类型的定义,ADT Tree 数据对象:D是具有相同特性的数据元素的集合。 数据关系: 若 D 为空集,则称为空树; 若 D 中仅含一个数据元素,则关系R为空集; 否则 R=H,,(1) 在D中存在唯一的称为根的数据元素 roo
3、t,它在关系H下无前驱; (2) 当n1时,其余数据元素可分为 m(m0) 个互不相交的(非空)有限集 T1,T2,Tm, 其中每一个子集本身又是一棵符合本定义的树,称为根 root 的子树,每一棵子树的根 xi 都是根 root 的后继,即 H, i=1,2,m。 基本操作: ADT Tree,基本操作:,结构初始化 InitTree( 初始条件:树 T 存在。 操作结果:销毁树 T。,引用型操作 TreeEmpty(T); 初始条件:树 T 存在。 操作结果:若 T 为空树,则返回 TRUE,否则返回 FALSE。 TreeDepth(T); 初始条件:树 T 存在。 操作结果:返回T的深
4、度。 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 中某个结点。 操作结果:若 cur_e 是T的非叶子结点,则返回它的最左孩子,否则返回“空“。,RightSibling(T, cur_e)
5、; 初始条件:树 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。,ClearTree( 初始条件:树 T 存在,p 指向 T 中某个结点,1ip 指
6、结点的度。 操作结果:删除 T 中 p 所指结点的第 i 棵子树。,二叉树,定义 或为空树,或是由一个根结点和两棵互不相交的左子树、右子树构成,并且左、右子树本身也是二叉树。 特性 二叉树中每个结点最多有两棵子树;二叉树每个结点的度小于等于2 子树有左右之分,不能颠倒有序树 二叉树是递归结构,在二叉树的定义中又用到了二叉树的概念,ADT BinaryTree 数据对象:D 是具有相同特性的数据元素的集合。 数据关系: 若 D 为空集,称 BinaryTree 为空二叉树; 否则 关系 R=H: (1) 在 D 中存在唯一的称为根的数据元素 root,它在关系 H 下无前驱; (2) D 中其余
7、元素必可分为两个互不相交的子集 L 和 R,每一个子集都是一棵符合本定义的二叉树,并分别为 root 的左子树和右子树。如果左子树 L 不空,则必存在一个根结点 XL,它是 root 的“左后继”(H),如果右子树 R 不空,则必存在一个根结点 XR为 root 的“右后继”(H)。 基本操作: ADT BinaryTree,二叉树的抽象数据类型的定义,结构初始化 InitBiTree( 初始条件:二叉树 T 存在。 操作结果:销毁二叉树 T。,基本操作:,引用型操作 BiTreeEmpty(T); 初始条件:二叉树 T 存在。 操作结果:若T为空二叉树,则返回 TRUE,否则 返回 FALS
8、E。 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); 初始条件:二叉树 T 存在,e 是 T 中某个结点。 操作结果:返回 e 的左孩子。若 e 无左孩子, 则返回“空“。,RightChil
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 10 二叉 定义
链接地址:https://www.31doc.com/p-3418465.html