《第2节二叉树及其基本性质课件》由会员分享，可在线阅读，更多相关《第2节二叉树及其基本性质课件（12页珍藏版）》请在金锄头文库上搜索。
1、第五章 树和二叉树,5.2 二叉树及其基本性质,一、二叉树的定义 二叉树是n(n=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的，互不相交的 二叉树构成。,5.2 二叉树及其基本性质,（一）二叉树的特点,每个结点至多有二棵子树(即不存在度大于2的结点)； 二叉树的子树有左、右之分，且其次序不能任意颠倒。,A,（二）二叉树的五种基本形态,1.空二叉树,2.只有根结点的二叉树,3.右子树为空,4.左子树为空,5.左、右子树均非空,5.2 二叉树及其基本性质,二、二叉树的基本特性,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),证明：用
2、归纳法证明之 i=1时，只有一个根结点，2i-1=20=1 是对的; 假设对所有j(1ji)命题成立，即第j层上至多有2j-1 个结点 那么，第i-1层至多有2i-2 个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即22i-2=2i-1 故命题得证,5.2 二叉树及其基本性质,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：深度为k的二叉树是指二叉树共有k层。 由性质1，可得深度为k 的二叉树最大结点数是 21-1+22-1+2k-1=2k-1,5.2 二叉树及其基本性质,性质 3 ： 对任何一棵二叉树，度为0的叶子结点总是比度为 2
3、 的结点多一个，则必存在关系式：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 二叉树及其基本性质,三、满二叉树与完全二叉树,第层上有2k-1个结点； 深度为的满二叉树有2m-1个结点。,5.2 二叉树及其基本性质,（一）满二叉树的定义 除最后一层外，每一层上的所有
4、结点都有两个子结点。 特点：每一层上的结点数都是最大结点数,5.2 二叉树及其基本性质,（二）完全二叉树的定义 除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 特点： 1.叶子结点只可能在层次最大的两层上出现; 2.对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1。,（三）满二叉树与完全二叉树的性质,性质 ： 具有 n 个结点的完全二叉树的深度为log2n + 1,证明： 设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为 k 只能是整数，所以， log2n取其整数部分 log2n 得： k =log2n + 1 。,5.2 二叉树及其基本性质,性质5： 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点； (2) 若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该 结点无右孩子结点， 否则，编号为2i+1 的 结点为其右孩子结点。,
