数据结构第六章树和二叉树1.ppt

第六章 树和二叉树;对比树型结构和线性结构的结构特点;6.1 树的类型定义;结点:;孩子结点：结点的子树的根称为该结点的孩子 双亲结点：B 结点是A 结点的孩子，则A结点是B结点的双亲 兄弟结点：同一双亲的孩子之间互称兄弟 堂兄弟结点：其双亲在同一层的结点互称堂兄弟 祖先结点：从根到该结点所经分支上的所有结点 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙;孩子结点 双亲结点 兄弟结点 堂兄弟结点 祖先结点 子孙结点;有序树： 子树之间存在确定的次序关系。 最左边子树的根称为第一个孩子； 最右边子树的根称为最后一个孩子。;任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林;A;ADT Tree {数据对象D：D是具有相同特性的数据元素的集合。数据关系R：　若 D 为空集，则称为空树；　若 D 中仅含一个数据元素，则关系R为空集；　否则 R={H}，　 (1) 在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱；　 (2) 当n1时，其余数据元素可分为 m(m0) 个互不相交的(非空)有限集 T1,T2,…,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根 root 的后继，即 root,xi ∈H, i=1,2,…,m。;基本操作：;{引用型操作} 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); 初始条件：树 T 存在。 操作结果：将树 T 清为空树。 InsertChild(T, p, i, c); 初始条件：树 T 存在，p 指向T中某个结点，1≤i≤(p 所指结点的度＋1),非空树 c 与 T 不相交。 操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树。 DeleteChild(T, p, i); 初始条件：树 T 存在，p 指向 T 中某个结点，1≤i≤p 指结点的度。 操作结果：删除 T 中 p 所指结点的第 i 棵子树。;定义 或为空树，或是由一个根结点和两棵互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。 特性 二叉树中每个结点最多有两棵子树；二叉树每个结点的度小于等于2 子树有左右之分，不能颠倒——有序树 二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;二叉树与度为2的树相同吗？为什么？; a、b两棵二叉树相同吗？为什么？;二叉树的五种基本形态：;二叉树的抽象数据类型定义如下：;基本操作：; 引用型操作; 引用型操作（续）; 引用型操作（续）; 引用型操作（续）; 引用型操作（续）; 引用型操作（续）; 加工型操作; 加工型操作; 加工型操作（续）;性质 1 在二叉树的第 i 层上至多有2i-1 个