数据结构学习指导第5章树.docxVIP

第五章 树本章要点一、树的概念1. 树（树型结构的简称）的定义树是n≥0个有限元素的集合T，当n=0时，称为空树。在一棵非空树中，1) 有且仅有一个特殊结点称为树的根（root）。2) 若n0，除根结点外的其余元素可分成m个不相交的子树，T1、T2 ……Tm。3) 每棵子树又同样是一棵树。4) 由此，树的定义是递归的，所以树是一种递归的数据结构。5) 树的二元组定义：tree=（K，R）K={kI|1≤i≤n，n≥0，ki∈ElemType}R={r}其中r满足下列条件：(1) 有且仅有一个结点没有前驱，该结点为树的根；(2) 除根结点之外，每个结点只有一个前驱结点；(3) 每个结点可以有多个后继结点。2. 树的表示方法树形表示法、集合表示法、凹入表示法、广义表表示法3. 树的基本术语1) 结点的度和树的度每个结点具有的子树数或者说后继结点数被定义为结点的度（degree）。所有结点的度的最大值定义为树的度。2) 分支结点和叶子结点度大于0的结点称为分支结点或非终端结点；度等于0的结点称为叶子结点或终端结点；在分支结点中，又把度为1的结点称为单分支接点；度为2的结点称为双分支结点。3) 孩子结点、双亲结点和兄弟结点4) 结点的层数和树的深度结点的层数（level）从树根开始定义：树的根结点的层数为1。其余结点的层数=其双亲层数+1树中结点的最大层数称为树的深度（depth）或高度（height）5) 森林M（M≥0）棵互不相交的树的集合。6) 有序树和无序树一般情况下认为树是有序的。4. 树的性质(P182)二、二叉树的定义1. 二叉树(binary tree)二叉树是一种特殊的树型结构，树中的每个结点至多有两棵子树（左子树和右子树，即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。2. 二叉树分类二叉树的性质的特征值的不同，可将二叉树分为以下几种基本形态：1) 满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的二叉树的称为满二叉树。特点：第i层的结点数为2i-1：P184图5－7(a)。2) 完全二叉树：除最后一层外其余层都是满的，并且最后一层是在右侧缺少连续若干个结点：P184图5－7 (b)。一棵深度为K的有N个结点的二叉树，对树中的结点按从上至下、从左至右顺序进行编号，如果编号 i的结点与满二叉树编号i 的结点在二叉树中位置相同，则称这棵树为完全二叉树。其特点如下：?叶子结点只能在层数最大的两层上出现。?对任一结点，若其右子树的最大层次为L，则其左子树的最大层次为L或L+1。?完全二叉树除最后一层外，各层都充满了结点，每一层的结点个数恰好是上一层结点个数的2倍。3) 理想平衡树：除最后一层外其余层都是满的，并且最后一层的结点可以任意分布：P186图5－8(a)。4) 普通二叉树：不受以上各条件约束：P186图5－8 (b)。三、二叉树的性质(P184)性质1：二叉树第i层上的结点数目最多为2i-1。（i≥1）性质2：深度为K的二叉树至多有2K-1。性质3：对于任意一棵非空的二叉树，如果叶子结点数为n0，度为2的结点数为n2，则有：n0= n2+1。性质4：具有n个结点的完全二叉树其深度为 log2n +1或 log2 (n+1)。?性质5：在具有n个结点的完全二叉树中，设ki是编号为i的结点1) 若i1，则ki的双亲编号为i/2；若i=1，则无双亲。2) 若2i≤n，则ki的左孩子编号是2i，否则无左孩子。因此，完全二叉树中编号in/2?的结点必定是叶结点。3) 若2i+1≤n，则ki的右孩子编号是2i+1，否则无右孩子。4) 若i为奇数且不为1，则ki的左兄弟编号为i-1，否则无左兄弟。5) 若i为偶数且小于n，则ki的右兄弟编号为i+1，否则无右兄弟。四、二叉树的存储结构1. 顺序存储结构顺序存储结构即用一组连续的存储单元存放二叉树中的结点。例，对满二叉树和完全二叉树，树中结点的序号可以唯一地反映出结点之间的逻辑关系，所以可用一维数组按从上至下、从左至右的顺序存储。但是，对于一般二叉树，则需对之进行改造，增添一些不存在的空结点，使之成为一棵完全二叉树形式。此种存储结构适用于理想二叉树，定义略。2. 链接存储结构类型定义1) 定义数据域的数据类型；2) 定义数据为通用数据类型(ElemType)；3) 定义每个结点类型struct BtreeNode{ElemType data;BTreeNode *left;BTreeNode *right;};4) 定义树根指针：BT五、二叉树的抽象数据类型: P186六、二叉树的运算（BTree.h）1. 初始化2. 二叉树的建立二叉树的输入格式不同，建立二叉树的算法也不同，我们采用广义表方