树和二叉树的定义.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个结点（