二进制树中的节点搜索溢出堆栈

Question

我使用以下方法遍历*300 000级别的二叉树:

Node* find(int v){
   if(value==v)
      return this;
   else if(right && value<v)
      return right->find(v); 
   else if(left && value>v)
      return left->find(v);
}

但是由于堆栈溢出,我得到了分段错误.关于如何在没有递归函数调用开销的情况下遍历深层树的任何想法？

*"遍历"我的意思是"搜索具有给定值的节点",而不是完整的树遍历.

Answer 1

是! 对于300 000级树,避免递归.遍历您的树并使用循环迭代地查找值.

二进制搜索树表示

           25             // Level 1
        20    36          // Level 2
      10 22  30 40        // Level 3
  .. .. .. .. .. .. .. 
.. .. .. .. .. .. .. ..   // Level n

只是为了进一步澄清问题.您的树的深度为n = 300.000级.因此,在最坏的情况下,二进制搜索树(BST)将不得不访问所有树的节点.这是坏消息,因为最坏的情况具有算法O(n)时间复杂度.这样的树可以有:

2300.000个节点= 9.9701e + 90308个节点(大约).

9.9701e + 90308节点是要访问的指数大量节点.有了这些数字,调用堆栈溢出的原因就变得非常清楚了.

解决方案(迭代方式):

我假设您的Node class/ struct声明是经典的标准整数BST.然后你可以调整它,它会工作:

struct Node {
    int data;
    Node* right;
    Node* left;
};

Node* find(int v) {
    Node* temp = root;  // temp Node* value copy to not mess up tree structure by changing the root
    while (temp != nullptr) {
        if (temp->data == v) {
            return temp;
        }
        if (v > temp->data) {
            temp = temp->right;
        }
        else {
            temp = temp->left;
        }
    }
    return nullptr;
}

采用这种迭代方法可以避免递归,从而避免了在程序调用堆栈中以递归方式查找树中的值的麻烦.

Answer 2

一个简单的循环,你有一个Node*类型的变量,你设置为下一个节点,然后再循环...
不要忘记你正在搜索的值不存在的情况!

Answer 3

您可以通过不使用调用堆栈来实现递归,而是使用用户定义的堆栈或类似的东西; 这可以通过现有的堆栈模板完成.方法是while循环迭代直到堆栈为空; 由于现有的实现使用深度优先搜索,因此可以在此处找到消除递归调用.

Answer 4

当您拥有的树是二进制搜索树时,您想要做的就是在其中搜索具有特定值的节点,那么事情很简单:不需要递归,您可以使用简单的循环来完成其他人指出.

在更一般的情况下,有一个树不一定是二进制搜索树,并且想要执行它的完整遍历,最简单的方法是使用递归,但正如你已经理解的,如果树很深,那么递归不管用.

因此,为了避免递归,您必须在C++堆上实现堆栈.您需要声明一个新StackElement类,该类将包含原始递归函数所具有的每个局部变量的一个成员,以及原始递归函数接受的每个参数的一个成员.(您可能能够使用更少的成员变量,您可以在使用代码后担心这一点.)

您可以将实例存储StackElement在堆栈集合中,或者您可以简单地让每个实例包含指向其父项的指针,从而自己完全实现堆栈.

因此,它不是递归调用自身的函数,而是简单地包含一个循环.您的函数进入循环,并使用有关树的根节点的信息初始化当前 StackElement.它的父指针将为null,这是另一种表示堆栈为空的方式.

在函数的递归版本调用自身的每个地方,新函数将分配一个新实例StackElement,初始化它,并使用这个新实例作为当前元素重复循环.

在函数的递归版本返回的每个地方,你的新函数将释放当前 StackElement,弹出位于堆栈顶部的那个,使其成为新的当前元素,并重复循环.

当您找到所需的节点时,您只需从循环中断开.

或者,如果现有树的节点支持a)到其"父"节点的链接和b)用户数据(您可以存储"已访问"标志),那么您不需要实现自己的堆栈,您可以只是在原地遍历树:在循环的每次迭代中,首先检查当前节点是否是您正在寻找的节点; 如果没有,那么你通过孩子进行枚举,直到你找到一个尚未访问过的孩子,然后你去看看它; 当你到达一个叶子,或者一个孩子都被访问过的节点时,你可以通过跟踪父母的链接来回溯.此外,如果您在遍历它时可以自由地销毁树,那么您甚至不需要"用户数据"的概念:一旦完成了子节点,就可以释放它并使其为空.