二叉树的性质

性质一:二叉树的第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

性质四: 

 

上一篇:Vue 3响应式系统全解析:深入ref、reactive、computed、watch及watchEffect-四、watch


下一篇:OpenHarmony鸿蒙南向开发案例:【智能门铃】