性质一:二叉树的第i层上最多有2^(i-1) 个节点
性质二:深度为k的二叉树最多有2^(k)-1个节点
等比数列求和公式:
直接套进去就得到 2^(k)-1
(结点的度(Degree) :结点子树的个数。
树的度: 树中结点的最大度数。度为k的树也称为k叉树)
性质三:叶子结点数n0,度为2的结点数n2,满足n0 = n2 + 1
推导:整颗树的节点n = n0(叶子结点)+n1(只有一个子树的节点)+n2(有两个子树的节点)
证明:
假设二叉树的0度,1度,2度结点为n0,n1,n2总结点为n
按照结点求和: n = n0+n1+n2 [1]
除了根节点之外,其余的任何节点都有一个入口分,n-1 = 2*n2+n1*1
性质四: