英文:
Number of nodes in the two subtrees of a complete binary tree
问题
There is indeed a mathematical formula to calculate the number of nodes in the left (L) and right (R) subtrees of a complete binary tree, given the total number of nodes (N). You can use the following formulas:
h = floor(log2(N)) // Calculate the height of the tree
L = min(N - 2^(h) + 1, 2^(h-1)) // Calculate the number of nodes in the left subtree
R = N - 1 - L // Calculate the number of nodes in the right subtree
These formulas will give you the values of L and R programmatically based on the total number of nodes, N.
英文:
Is there a mathematical formula to calculate the number of nodes in the Left and Right of a complete binary tree?
There exists a similar problem on Stack Overflow - Find number of nodes in left and right subtree of a complete binary tree if total number of nodes are given in O(1).
But here I want to calculate the number of nodes in the left (L) and right (R) subtreee of a complete binary Tree programmatically.
I suspect there must be a concrete math formula to calculate L and R, given N, where N is the total number of nodes. Does anyone know of it?
I've been trying to calculate the height of the binary tree and then use height to calculate L and R, but I'm unsuccessful so far.
This is what I tried, but it's wrong:
h = math.floor(math.log(N,2))
L = min(N-1, 1+2**(h-1))
R = N - 1 - L
答案1
得分: 1
让 ℎ 为树的高度，即根到最左叶子节点路径上的边数。对于给定的节点数 𝑛，我们有 ℎ=⌊log<sub><sub>2</sub></sub>𝑛⌋
对于给定的高度 ℎ，左子树中的节点最小数为 𝑛=2<sup>ℎ−1</sup>。
具有 𝑛 节点的树左子树中的实际节点数为 𝑛 + min(𝑛−1, 2𝑛)。
右子树中节点数可由此派生，因为两个子树中节点数之和应为 𝑛−1。
以下是JavaScript中的实现代码，并且该公式在 𝑛 介于1和16之间运行：
<!-- begin snippet: js hide: false console: true babel: false -->
<!-- language: lang-js -->
// This function returns two integers (as array):
// the sizes of the two subtrees given the number of nodes in a complete binary tree
function subTreeSizes(n) {
if (n < 2) return [0, 0]; // There are no left/right subtrees
const height = Math.floor(Math.log2(n)); // Number of edges on leftmost path
const minLeftSize = 1 << (height - 1);
const leftSize = minLeftSize + Math.min(minLeftSize - 1, n - 2*minLeftSize);
const rightSize = n - 1 - leftSize;
return [leftSize, rightSize];
}
console.log("Nodes, left size, right size:");
for (let n = 1; n <= 17; n++) {
console.log(n, ...subTreeSizes(n));
}
<!-- end snippet -->
英文:
Let ℎ be the tree's height, i.e. the number of edges on the root-to-leftmost-leaf path. For a given number of nodes 𝑛, we have ℎ=⌊log<sub><sub>2</sub></sub>𝑛⌋
For a given height ℎ the minimum number of nodes in the left subtree is 𝑚=2<sup>ℎ−1</sup>.
The actual number of nodes in the left subtree of a tree with 𝑛 nodes is 𝑚 + min(𝑚−1, 𝑛−2𝑚).
The number of nodes in the right subtree can be derived from that, since the sum of the nodes in both subtrees should be 𝑛−1.
Here is an implementation in JavaScript, and the formula is run for 𝑛 between 1 and 16:
<!-- begin snippet: js hide: false console: true babel: false -->
<!-- language: lang-js -->
// This function returns two integers (as array):
// the sizes of the two subtrees given the number of nodes in a complete binary tree
function subTreeSizes(n) {
if (n < 2) return [0, 0]; // There are no left/right subtrees
const height = Math.floor(Math.log2(n)); // Number of edges on leftmost path
const minLeftSize = 1 << (height - 1);
const leftSize = minLeftSize + Math.min(minLeftSize - 1, n - 2*minLeftSize);
const rightSize = n - 1 - leftSize;
return [leftSize, rightSize];
}
console.log("Nodes, left size, right size:");
for (let n = 1; n <= 17; n++) {
console.log(n, ...subTreeSizes(n));
}
<!-- end snippet -->
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论