数据结构(本科)辅导2.doc

数据结构(本) 教学辅导六 1 第6章树和二叉树树是一种重要的非线性结构, 从逻辑角度看, 其数据元素之间体现的是一对多的非线性关系,一切具有层次关系的问题都可以用树来描述。一、相关术语树、二叉树、树根、子树、有序树、无序数、森林、终端结点(叶子) 、非终端结点、结点的度、结点的层次、树的深度、满二叉树、完全二叉树、理想二叉树、孩子、双亲、左孩子、右孩子、先序遍历、中序遍历、后序遍历、层次遍历、哈夫曼树、最优二叉树、路径、路径长度、权、带权路径长度、哈夫曼编码。二、树的概念树的定义树的递归定义: 树(Tree) 是 n(n ≥ 0) 个结点的有限集 T,T 为空时称为空树,否则它满足如下两个条件: (1) 有且仅有一个特定的称为根(Root) 的结点; (2) 其余的结点可分为 m(m ≥ 0) 个互不相交的子集 T l,T 2,…,T m, 其中每个子集本身又是一棵树,并称其为根的子树(Subree) 。注意: 树的递归定义刻画了树的固有特性: 一棵非空树是由若干棵子树构成的, 而子树又可由若干棵更小的子树构成。三、二叉树的定义二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式, 即使是一般的树也能简单地转换为二叉树, 而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。(1 )二叉树与无序树不同二叉树中,每个结点最多只能有两棵子树,并且有左右之分。二叉树并非是树的特殊情形,它们是两种不同的数据结构。(2 )二叉树与度数为 2 的有序树不同在有序树中,虽然一个结点的孩子之间是有左右次序的,但是若该结点只有一个孩子, 就无须区分其左右次序。而在二叉树中,即使是一个孩子也有左右之分。四、二叉树的存储结构(一) 顺序存储结构该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。 1 .完全二叉树结点编号(1) 编号办法在一棵 n 个结点的完全二叉树中, 从树根起, 自上层到下层, 每层从左至右, 给所有结点编号,能得到一个反映整个二叉树结构的线性序列。数据结构(本) 教学辅导六 2 【例】如下图所示。(2) 编号特点完全二叉树中除最下面一层外, 各层都充满了结点。每一层的结点个数恰好是上一层结点个数的 2 倍。从一个结点的编号就可推得其双亲,左、右孩子,兄弟等结点的编号。假设编号为 i 的结点是 k i (1≤i≤ n) ,则有: ①若 i>1 ,则 k i 的双亲编号为[i/2] ;若 i=1 ,则 K i 是根结点,无双亲。②若 2i≤n ,则 K i 的左孩子的编号是 2i ;否则, K i 无左孩子,即 K i 必定是叶子。因此完全二叉树中编号 i>[n/2] 的结点必定是叶结点。③若 2i+1 ≤n ,则 K i 的右孩子的编号是 2i+1 ;否则, K i 无右孩子。④若i 为奇数且不为 1 ,则 K i 的左兄弟的编号是 i-1 ;否则, K i 无左兄弟。⑤若i 为偶数且小于 n ,则 K i 的右兄弟的编号是 i+1 ;否则, K i 无右兄弟。 2 .完全二叉树的顺序存储将完全二叉树中所有结点按编号顺序依次存储在一个向量 bt[0..n] 中。其中: bt[1 .. n] 用来存储结点 bt[0] 不用或用来存储结点数目