第6章树和二叉树.ppt

第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 什么是树？ 树（Tree）的例子，一个家族： A有子女B、C；B和 C分别有子女D、E、F和G、H；E有子女I、J。 T=(N, R) ，其中： N={A, B, C, D, E, F, G, H, I, J} R={A, B, A, C, B, D, B, E, B, F, C, G, C, H, E, I, E, J} 树的表示方法 6.1 树的定义和基本术语 树（Tree)的递归定义： 树是n ( n≥0 ) 个结点的有限集。如果 n = 0，称为空树； 如果 n0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱； 当n1，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1, T2 ,…, Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。 树的示例 关于子树 T={A, B, C, D, E, F, G, H, I, J, K, L, M} ，其中A是根，其余结点可以划分为3个互不相交的集合：T1={B, E, F, K, L}，T2={C, G}，T3={D, H, I, J, M} 。 T1、T2、T3都是根A的子树，且其本身又是一棵树。 树的基本术语 结点(node)：包含一个数据元素及若干指向其子树的分支。 结点的度(degree)：结点拥有子树数。 叶结点(leaf)：又称为终端结点。度为0的结点。 分支结点：度不为0的结点。又称为非终端结点。 内部结点：除了根结点与叶子结点以外的所有结点。 树的度：树内各结点的最大值。 孩子(child)：结点的子树的根称为该结点的孩子。 双亲(parent)：相应的该结点为其孩子的双亲结点。 兄弟(sibling)：同一个双亲的孩子之间互称兄弟。 祖先(ancestor)：从根到该结点所经分支上的所有结点。 子孙（descendant）：以某结点为根的子树中的任一结点都称为该结点的子孙。 路径（path）：若树中存在一个结点序列k1,k2,…,ki，使得ki是ki+1的双亲（1≤ij），则称该结点序列是从kl到kj的一条路径（Path）或道路。 路径的长度：路径所经过的边（即连接两个结点的线段）的数目，等于j-1。 树的基本术语 结点层次(level)：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第L层，则其子树的根就在第L+1层。 树的深度(高度）：树中结点的最大层次称为树的深度或高度。 有序树/无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则成为无序树。 树的基本术语 森林（Forest）：m(m≥0)棵互不相交的树的集合称为森林。 树和森林的概念相近，删去一棵树的根，就得到一个森林； 反之，加上一个结点作树根，森林就变为一棵树。 抽象数据类型树的定义 ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) (3) 基本操作P：…… } 基本操作 InitTree(T)；操作结果：构造空树T。 DestroyTree(T)；初始条件：树T存在。操作结果：销毁树T。 CreateTree(T, definition)；初始条件：definition给出树T的定义。操作结果：按definition构造树T。 ClearTree(T)；初始条件：树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的值。 Assign(T, cur_e, value)；初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。 Parent(T, cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果；若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。 LeftChild(T, cur_e)；初始条件：树T存在，cur_e是T中