如果节点总数在 O(1) 中给出，则查找完全二叉树的左子树和右子树中的节点数

Question

如果给定总节点数，我想找到完全二叉树的左子树和右子树中的节点数，

例如，

n = 5 ===> 左 -> 3 右 -> 1

n = 8 ===> 左 -> 4 右 -> 3

其中 n 是二叉树中的节点总数

是否有任何公式或 O(1)/最佳解决方案可以做到这一点？

Answer 1

is there any formula or O(1)/optimal solution to do this?

是的。

用二进制表示法写出给定的（节点数），并将每个 1 变为 0，除了最重要的 1。称这个数字为 。定义为 − ，因此在二进制中它与 相同，但删除了最高有效位。 right 子树中的节点数将等于 max(, / 2 − 1).

然后知道左子树中有多少个小菜一碟，因为两个子树中的节点之和加1（对于根节点）必须是等于.

你的例子

当 = 5 时，我们记下来二进制为 0b101。我们可以看到 = 0b100 和 = 0b001。所以右子树有 max(, /2 − 1) 个节点，即 max(1, 1) = 1。左子树有剩余的节点，即 3，所以 3 + 1 + 1（对于根）= 5。

其他例子

这是一个 table，结果介于 1 和 15 之间：

	in binary			/2 − 1	in right subtree = max(, /2 − 1)	in left subtree
1	0b1	0b1	0b0	0b0	0	0
2	0b10	0b10	0b0	0b0	0	1
3	0b11	0b10	0b1	0b1	1	1
4	0b100	0b100	0b00	0b1	1	2
5	0b101	0b100	0b01	0b1	1	3
6	0b110	0b100	0b10	0b1	2	3
7	0b111	0b100	0b11	0b1	3	3
8	0b1000	0b1000	0b000	0b11	3	4
9	0b1001	0b1000	0b001	0b11	3	5
10	0b1010	0b1000	0b010	0b11	3	6
11	0b1011	0b1000	0b011	0b11	3	7
12	0b1100	0b1000	0b100	0b11	4	7
13	0b1101	0b1000	0b101	0b11	5	7
14	0b1110	0b1000	0b110	0b11	6	7
15	0b1111	0b1000	0b111	0b11	7	7