0

我正在尝试计算二叉搜索树中的节点数，并且想知道最有效的方法是什么。这些是我发现的选项：

  1. 在 BST 类中存储 int 计数

  2. 将 int children 存储在树的每个节点中，该节点存储其下的子节点数

  3. 编写一个统计 BST 中节点数的方法

如果使用选项 3，我写过：

int InOrder {
    Node *cur = root;
    int count = 0;
    Stack *s = null;
    bool done = false;

    while(!done) {
        if(cur != NULL) {
            s.push(cur);
            cur = cur->left;
        }
        else {
            if(!s.IsEmpty()) {
                cur = s.pop();
                count++;
                cur = cur->right;
            }
            else {
                done = true;
            }
        }
    }
    return count;

}

但从外观上看，它似乎会陷入和之间的无限cur = cur->left;循环cur = cur->right;

那么哪个选项最有效，如果是选项 3，那么这种方法会起作用吗？

4

1 回答 1

0

我认为第一个选项是最快的，它只需要 O(1) 空间来实现这一点。但是，每当您插入/删除项目时，您都需要不断更新此值。获取所有节点的数量需要 O(1) 时间。

第二个选项会使这个程序变得过于复杂，因为在某处删除/插入一个节点将不得不更新它的所有祖先。要么添加父指针，以便充分更新每个祖先，要么需要遍历树中的所有节点并再次更新数字。无论如何，我认为这将是所有三个中最糟糕的选择。

如果您不多次调用此选项，则第三个选项很好，因为第一个选项比此选项快得多，O(1)。这将花费 O(n)，因为您需要遍历每个节点来检查计数。

就您的代码而言，我认为以递归方式编写更容易，如下所示：

int getCount(Node* n)
{
 if (!n)
  return 0;
 return 1 + getCount(n->left) + getCount(n->right);
}

希望这可以帮助！

于 2013-06-25T05:32:33.770 回答