二叉树的性质
二叉树具有以下重要性质： 性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。 证明：用数学归纳法证明： 　    归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。     　归纳假设：假设对所有的j(1≤j 证明：设所求完全二叉树的深度为k。由完全二叉树定义可得： 　　深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。 由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：                   n>2k-1-1。     　另一方面，由性质2可得：                   n≤2k-1，        即：2k-1-l

自动ftp脚本 你了解自己吗？

评论 (0) All

登陆 还没注册？