第6章 树和二叉树(严).ppt

第6章 树和二叉树（Tree Binary Tree） 6.1 树6.1.1 树的定义 6.1.2 若干术语 6.1.3 树的抽象数据类型 6.1.4　树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有： 双亲表示法 孩子表示法 双亲孩子表示法 孩子兄弟表示法 四种组合。 补充：树的5种表示法： 图形表示法 6.2 二叉树 为何要重点研究结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 6.2.1　二叉树的定义 二、满二叉树 　　在一棵二叉树中，如果所有分支结点都 存在左子树和右子树，并且所有叶子结点都 在同一层上，这样的二叉树称为满二叉树。 (一棵深度为k((k≥-1)且有2k+1-1个结点的 图6.4 二叉树称为满二叉树。) 三、完全二叉树 　　如果一棵深度为k，有n个结点的二叉树 中各结点能够与深度为k的顺序编号的满二叉 树从1到n标号的结点相对应的二叉树称为完 全二叉树。 特点: 图6.5 (1)所有的叶结点都出现在第k层或k－1层。 (2)若任一结点，如果其右子树的最大层次为i，则其左子树的 最大层次为i或i＋1。 三、满二叉树与完全二叉树的区别 　　　满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。 四、为何要研究这两种特殊形式？ 　　　因为它们在顺序存储方式下可以复原。 6.2.2 二叉树的抽象数据类型 6.2.3　二叉树的性质 问题、针对二叉树，回答下列问题：(1)具有n个结点的非空二叉树的最小深度是多少？最大深度是多少？(2)具有n个结点的完全二叉树中有多少个叶子结点？有多少个度为2的结点？(3)具有n0个叶子结点的完全二叉树中共有多少个结点？ 答:(1)其最小深度是?㏒2n? +1 ，最大深度是n。 (2)具有n个结点的完全二叉树中有?n/2?叶子结点，有?n/2?-1个度为2的结点。 （3）具有n0个叶子结点的完全二叉树中共有2n0 个结点或2n0-1个结点。 练习： 6.2.3 二叉树的顺序存储结构 二叉树的存储结构主要有三种：顺序存储结构、链式存储结构和仿真指针存储结构。 1. 二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。图6-4在数组中的存储结构为： 数组 下标 0 1 2 3 4 5 6 3. 二叉树的仿真指针 补充：二叉链存储结构的二叉树操作实现 在二叉链存储结构下，针对一棵二叉树，主要涉及如下几个功能模块： 二叉树的初始化操作； 二叉树中给某结点插入一个左结点的操作； 二叉树中给某结点插入一个右结点的操作； 删除二叉树中某结点的左子树操作； 删除二叉树中某结点的右子树操作。 各算法的基本思想及程序实现如下： typedef struct BiTNode { TElemType data; struct BiTNode *leftChild; struct BiTNode *rightChild; }BiTNode,*BiTree; /*结点的结构体定义*/ 2.二叉树中给某结点插入一个左结点的操作 算法的基本思想: 若当前结点(假设为curr）非空，在curr的左子树插入元素值为x的新结点 ，原curr所指结点的左子树成为新插入结点的左子树。若插入成功返回新插入结点的指针，否则返回空指针。 3.删除二叉树中某结点的左子树操作 例：编写一个建立图6.8(b)所示的带头结点的二叉链存储结构二叉树的程序。 设计：假设上述二叉树结点结构体定义和二叉树操作实现函数存放在文件“Bitree.h”中,程序设计如下： #include stdlib.h #include stdio.h typedef char TElemType; #include Bitree.h 小结 内容回顾； 6.2 二叉树 6.2.1 二叉树的存储结构 6.2.2 二叉链存储结构的二叉树操作实现 下节课内容 二叉树遍历和线索二叉树 上节回顾 6.2 二叉树的设计和实现