第10讲 树和二叉树的定义

《第10讲 树和二叉树的定义》由会员分享，可在线阅读，更多相关《第10讲 树和二叉树的定义（37页珍藏版）》请在金锄头文库上搜索。

1、数据结构 第10讲 树和二叉树的定义主讲人：陈红丽第六章 树和二叉树 对比树型结构和线性结构的结构特点第六章 树和二叉树 线性结构树型结构 第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素 (一个前驱、一个后继)其它数据元素 (一个前驱（双亲） 多个后继（孩子）)第六章 树和二叉树 l树的定义树是n（n0）个结点的有限集合，在任 一棵非空树中： (1)有且仅有一个称为根(root)的结点。 (2)其余结点可分为 m 个互不相交的集合 ，而且其中的每一个集合本身又是一棵树 ，称为根的子树。ABCDEFGHIJMKL第六章 树和二叉树 结点:结点

2、的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM树的基本术语第六章 树和二叉树 (从根到结点的)路径：孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分 支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l 层的 结点的子树根结点的层次为l+1树中叶子结点所在的最大层次第六章 树和二叉树 任何一棵非空树是一个二元组Tree = （root，F） 其中：root 被称为根结点F 被称为子树森林森林：是m（m0）棵互不相交的树的 集合ArootBCDE

3、FGHIJMKLF 有序树： 子树之间存在确定的 次序关系。 无序树： 不考虑子树的顺序。第六章 树和二叉树 树的抽象数据类型的定义ADT Tree 数据对象：D是具有相同特性的数据元素的集合。 数据关系：若 D 为空集，则称为空树；若 D 中仅含一个数据元素，则关系R为空集；否则 R=H， (1) 在D中存在唯一的称为根的数据元素 root，它 在关系H下无前驱；(2) 当n1时，其余数据元素可分为 m(m0) 个互不 相交的(非空)有限集 T1,T2,Tm, 其中每一个子集本身 又是一棵符合本定义的树，称为根 root 的子树，每一 棵子树的根 xi 都是根 root 的后继，即 H, i

4、=1,2,m。 基本操作： ADT Tree第六章 树和二叉树 基本操作：结构初始化 InitTree( 操作结果：构造空树 T。CreateTree( 初始条件：definition 给出树T的定义。 操作结果：按 definition 构造树 T。销毁结构 DestroyTree( 初始条件：树 T 存在。 操作结果：销毁树 T。第六章 树和二叉树 引用型操作 TreeEmpty(T); 初始条件：树 T 存在。 操作结果：若 T 为空树，则返回 TRUE，否则返 回 FALSE。TreeDepth(T); 初始条件：树 T 存在。 操作结果：返回T的深度。 Root(T); 初始条件：树

5、 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)

6、; 初始条件：树 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 存在。 操作结果：将树

7、T 清为空树。InsertChild( 初始条件：树 T 存在，p 指向T中某个结点，1ip 所 指结点的度1，非空树 c 与 T 不相交。 操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树。DeleteChild( 初始条件：树 T 存在，p 指向 T 中某个结点，1ip 指 结点的度。 操作结果：删除 T 中 p 所指结点的第 i 棵子树。第六章 树和二叉树 二叉树l定义或为空树，或是由一个根结点和两棵互不相交 的左子树、右子树构成，并且左、右子树本身 也是二叉树。l特性二叉树中每个结点最多有两棵子树；二叉树 每个结点的度小于等于2子树有左右之分，不能颠倒有序树二叉树是递归结构

8、，在二叉树的定义中又用 到了二叉树的概念二叉树与度为2的树相同吗？ 为什么？ABCDEFGHK根结点左子树右子树第六章 树和二叉树 ADT BinaryTree 数据对象：D 是具有相同特性的数据元素的集合。 数据关系：若 D 为空集，称 BinaryTree 为空二叉树；否则 关系 R=H：(1) 在 D 中存在唯一的称为根的数据元素 root，它在 关系 H 下无前驱；(2) D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本定义的二叉树，并分别 为 root 的左子树和右子树。如果左子树 L 不空，则必 存在一个根结点 XL，它是 root 的“左后继”(H)

9、，如果右子树 R 不空，则必存在一个根结点 XR为 root 的“右后继”(H)。基本操作： ADT BinaryTree二叉树的抽象数据类型的定义第六章 树和二叉树 结构初始化 InitBiTree( 操作结果：构造空二叉树 T。CreateBiTree( 初始条件：definition 给出二叉树 T 的定义。 操作结果：按 definition 构造二叉树 T。销毁结构 DestroyBiTree( 初始条件：二叉树 T 存在。 操作结果：销毁二叉树 T。 基本操作：第六章 树和二叉树 引用型操作 BiTreeEmpty(T); 初始条件：二叉树 T 存在。 操作结果：若T为空二叉树，则

10、返回 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

11、无左孩子，则返回“空“。 第六章 树和二叉树 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，vi

12、sit(); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。InOrderTraverse(T， vsit(); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。PostOrderTraverse(T，visit(); 初始条件：二叉树T存在，visit 是对结点操作的应用函数。 操作结果：后序遍历 T，对每个结点调用函数 visit 一次

13、且仅一次。一旦 visit() 失败，则操作失败。 第六章 树和二叉树 LevelOrderTraverse(T，visit(); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。加工型操作 ClearBiTree( 初始条件：二叉树 T 存在。 操作结果：将二叉树 T 清为空树。Assign( 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：结点 e 赋值为 value。第六章 树和二叉树 InsertChild( 初始条件：二叉树 T 存在，p 指

14、向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空。 操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点原有左或右子树成为 c 的右子树。DeleteChild( 初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。 操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。 第六章 树和二叉树 la、b两棵二叉树相同吗？为什么？AFGE DCBAFCGE DB(a)(b)第六章 树和二叉树 l二叉树的基本形态ABAABACB(a) 空二叉树(b) 只有根结 点的二叉树

15、(c) 左右子树都 非空的二叉树(e) 左子树为 空的二叉树(d) 右子树为 空的二叉树第六章 树和二叉树 问：具有3个结点的二叉树可能有几种不同 形态？ 答：有5种第六章 树和二叉树 二叉树的性质l性质1：在二叉树的第i层上至多有( )个 结点( i1)2i-1证明：用归纳法 当i=1时，只有一个根结点，2i-1 = 20 = 1，命题 成立。 现在假设当 j i1时命题成立，即第 i1层上 至多有2i-2 个结点。 由于二叉树的每个结点最多有两棵子树，那么 在第 i层上的结点数目为第 i1层上最大结点 数的 2 倍，即 22i-2 2i-1。 由此证明命题。第六章 树和二叉树 l性质2：深

16、度为 k 的二叉树至多有( ) 个结点（k1)。2k-1证明如下：深度为 k 的二叉树的最大结点数目为二叉 树中每层上的最大结点数之和，第1层到第k 层的最大结点数之和为：20+ 21 + 22+ + 2k-1= (1-2k)/(1-2) = 2k-1第六章 树和二叉树 l性质3：对任何一棵二叉树 T，如果其终 端结点数为 n0，度为2的结点数为 n2， 则 ( )。证明：l设 n1为二叉树 T 中度为 1的结点数，又因为 二叉树中所有结点的度都 2，所以二叉树中 结点总数 n 为： n n0 n1 n2 （1）l再看二叉树中的分支数：除根结点外，每个结 点都有一个分支进入，设B为分支总数，则nB1 （2）l由于这些分支是由度为 1 或 2 的结点射出的 ，所以又有： Bn1 2n2 （3）l由（1）、（2）、（3）可得： n0n21。