【数据结构】树.pptVIP

第6章 树(6学时) 树 二叉树 树和森林 哈夫曼树及应用 6.1 树 树形结构是一类重要的非线性结构，树形结构是结 点之间有分支、分层关系的结构。 树的定义：树是n(n≥0)个结点的有限集。 它满足以下两个条件： （1）有且仅有一个特定的称为根的结点。 （2）其余的结点可分为m个互不相交的有限集合T1, T2,…,Tm，其中，每个集合又都是一棵树（子 树）。 树的表示 6.1 树 结点的度：一个结点的子树个数称为该结点的度。 树的度：一棵树中结点度的最大值。 叶子（终端结点）：度为0的结点。 分支结点（非终端结点）：度不为0的结点。 内部结点：除根结点之外的分支结点。 孩子：树中某个结点的子树的根称为个结点的孩子。 双亲：该结点则为孩子的双亲。 兄弟：同一个双亲的孩子。 路径：若树中存在一个结点序列k1,k2,…,kj，使得ki是ki+1的双亲 (1≤ij)，称该结点序列是从k1到kj的一条路径。 祖先：若树中结点k到ks存在一条路径，则称k是ks的祖先。 子孙：ks是k的子孙。 6.1 树 层次：结点的层次是从根开始算起(根为1层)。 高度：树中结点的最大层次称为树的高度或深度。 有序树：若将树中每个结点的各子树看成是从左到右有 秩序的。 无序树：否则称为无序树。 森林：是m(m≥0)棵互不相交的树的集合。 (树形结构的逻辑特征可用树中结点之间的父子关系来描述) 6.1 树 树的基本操作有下列几种： （1）初始化操作。 （2）求根函数。 （3）求双亲函数。 （4）求孩子结点函数。 （5）求右兄弟函数。 （6）建树函数。 （7）插入子树操作。 （8）删除子树操作。 （9）遍历操作。 （10）清除结构操作。 6.2 二叉树 概念 性质 存储结构 遍历 线索化 6.2 二叉树 概念 定义：二叉树是个结点的有限集，它或者是空集， 或者由一个根结点及两棵不相交的分别称作 这个根的左子树和右子树的二叉树组成。 二叉树的五种基本形态 6.2 二叉树 二叉树的性质 1、二叉树第i层上的结点数目最多为2i-1(i≥0)。 归纳法证明： 归纳基础：i=1时，有2i-1=20=1。 归纳假设：假设对所有的j(1≤ji)命题成立，即第j层上至多 有2j-1个结点，证明j=i时命题成立。 归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点，由于 二叉树的每个结点至多有两个孩子，故第i层上的 结点至多是第i层上的最大结点数的2倍，即j=i时 该层上至多有2*2i-2=2i-1个结点，故命题成立。 6.2 二叉树 2、深度为k的二叉树至多有2k-1个结点。 证明：在具有相同深度的二叉树中，仅当每一层都含有最多结点时， 其树中结点数最多。因此，利用性质1可得，深度为的二叉树 中至多含有的结点数为： 20+21+…+2k-1=2k-1 故命题正确。 3、在任意一棵二叉树中，若终端结点的个数为n0，度为2 的结点数为n2，则n0=n2+1。 证明：因为二叉树中所有结点的度数均不大于2，所以结点总数应等 于0度结点数、1度结点数和2度结点数之和，即： n=n0+n1+n2 ① 6.2 二叉树 另一方面，1度结点有一个孩子，2度结点有两个孩子。所以， 二叉树中孩子结点总数是n1+2n2，二叉树中只有根结点不是任何结点 的孩子，故二叉树中的结点总数又可以表示为： n=n1+2n2+1 ② 由式①和式②得到： n0=n2+1 两种特殊形式的二叉树： 满二叉树：一棵深度为k且有2k-1个结点的二叉树。 完全二叉树：若一棵二叉树至多只有最下面两层上结点的度数可以 小于2，并且最下层上的结点都集中在该层最左边的若 干位置上，则此二叉树称为完全二叉树。 6.2 二叉树 4、具有n个结点的完全二叉树的深度为log2n +1 证明：设所有完全二叉树的深度为k，由完全二叉树的定义可知，它