第07章1自定义数据类型.ppt
《第07章1自定义数据类型.ppt》由会员分享,可在线阅读,更多相关《第07章1自定义数据类型.ppt(38页珍藏版)》请在三一文库上搜索。
1、第7章 树和二叉树,树 二叉树 以结点类为基础的二叉树设计 二叉树类 二叉树的分步遍历 线索二叉树 哈夫曼树 树与二叉树的转换 树的遍历,主要知识点,7.1 树,1.树的定义,树是由n(n0)个结点组成的有限集合T。n=0的树称为空树;对n0的树,有:(1)仅有一个特殊的结点称为根结点,根结点没有前驱结点;(2)当n1时,除根结点外其余的结点分为m(m0)个互不相交的有限集合T1,T2,Tm,其中每个集合Ti本身又是一棵结构和树类似的子树。,注:树的定义具有递归性,即“树中还有树”。,若干术语,结点:由数据元素和构造数据元素之 间关系的指针组成,结点的度:结点所拥有的子树的个数,叶结点:度为0
2、的结点,也称作 终端结点,分支结点:度不为0的结点,孩子结点:树中一个结点的子树的根结点,双亲结点:若树中某结点有孩子结点,则这个结点就 称作它的孩子结点的双亲结点,兄弟结点:具有相同的双亲结点的结点,树的度:树中所有结点的度的最大值,结点的层次:从根结点到树中某结点所经路径上的分支数,树的深度:树中所有结点的层次的最大值,无序树:树中任意一个结点的各孩子结点之间的次序 构成无关紧要的树,有序树:树中任意一个结点的各孩子结点有严格排列 次序的树,森林:m(m0)棵树的集合,2.树的表示方法,(1)直观表示法,(2)形式化表示法,(3)凹入表示法,3.树的抽象数据类型,数据集合: 树的结点集合,
3、每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合: (1)创建树 MakeTree(T) (2)撤消树 DestroyTree(T) (3)查找树中当前结点的双亲结点 Parent(T,curr) (4)查找树中当前结点的左孩子结点 LeftChild(T,curr) (5)查找树中当前结点的右兄弟结点 RightSibling(T,curr) (6)遍历树 Traverse(T,Visit( ),4.树的存储结构,树的结点之间的逻辑关系主要有双亲-孩子关系,兄弟关系。因此,从结点之间的逻辑关系分,树的存储结构主要有:双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组
4、合。,(1)双亲表示法,(a)一棵树,(b)仿真指针的双亲表示法存储结构,树及其使用仿真指针的双亲表示法,(2)孩子表示法,双亲孩子表示法,(3)双亲孩子表示法,(4)孩子兄弟表示法,常规指针的孩子兄弟表示法,7.2 二叉树,一、二叉树:是n(n0)个结点的有限集合。n=0的树称为空二叉树;n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构: 一对二(1:2) 基本特征: 每个结点最多只有两棵子树(不存在度大于2的结点); 左子树和右子树次序不能颠倒。所以下面是两棵不同的树,1.二叉树的定义,二、满二叉树:在一棵二叉树中,如果所有分支结点都存在左 子树
5、和右子树,并且所有叶子结点都在同一层上,这样的 二叉树称为满二叉树。 三、完全二叉树:如果一棵深度为k,有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示,(a)满二叉树,(b)完全二叉树,数据集合:二叉树的结点集合,每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合: (1)创建二叉树 MakeTree(T) (2)撤消二叉树 DestroyTree(T) (3)左插入结点 InsertLeftNode(curr,x) (4)右插入结点 InsertRightNode(curr,x) (5)左删除子树 Del
6、eteLeftTree(curr) (6)右删除子树 DeleteRightTree(curr) (7)遍历二叉树 Traverse(T,Visit(),2.二叉树抽象数据类型,3.二叉树的性质,性质1:在一棵非空二叉树的第i层上至多有2i个结点(i0)。,性质2:深度为k的二叉树至多有2k+1-1个结点(k-1)。,性质3: 具有n个结点的完全二叉树的深度k为不超过log2(n+1)-1的最大整数。,证明:根据性质2,对于有n个接点的深度为k的完全二叉树有 2k-1n2k+1-1,移项,有 2kn+12k+1 对不等式求对数,有klog2(n+1)k+1,因为k必须是整数,所以k=log2(
7、n+1)-1,性质4:对于一棵有n个结点的完全二叉树,按照从上至下和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点(0in),有: (1)如果i0,则其双亲是结点(i-1)/2(“/”表示整除) ;如果i=0,则结点I是根结点,无双亲。 (2)如果2i+1n ,其左孩子是结点2i+1;如果2i+1n,则结点i无左孩子。 (3)如果2i2n,其右孩子是结点2i2;如果2i2n,则结点i无右孩子。,二叉树的存储结构主要有三种:顺序存储结构、链式存储结 构和仿真指针存储结构。 (1) 二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中,其结点之间的关系
8、可由公式计算得到,这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为:,4.二叉树的存储结构,对于一般的非完全二叉树显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态,然后再用顺序存储结构存储。,(a)一般二叉树,(b)完全二叉树形态,(c) 在数组中的存储形式,(2) 二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域,分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中
9、每个结点的图示结构为:,二叉链存储结构的二叉树也有不带头结点和带头结点两种。带头结点的二叉链存储结构的二叉树见下图(b),不带头结点的二叉链存储结构的二叉树如下图(a)所示。,图7-10 二叉链存储结构的二叉树,(a)不带头结点的二叉树,(b)带头结点的二叉树,(3)二叉树的仿真指针 二叉树的仿真指针存储结构是用数组存储二叉树中的结点,数组中每个结点除数据元素域外,再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。,二叉树的仿真二叉链存储结构,7.3 以结点类为基础的二叉树设计,二叉树的实现有两种基本方法:一种方法是首先设计二叉树结点类,然后在二叉树结点类的基础上,用结点类的外部函数
10、实现二叉树的操作;另一种方法是在二叉树结点类的基础上,再设计二叉树类。,1.二叉树的结点类,模板形式的二叉树结点类定义和实现代码如下:,template class BiTreeNode private: BiTreeNode *leftChild; /左子树指针 BiTreeNode *rightChild; /右子树指针 public: T data; /数据域 BiTreeNode():leftChild(NULL), rightChild(NULL) BiTreeNode(T item, BiTreeNode *left = NULL, BiTreeNode *right = NULL
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 07 自定义 数据类型
链接地址:https://www.31doc.com/p-3417675.html