第10讲树和二叉树的定义.ppt

第10讲 树和二叉树的定义,主讲人：陈红丽,对比树型结构和线性结构的结构特点,树的定义 树是n（n0）个结点的有限集合，在任一棵非空树中：(1)有且仅有一个称为根(root)的结点。(2)其余结点可分为 m 个互不相交的集合，而且其中的每一个集合本身又是一棵树，称为根的子树。,A,B,C,D,E,F,G,H,I,J,M,K,L,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,树的基本术语,(从根到结点的)路径：,孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m0）棵互不相交的树的集合,有序树：子树之间存在确定的次序关系。无序树：不考虑子树的顺序。,树的抽象数据类型的定义,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。基本操作：ADT Tree,基本操作：,结构初始化InitTree(初始条件：树 T 存在。操作结果：销毁树 T。,引用型操作TreeEmpty(T);初始条件：树 T 存在。操作结果：若 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 中某个结点。操作结果：若 cur_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。,ClearTree(初始条件：树 T 存在，p 指向 T 中某个结点，1ip 指结点的度。操作结果：删除 T 中 p 所指结点的第 i 棵子树。,二叉树,定义 或为空树，或是由一个根结点和两棵互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。特性二叉树中每个结点最多有两棵子树；二叉树每个结点的度小于等于2子树有左右之分，不能颠倒有序树二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念,ADT BinaryTree 数据对象：D 是具有相同特性的数据元素的集合。数据关系：若 D 为空集，称 BinaryTree 为空二叉树；否则 关系 R=H：(1)在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱；(2)D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L 不空，则必存在一个根结点 XL，它是 root 的“左后继”(H)，如果右子树 R 不空，则必存在一个根结点 XR为 root 的“右后继”(H)。基本操作：ADT BinaryTree,二叉树的抽象数据类型的定义,结构初始化InitBiTree(初始条件：二叉树 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);初始条件：二叉树 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 是其双亲的右孩子或无右兄弟，则返回空。,PreOrderTraverse(T，visit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit()失败，则操作失败。InOrderTraverse(T，vsit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit()失败，则操作失败。PostOrderTraverse(T，visit();初始条件：二叉树T存在，visit 是对结点操作的应用函数。操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 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 所指结点的左或右子树。,a、b两棵二叉树相同吗？为什么？,(a),(b),二叉树的基本形态,A,(a)空二叉树,(b)只有根结点的二叉树,(c)左右子树都非空的二叉树,(e)左子树为空的二叉树,(d)右子树为空的二叉树,问：具有3个结点的二叉树可能有几种不同形态？,答：有5种,二叉树的性质,性质1：在二叉树的第i层上至多有()个结点(i1),2i-1,证明：用归纳法当i=1时，只有一个根结点，2i-1=20=1，命题成立。现在假设当 j i1时命题成立，即第 i1层上至多有2i-2 个结点。由于二叉树的每个结点最多有两棵子树，那么在第 i层上的结点数目为第 i1层上最大结点数的 2 倍，即 22i-2 2i-1。由此证明命题。,性质2：深度为 k 的二叉树至多有()个结点（k1)。,2k-1,证明如下：深度为 k 的二叉树的最大结点数目为二叉树中每层上的最大结点数之和，第1层到第k层的最大结点数之和为：20+21+22+2k-1=(1-2k)/(1-2)=2k-1,性质3：对任何一棵二叉树 T，如果其终端结点数为 n0，度为2的结点数为 n2，则()。,证明：设 n1为二叉树 T 中度为 1的结点数，又因为二叉树中所有结点的度都 2，所以二叉树中结点总数 n 为：n n0 n1 n2（1）再看二叉树中的分支数：除根结点外，每个结点都有一个分支进入，设B为分支总数，则 nB1（2）由于这些分支是由度为 1 或 2 的结点射出的，所以又有：Bn1 2n2（3）由（1）、（2）、（3）可得：n0n21。,n0n21,两类特殊的二叉树,满二叉树：深度为 k，且有 2k-1 个结点的二叉树；特点：每一层上的结点数都是最大数目。结点层序编号方法：从根结点起自上而下逐层（层内自左至右）对二叉树的结点进行连续编号。,完全二叉树：一棵深度为 k 有 n 个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。一棵深度为k的二叉树，如果它的前k-1层构成了一棵深度为k-1的满二叉树，而最后一层上的结点是向左充满分布的，则称此二叉树为完全二叉树。,特点：叶子结点只可能在层次数最大的两层上出现。只有最下一层的结点数可能未达到最大值。其最后一层结点是向左充满的；完全二叉树结点数是（）满二叉树一定是完全二叉树，反之不成立。,完全二叉树,2k-1-1n 2k-1,性质4：具有n个结点的完全二叉树的深度为()。,证明如下：假设该完全二叉树的深度为 k，则根据完全二叉树的定义和性质 2有：2k-11 n 2k1 或 2k-1 n 2k 所以有：k1 log2nk 又因为 k是整数，所以，k log2n 1,log2n 1,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点 i(1in)，有：1、如果 i=1，则结点 i是二叉树的根，无双亲；如果 i 1，则其双亲是（）结点2、如果 2i n，则结点 i无左孩子，为叶结点；否则其左孩子是结点（）。3、如果 2i+1 n，则结点 i无右孩子；否则其右孩子是结点（）。,i/2,2i,2i+1,习题：设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。,1,0,由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。,答：易求出总层数和末层叶子数。总层数k=log2n1=10;且前9层总结点数为29-1=511(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。,请注意叶子结点总数末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。分析：末层的489个叶子只占据了上层的245个结点（489/2)上层（k=9)右边的0度结点数还有29-1-245=11个！,第i层上的满结点数为2i-1,所以，全部叶子数489(末层)11(k-1层)=500个。度为2的结点叶子总数1=499个。,另一法：可先求2度结点数,再由此得到叶子总数。首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉）另外，末层叶子（刚才已求出为489）所对应的双亲也是度2，（共有489/2244个）。所以，全部2度结点数为255(k-2层)244(k-1层)=499个；总叶子数2度结点数1=500个。,