二叉树及其基本性质.pptVIP

第五章 树和二叉树 §5.2 二叉树及其基本性质 1 2 3 11 4 5 8 9 12 6 7 10 一、二叉树的定义 二叉树是n(n〉=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的，互不相交的 二叉树构成。 1 2 3 11 4 5 8 9 12 6 7 10 1 3 2 9 7 6 12 11 8 5 4 10 §5.2 二叉树及其基本性质 （一）二叉树的特点 ——每个结点至多有二棵子树(即不存在度大于2的结点)； ——二叉树的子树有左、右之分，且其次序不能任意颠倒。 A ? A B A B A B C （二）二叉树的五种基本形态 1.空二叉树 2.只有根结点的二叉树 3.右子树为空 4.左子树为空 5.左、右子树均非空 §5.2 二叉树及其基本性质 二、二叉树的基本特性 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1) 证明：用归纳法证明之 ?i=1时，只有一个根结点，2i-1=20=1 是对的; ?假设对所有j(1?ji)命题成立，即第j层上至多有2j-1 个结点 那么，第i-1层至多有2i-2 个结点 又二叉树每个结点的度至多为2 ? 第i层上最大结点数是第i-1层的2倍，即2×2i-2=2i-1　 故命题得证 §5.2 二叉树及其基本性质 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。 证明：深度为k的二叉树是指二叉树共有k层。 由性质1，可得深度为k 的二叉树最大结点数是 21-1+22-1+…+2k-1=2k-1 §5.2 二叉树及其基本性质 性质 3 ： 对任何一棵二叉树，度为0的叶子结点总是比度为 2 的结点多一个，则必存在关系式：n0 = n2+1。 证明：n1为二叉树T中度为1的结点数 因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个分支进入。设m为分支总数，则二叉树中总结点数又为：n=m+1 又：分支由度为1和度为2的结点射出，?m=n1+2n2 于是，n=m+1=n1+2n2+1=n0+n1+n2 所以：n0=n2+1 §5.2 二叉树及其基本性质 三、满二叉树与完全二叉树 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 ——第ｋ层上有2k-1个结点； ——深度为ｍ的满二叉树有2m-1个结点。 §5.2 二叉树及其基本性质 （一）满二叉树的定义 　——除最后一层外，每一层上的所有结点都有两个子结点。 　特点：每一层上的结点数都是最大结点数 §5.2 二叉树及其基本性质 （二）完全二叉树的定义 　——除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 特点： 1.叶子结点只可能在层次最大的两层上出现; 2.对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1。 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6 7 1 2 3 4 5 6 （三）满二叉树与完全二叉树的性质 性质４ ： 具有 n 个结点的完全二叉树的深度为?log2n? + 1 证明： 设完全二叉树的深度为 k 则根据第二条性质得 2k-1≤ n 2k 即 k-1 ≤ log2 n k 因为 k 只能是整数，所以， log2n取其整数部分 ?log2n?　 　得： k =?log2n? + 1 。 §5.2 二叉树及其基本性质 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 性质5： 　　若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 ?i/2? 的结点为其双亲结点； (2) 若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该 结点无右孩子结点， 否则，编号为2i+1 的 结点为其右孩子结点。