数据结构（本科）辅导.doc

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