⼆叉树结点的计算
⼆叉树结点的计算
1. ⼆叉树的第 i 层上⾄多有 2^(i-1) 个结点 (i >= 1)
2. ⼀个⼆叉树的层数为k，且结点总数是(2^k) -1 ，则它就是满⼆叉树； 深度为 k 的⼆叉树⾄多有 (2^k) -1 个结点( k >= 1)
3. 对任意的⼀颗⼆叉树 Tree，若叶⼦结点数为 n0,⽽其度数为 2 的结点数为 n2，则 n0 = n2+1
4. 具有 n 个结点的完全⼆叉树的深度 [log2n]+1
5. 如果有⼀颗有n个节点的完全⼆叉树的节点按层次序编号，对任⼀层的节点i（1 <= i <= n）有
(1).如果 i = 1，则节点是⼆叉树的根，⽆双亲，如果 i > 1，则其双亲节点为 [ i /2 ]，向下取整
(2).如果2i > n那么节点 i 没有左孩⼦，否则其左孩⼦为 2i
(3).如果 2i + 1 > n那么节点没有右孩⼦，否则右孩⼦为 2i + 1
6. n 层⼆叉树的第n层最多为 2^(n-1) 个
二叉树公式
7. ⼆叉树节点计算公式 N = n0+n1+n2，度为0的叶⼦节点⽐度为2的节点数多⼀个，N=1n1+2n2+1
8. 满⼆叉树是指除最后⼀层外，每⼀层上的所有结点有两个⼦结点，则 k 层上有 2k-1 个结点深度为m的满⼆叉树有 2m-1 个结点以上是⼆叉树中有关的计算⽅法，在笔试中可能会⽤到，如果有什么错误，请⼤家留⾔，谢谢

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。