我终于把它想通了。
从条件
保证每个节点E的左子树将具有与该节点E上的右子树相同或多一个节点。
可以得出以下结论:
- 非叶子节点的数量可以从树的深度计算出来;它是2的深度-1次方。因此,有趣的事情是计算叶子节点的数量。
- 考虑到平衡条件,新节点只能插入或删除现有节点的唯一位置。(这意味着给定叶子节点的数量意味着只有一种叶子节点的模式。)
- 如果我们知道节点的左子树中叶子节点的数量,则我们知道右子树中的叶子节点(和节点)的数量要么相同,要么比其少一个。
- 由2和3可知,在右子树中只有一个叶子节点槽位我们无法在检查树的情况下确定它是否被填充。找到它是此算法的关键。
所以,利用3:假设我们有一棵(子)树T。我们知道其左子树中叶节点的数量为n
left。因此,我们知道其右子树中叶节点的数量为n
left或n
left-1,并且特别地,它最多为n
left。
我们进入右子树。知道这个子树中叶节点的最大数量,并知道它们平均分布在两侧的子树中,我们可以推断出两件事:
- 如果这个子树中叶节点的最大数量是奇数,则可疑插槽位于左侧,因为右侧不能比左侧更重。如果是偶数,则插槽位于右侧。
- 每个子子树中叶节点的最大数量是该子树中叶节点数量的一半,在左侧向上取整,在右侧向下取整。
这解决了问题的核心;其余部分是简单的递归。在C++中:
#include <cstddef>
struct node {
node *left = nullptr, *right = nullptr;
};
struct node_counter {
std::size_t leaf;
std::size_t trunk;
std::size_t depth;
};
node const *find_leaf(node const *branch, std::size_t leaf_count, std::size_t depth) {
if(depth == 0) { return branch; }
return find_leaf(leaf_count % 2 ? branch->left : branch->right,
(leaf_count + 1) / 2,
depth - 1);
}
node_counter count_nodes_aux(node const *root) {
if(!root->left) {
return { 1, 0, 0 };
}
auto ctr_left = count_nodes_aux(root->left);
auto leaf_right = find_leaf(root->right, ctr_left.leaf, ctr_left.depth);
return {
ctr_left.leaf * 2 - (leaf_right ? 0 : 1),
ctr_left.trunk * 2 + 1,
ctr_left.depth + 1
};
}
std::size_t count_nodes(node const *root) {
auto ctr = count_nodes_aux(root);
return ctr.leaf + ctr.trunk;
}
为了尝试这个算法,我使用了下面这个非常丑陋的
main
函数。它只是构建一个有许多节点的树,在正确的位置插入新节点,并检查计数器是否按照正确的方式移动。它并不漂亮,也没有遵循最佳实践,如果您在生产中编写这样的代码,您应该被解雇。它是这样的,因为本答案的重点是上面的算法,我认为使其漂亮没有任何意义。
void fill_node(node *n) {
n->left = new node;
n->right = new node;
}
int main() {
node *root = new node;
fill_node(root);
fill_node(root->left);
fill_node(root->right);
fill_node(root->left->left);
fill_node(root->left->right);
fill_node(root->right->left);
fill_node(root->right->right);
fill_node(root->left->left->left);
fill_node(root->left->left->right);
fill_node(root->left->right->left);
fill_node(root->left->right->right);
fill_node(root->right->left->left);
fill_node(root->right->left->right);
fill_node(root->right->right->left);
fill_node(root->right->right->right);
std::cout << count_nodes(root) << std::endl;
root->left ->left ->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl;
root->right->left ->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl;
root->left ->right->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl;
root->right->right->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl;
root->left ->left ->right->left ->left = new node; std::cout << count_nodes(root) << std::endl;
root->right->left ->right->left ->left = new node; std::cout << count_nodes(root) << std::endl;
root->left ->right->right->left ->left = new node; std::cout << count_nodes(root) << std::endl;
root->right->right->right->left ->left = new node; std::cout << count_nodes(root) << std::endl;
root->left ->left ->left ->right->left = new node; std::cout << count_nodes(root) << std::endl;
root->right->left ->left ->right->left = new node; std::cout << count_nodes(root) << std::endl;
root->left ->right->left ->right->left = new node; std::cout << count_nodes(root) << std::endl;
root->right->right->left ->right->left = new node; std::cout << count_nodes(root) << std::endl;
root->left ->left ->right->right->left = new node; std::cout << count_nodes(root) << std::endl;
root->right->left ->right->right->left = new node; std::cout << count_nodes(root) << std::endl;
root->left ->right->right->right->left = new node; std::cout << count_nodes(root) << std::endl;
root->right->right->right->right->left = new node; std::cout << count_nodes(root) << std::endl;
root->left ->left ->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl;
root->right->left ->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl;
root->left ->right->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl;
root->right->right->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl;
root->left ->left ->right->left ->right = new node; std::cout << count_nodes(root) << std::endl;
root->right->left ->right->left ->right = new node; std::cout << count_nodes(root) << std::endl;
root->left ->right->right->left ->right = new node; std::cout << count_nodes(root) << std::endl;
root->right->right->right->left ->right = new node; std::cout << count_nodes(root) << std::endl;
root->left ->left ->left ->right->right = new node; std::cout << count_nodes(root) << std::endl;
root->right->left ->left ->right->right = new node; std::cout << count_nodes(root) << std::endl;
root->left ->right->left ->right->right = new node; std::cout << count_nodes(root) << std::endl;
root->right->right->left ->right->right = new node; std::cout << count_nodes(root) << std::endl;
root->left ->left ->right->right->right = new node; std::cout << count_nodes(root) << std::endl;
root->right->left ->right->right->right = new node; std::cout << count_nodes(root) << std::endl;
root->left ->right->right->right->right = new node; std::cout << count_nodes(root) << std::endl;
root->right->right->right->right->right = new node; std::cout << count_nodes(root) << std::endl;
}