数据结构树和二叉树C.ppt

6.1 树的定义和基本术语 1.树的逻辑定义 是由n(n ≥ 0)个结点组成的有限集合T。 在任意一个非空树中： ? 有且仅有一个特定的称为根的结点； ? n 1时，其余结点可以分为m（m 0）个互不相交的有限集T1,T2,T3 ,…,Tm，其中每一个集合本身又是一棵树，且称为根的子树。 树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它说明了树的特性。 2.树的其它表示方法 嵌套集合：是一些集合的集体，对于其中任何两个集合，或不相交，或一个包含另一个的形式表示。 广义表表示：根作为由子树森林组成的表的名字写在表的左边。 凹入表示：类似书的编目。 3.树的基本术语 结点：数据元素+若干指向其子树的分支； 结点的度：结点拥有的子树数； 树的度：树中所有结点的度的最大值； 叶子结点：度为零的结点，或称为终端结点； 分支结点：度大于零的结点，或称为非终端结点； 结点的层次：假设根结点的层次为1, 若某结点在第i层，则其子树的根在第i+1层； 3.树的基本术语 树的深度：树中叶子结点所在的最大层次； 孩子结点：结点的子树的根；相应地该结点称为孩子的双亲结点； 兄弟结点：同一个双亲的孩子之间称为兄弟结点； 祖先：从根到该结点所经分支上的所有结点； 子孙：子树中任一结点； 3.树的基本术语 有序树、无序树 子树之间是否存在次序关系？ 将树中结点的各子树看成从左至右是有次序的(即不能互换) 称有序树，否则称无序树； 森林：是m（m≥0）棵互不相交的树的集合。 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root被称为根结点，F被称为子树森林； 5.树的抽象类型定义 ADT List { 数据对象D：是具有相同特性的数据元素的集合 数据关系R：数据关系R：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则 R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}!=Φ，则存在 D-{root}的一个划分D1，D2，…，Dm (m0)，对任意j≠k(1≤j，k≤m)有Dj∩Dk=Φ，且对任意的 i(1≤i≤m)，唯一存在数据元素xi∈Di，有root，xi∈H； 5.树的抽象类型定义 ADT List { 数据关系R： (3) 对应于 D-{root}的划分，H-{root，x1，…，root，xm} 有唯一的一个划分 H1，H2，…，Hm(m0)，对任意j≠k(1≤j，k≤m)有 Hj∩Hk=Φ，对任意 i(1≤i≤m)，Hi是Di上的二元关系，(Di，{Hi})是一棵符合本定义的子树，称为根root的子树。 基本操作： } ADT List 树的基本操作 1）Root(T);初始条件：树T存在；操作结果：返回T的根 2）Value(T, cur_e); 初始条件：树T存在， cur_e是T中某个结点 操作结果：返回cur_e的值 3）Parent(T, cur_e); 初始条件：树T存在， cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双 亲，否则其函数值为“空”。 4）TreeDepth(T); 初始条件：树T存在；操作结果：返回T的深度。 5）LeftChild(T, cur_e); 初始条件：树T存在， cur_e是T中某个结点 操作结果：若cur_e是T的非叶子结点，则返回它的最 左孩子，否则其函数值为 “空” 6）RightSibling(T, cur_e); 初始条件：树T存在， cur_e是T中某个结点 操作结果：若cur_e有右兄弟，则返回它的右兄弟， 否 则其函数值为“空” 7）TreeEmpty(T); 初始条件：树T存在 操作结果：判别T是否为空树 8) TraverseTree(T, Visit()); 初始条件：树T存在。Visit是对结点操作的函数。 操作结果：按某种次序对T的每个结点调用函数 Visit()一次且至多一次 9）InitTree(T); 操作结果：构造空树T 10）Assign(T, cur_e, value); 初始条件：树T存在， cur_e是T中某个结点。 操作结果：结点cur_e赋值value。 11）DestroyTree(T); 初始条件：树T存在 操作结果：销毁树T 6.2.1 二叉树的定义 或者为空树；或者是