二叉树的性质
- 在二叉树的第i层最多有
2i−1个节点(
i≥1),其中i为层数
- 深度为k的二叉树最多多有
2k−1个节点(
k≥1),其中k为树的深度
- 对于任意一棵二叉树,如果其叶节点为
n0, 度为二的节点
n2, 则有
n0=n2+1
如果树为满二叉树(节点只能在最大的两层出现)
- 具有n个节点的完全二叉出的深度为
⌊log2n⌋+1
- 如果对一棵有n个节点的完全二叉树的节点按层序编号, 则对任意节点i有:
- 如果i=1则节点i是二叉树的根, 无双亲; 如果i>1则其双亲节点是
⌊i/2⌋
- 如果2i>n, 则i节点无左孩子(i为叶子节点); 否则其左孩子是节点
2i
- 如果2i+1>n, 则i无右孩子; 否则其右孩子
2i+1
想透彻理解知识需要不断问为什么, 这样才可以深刻记忆和理解知识. 下面是一点随想.
为什么二叉树第i层最多有
2i−1个节点??
二叉树, 它最基本的定义是, 一棵最多有两个子节点(孩子)的树, 且它的左右孩子是有序的.
如果是一块满二叉树, 那么, 第一层有1节点, 第二层有2个节点, 第三层有4个节点…可以推出第四层有8个节点…
即1 2 4 8…
根据二叉树的性质又可以表示为:
20212223.... 它是一个等比数列, 它的q=2, 这是一个很有意义的等比数列.
满二叉树的每一次就代表了二叉树每一层节点的最大值, 因此二叉树每一层最大值是
2i−1, i是层数.
为什么深度为k的二叉树最多多有
2k−1个节点???
算满二叉树的k层就代表了, 二叉树k层最多的节点数.
求k层最大的节点的公式, 直接用等比数列前n项和公式推出来emm.
插张等比数列基本公式:
求满二叉树前n层节点的和, 已知
a1=1和q=2, 带入
sn=a1∗(1−qn)/(1−q)得
(1−2n)/(−1)
最终推得:
2n−1
ps:这里的是笔者随想而写的, 并不具有数学推理的严谨性.