所以我想出了一个有趣的问题，看看是否有一种有效的方法来解决。所以基本上有一个平衡的二叉树，其中保留了 id 号(它不是 bst，所以没有正式的安排)。您只有有限数量的查询才能查明有多少个节点。保证对于每个节点 E，左子树在该节点 E 处的节点数与右子树的节点数一样多或多一个。要求程序找出有多少个节点的最佳方法是什么？ 例如给定这样一棵树:

          1
      4      2
  3

程序将给出以下输出:

 Query: 1
 Response: 4 2
 Query: 4
 Response 3
 Query: 3
 Response: 0 0 
 Query: 2
 Response: 0 0
 Answer: 4

最佳答案

我终于弄明白了。

从条件

It is guaranteed that for every node E that the left subtree will have as many or one more node than the right subtree at that node E.

由此可见

1. 可以根据树的深度计算出非叶节点的个数；它是 2^{深度 - 1}。因此，有趣的是叶节点。
2. 给定平衡条件，总是只有一个地方可以插入新节点或删除现有节点。 (这意味着给定数量的叶节点意味着一种且只有一种叶节点模式。)
3. 如果我们知道一个节点的左子树的叶节点数，我们就知道右子树的叶节点数(和节点数)要么相同，要么比它少一个。
4. 从 2. 和 3. 可以看出，在右子树中只有一个叶节点槽，如果不检查树，我们无法知道它是否已填充。找到它是这个算法的诀窍。

所以，利用3:假设我们有一棵(子)树T。我们知道它的左子树中的叶节点数是n_left。因此我们知道其右子树中叶节点的数量要么是 n_left 要么是 n_left - 1，特别是它至多是 n_left .

我们进入右子树。知道这棵子树的最大叶子节点数，并且知道它们平分在两边的子树中，我们可以推断出两件事:

• 如果此子树中叶节点的最大数目为奇数，则有问题的插槽在左侧，因为右侧不能比左侧重。如果是偶数，则插槽在右边
• 每个子树的叶节点数最大为子树叶节点数的一半，左边向上取整，右边向下取整。

这解决了问题的核心；剩下的就是简单的递归。在 C++ 中:

#include <cstddef>

// I'm using a simple node structure, you'd use query functions. The
// algorithm is not meaningfully altered by this.
struct node {
  node *left = nullptr, *right = nullptr;
};

struct node_counter {
  std::size_t leaf;      // number of leaf nodes,
  std::size_t trunk;     // number of trunk nodes,
  std::size_t depth;     // and depth of the inspected subtree.
};

// Interesting function #1: Given a right subtree and the leaf-count and
// depth of its left sibling, find the node that might or might not be there
node const *find_leaf(node const *branch, std::size_t leaf_count, std::size_t depth) {
  // We've gone down, found the slot. Return it.
  if(depth == 0) { return branch; }

  // The heart of the matter: Step into the subtree that contains the
  // questionable slot, with its maximum leaf node count and depth.
  return find_leaf(leaf_count % 2 ? branch->left : branch->right,
                   (leaf_count + 1) / 2, // int division
                   depth - 1);
}

// Recursive counter. This steps down on the left side, then infers the
// number of leaf and trunk nodes on the right side for each level.
node_counter count_nodes_aux(node const *root) {
  // leftmost leaf node is reached. Return info for it.
  if(!root->left) {
    return { 1, 0, 0 };
  }

  // We're in the middle of the tree. Get the counts for the left side,
  auto ctr_left   = count_nodes_aux(root->left);

  // then find the questionable slot on the right
  auto leaf_right = find_leaf(root->right, ctr_left.leaf, ctr_left.depth);

  return {
    // the number of leaf nodes in this tree is double that of the left
    // subtree if the node is there, one less otherwise.
    ctr_left.leaf * 2 - (leaf_right ? 0 : 1),

    // And this is just an easy way to keep count of the number of non-leaf
    // nodes and the depth of the inspected subtree.
    ctr_left.trunk * 2 + 1,
    ctr_left.depth + 1
  };
}

// Frontend function to make the whole thing easily usable.
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;
}

关于python - 平衡树中的节点数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29463725/