二叉树的5种形态: 人△人△
• 二叉树的5种形态： ø (a) (b) (c) (d) (e)
621二叉树的类型定义 ADT Binary Tree i 数据对象:D是具有相同特性的数据元素的集 数据关系: 若D为空集,称 Binary Tree为空二叉树; 否则关系R=H} 在D中存在唯一的称为根的数据元素 root,它在关系H下无前驱; (2)D中其余元素必可分为两个互不相交的子 集L和R,每一个子集都是一棵符合本定义的二叉 树。如 左子树 L木空,则必存在一个根结点,它是roo的”左后 <root>∈H,如果右子树R不空,则必存在 根结点为root的右后继"<root,>∈H)
6.2.1 二叉树的类型定义 ADT BinaryTree { 数据对象：D 是具有相同特性的数据元素的集 合。 数据关系： 若 D 为空集，称 BinaryTree 为空二叉树； 否则 关系 R={H}： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子 集 L 和 R，每一个子集都是一棵符合本定义的二叉 树，并分别为 root 的左子树和右子树。如果左子树 L 不空，则必存在一个根结点 ，它是 root 的"左后 继"(<root, >∈H)，如果右子树 R 不空，则必存在一 个根结点 为 root 的"右后继"(<root, >∈H)
根结点 左子树 右子树 C E F J
基本操作P: {结构初始化} InitBiTree(&T); 操作结果:构造空二叉树T。 Create BiTree(&T, definition) 初始条件: definition给出二叉树T的定义。 操作结果:按 definition构造二叉树T。 {销毁结构} Destroy BiTree(&T) 初始条件:二叉树T存在。 操作结果:销毁二叉树T
• 基本操作P： {结构初始化} InitBiTree(&T); 操作结果：构造空二叉树 T。 CreateBiTree(&T, definition); 初始条件：definition 给出二叉树 T 的定义。 操作结果：按 definition 构造二叉树 T。 {销毁结构} DestroyBiTree(&T); 初始条件：二叉树 T 存在。 操作结果：销毁二叉树 T
引用型操作 BiTree Empty (T 初始条件:二叉树T存在。 操作结果:若T为空二叉树,则返回TRUE,否 则返回 FALSE。 BiTreeDepth(T) 初始条件: 树T存在 操作结果:返回T的深度。 Root(T) 初始条件:二叉树T存在 操作结果:返回T的根。 Value(T, e 初始条件:二叉树T存在,e是T中某个结点 操作结果:返回e的值
• {引用型操作} BiTreeEmpty(T); 初始条件：二叉树 T 存在。 操作结果：若T为空二叉树，则返回 TRUE，否 则返回 FALSE。 BiTreeDepth(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的深度。 Root(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的根。 Value(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的值