《教学课件第2节二叉树及其基本性质》由会员分享，可在线阅读，更多相关《教学课件第2节二叉树及其基本性质（12页珍藏版）》请在金锄头文库上搜索。
1、第五章 树和二叉树 5.2 二叉树及其基本性质123114589126710一、二叉树的定义 二叉树是n(n=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的，互不相交的二叉树构成。1231145891267101329761211854105.2 二叉树及其基本性质（一）二叉树的特点 每个结点至多有二棵子树(即不存在度大于2的结点)； 二叉树的子树有左、右之分，且其次序不能任意颠倒。AABABABC（二）二叉树的五种基本形态1.空二叉树2.只有根结点的二叉树3.右子树为空4.左子树为空5.左、右子树均非空5.2 二叉树及其基本性质二、二叉树的基本特性性质
2、性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1)证明：用归纳法证明之 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-15.2 二叉树及其
3、基本性质性质性质 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+15.2 二叉树及其基本性质三、满二叉树与完全二叉树123114589121367101415第层上有2k-1个结点；深度为的
4、满二叉树有2m-1个结点。5.2 二叉树及其基本性质（一）满二叉树的定义除最后一层外，每一层上的所有结点都有两个子结点。特点：每一层上的结点数都是最大结点数5.2 二叉树及其基本性质（二）完全二叉树的定义除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 特点： 1.叶子结点只可能在层次最大的两层上出现; 2.对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1。1231145891213671014151231145891267101234567123456（三）满二叉树与完全二叉树的性质性质性质 ： 具有 n 个结点的完全二叉树的深度深度为log2n+ 1 证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。
