c++ - 遍历 BST 时的 Stackoverflow 异常

我已经在 C++ 中为我的一项任务实现了一个基于链接的 BST(二叉搜索树)。我已经写了我的整个类(class)并且一切正常，但是我的作业要求我绘制以下运行时间:

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

没关系，我可以插入数字，但它也要求我调用树上的 FindHeight() 和 CountLeaves() 方法。我的问题是我已经使用 recursion 实现了这两个函数。由于我有一个如此大的数字列表，因此我收到了 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);
}

我试图考虑如何在没有递归的情况下实现这两种方法，但我完全被难住了。有人有主意吗？

最佳答案

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

countLeaves

c++ - 遍历 BST 时的 Stackoverflow 异常