遍历BST时出现Stackoverflow异常

Question

我已经在 C++ 中为我的一项作业实现了基于链接的 BST（二叉搜索树）。我已经编写了整个课程，一切都运行良好，但我的作业要求我绘制运行时间：

a.  A sorted list of 50000, 75000, and 100000 items
b.  A random list of 50000, 75000, and 100000 items

没关系，我可以插入数字，但它还要求我调用 FindHeight() 和树上的 CountLeaves() 方法。我的问题是我使用递归实现了这两个函数。由于我有一个如此大的数字列表，我收到了 stackoverflow 异常。

这是我的类定义：

template <class TItem>
class BinarySearchTree
{
public:
    struct BinarySearchTreeNode
    {
    public:
        TItem Data;
        BinarySearchTreeNode* LeftChild;
        BinarySearchTreeNode* RightChild;
    };

    BinarySearchTreeNode* RootNode;

    BinarySearchTree();
    ~BinarySearchTree();

    void InsertItem(TItem);

    void PrintTree();
    void PrintTree(BinarySearchTreeNode*);

    void DeleteTree();
    void DeleteTree(BinarySearchTreeNode*&);

    int CountLeaves();
    int CountLeaves(BinarySearchTreeNode*);

    int FindHeight();
    int FindHeight(BinarySearchTreeNode*);

    int SingleParents();
    int SingleParents(BinarySearchTreeNode*);

    TItem FindMin();
    TItem FindMin(BinarySearchTreeNode*);

    TItem FindMax();
    TItem FindMax(BinarySearchTreeNode*);
};

FindHeight() 实现

template <class TItem>
int BinarySearchTree<TItem>::FindHeight()
{
    return FindHeight(RootNode);
}

template <class TItem>
int BinarySearchTree<TItem>::FindHeight(BinarySearchTreeNode* Node)
{
    if(Node == NULL)
        return 0;

    return 1 + max(FindHeight(Node->LeftChild), FindHeight(Node->RightChild));
}

CountLeaves() 实现

template <class TItem>
int BinarySearchTree<TItem>::CountLeaves()
{
    return CountLeaves(RootNode);
}

template <class TItem>
int BinarySearchTree<TItem>::CountLeaves(BinarySearchTreeNode* Node)
{
    if(Node == NULL)
        return 0;
    else if(Node->LeftChild == NULL && Node->RightChild == NULL)
        return 1;
    else
        return CountLeaves(Node->LeftChild) + CountLeaves(Node->RightChild);
}

我试图思考如何在不使用递归的情况下实现这两个方法，但我完全被难住了。有人有什么想法吗？

Answer 1

如果平衡的话，在具有 100,000 个节点的树上递归应该不是问题。深度可能只有 17，在所示的实现中不会使用太多堆栈。 (log2(100,000) = 16.61)。所以看来构建树的代码可能没有正确平衡它。

Answer 2

我发现此页面非常有启发性，因为它讨论了将使用递归的函数转换为递归的机制使用迭代。

它也有显示代码的示例。

Answer 3

可能您需要在插入时计算这个。存储节点的高度，即在Node对象中添加一个整数字段，如高度。还有树的柜台高度和叶子。当您插入一个节点时，如果它的父节点是（曾经）叶子，则叶子计数不会改变，但如果不是，则将叶子计数增加 1。此外，新节点的高度是父节点的高度 + 1，因此如果它更大比树的当前高度高，然后更新它。这是一项作业，所以我不会帮助实际代码

Answer 4

偶尔平衡你的树。如果您的树在 FindHeight() 上出现堆栈溢出，则意味着您的树方式不平衡。如果树是平衡的，对于 100000 个元素，它的深度应该仅为 20 个左右的节点。

重新平衡不平衡二叉树的最简单（但相当慢）的方法是分配一个足够大的 TItem 数组来容纳树中的所有数据，将所有数据按排序插入其中排序，并删除所有节点。然后递归地从数组重建树。根是中间的节点。 root->left 是左半部的中间，root->right 是右半部的中间。递归地重复。这是最简单的重新平衡方法，但速度较慢并且会暂时占用大量内存。另一方面，只有当您检测到树非常不平衡（插入深度超过 100）时才需要执行此操作。

另一个（更好的）选项是在插入期间保持平衡。最直观的方法是跟踪当前节点下方有多少个节点。如果右子节点的“子”节点数量是左子节点的两倍以上，则向左“旋转”。反之亦然。互联网上到处都有关于如何进行树旋转的说明。这使得插入速度稍微慢一些，但是这样就不会出现第一个选项偶尔造成的大规模停顿。另一方面，您必须在进行轮换时不断更新所有“子项”计数，这并非易事。

Answer 5

为了在不递归的情况下对叶子进行计数，请使用迭代器的概念，就像 STL 用于底层 std::set 和 std::map 的 RB 树一样。为您的树创建一个 begin() 和 end() 函数，用于标识有序的第一个和最后一个节点（在本例中是最左边的节点，然后是最右边的节点）大多数节点）。然后创建一个名为

BinarySearchTreeNode*increment(const BinarySearchTreeNode* current_node)

的函数，对于给定的 current_node，它将返回指向树中下一个节点的指针。请记住，要使此实现正常工作，您的 node 类型中需要一个额外的 parent 指针来帮助迭代过程。

increment() 的算法如下所示：

1. 检查当前节点是否有右子节点。
2. 如果有右子树，则使用 while 循环查找该右子树的最左节点。这将是“下一个”节点。否则转至步骤#3。
3. 如果当前节点没有右子节点，则检查当前节点是否是其父节点的左子节点。
4. 如果步骤 #3 为 true，则“下一个”节点是父节点，因此您可以在此时停止，否则继续下一步。
5. 如果步骤 #3 为 false，则当前节点是父节点的右子节点。因此，您需要使用 while 循环继续移动到下一个父节点，直到遇到作为其父节点的左子节点的节点。该左子节点的父节点将成为“下一个”节点，您可以停止。
6. 最后，如果步骤 #5 返回根，则当前节点是树中的最后一个节点，并且迭代器已到达树的末尾。

最后，您需要一个 bool leaf(const BinarySearchTreeNode* current_node) 函数来测试给定节点是否是叶节点。因此，计数器函数可以简单地迭代树并找到所有叶节点，完成后返回最终计数。

如果您想在不使用递归的情况下测量不平衡树的最大深度，则需要在树的 insert() 函数中跟踪节点插入的深度。这可以只是 node 类型中的一个变量，在将节点插入树中时设置。然后，您可以迭代这三个节点，并找到叶节点的最大深度。

顺便说一句，不幸的是，该方法的复杂度将是 O(N) ...远不如 O(log N) 那么好。