二叉树中节点搜索导致堆栈溢出

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);
}

然而，由于堆栈溢出，我得到了一个分段错误。有没有办法在不使用递归函数调用的情况下遍历深度树？

* 通过“遍历”，我指的是“搜索具有给定值的节点”，而不是完整的树遍历。

- Conjecture

---

300,000个层级？你知道一个有N个层级的满二叉树有2^N-1个节点吗？这条评论太短了，无法写出你的树可能具有多少个节点！ - MSalters

也许树被存储在外部，并且不作为一个整体加载到内存中。 - Codor

那是针对一棵平衡二叉树的。也许这棵树不平衡。 - Arthur Tacca

如果找不到任何内容，你会返回什么？ - n. m.

如果没有找到任何内容，我会返回nullptr，但是在发布的代码中看不到这一点。实际上，我使用循环构建它，那么为什么不使用循环搜索呢？ - n. m.

Answer 1

是的！ 对于300000级别的树，避免递归。使用循环遍历树并迭代查找值。

二叉搜索树表示

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

为了更进一步澄清问题，您的树的深度为n = 300,000级。因此，在最坏情况下，二叉搜索树（BST）将不得不访问所有树节点。这是一个坏消息，因为该最坏情况具有算法的O(n)时间复杂度。这样的树可能有： 2ˆ300,000个节点=9.9701e+90308个节点（大约）。

---

9.9701e+90308个节点是需要访问的指数级巨大的节点数。有了这些数字，很明显为什么调用堆栈会溢出。

---

解决方案（迭代方式）： 我假设您的节点/声明是经典的标准整数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;
}

采用这种迭代方法可以避免递归，从而节省您在程序调用堆栈中递归查找大型树中的值时所需的麻烦。

- Santiago Varela

---

等等，这不是完整的遍历，这只是节点搜索。话虽如此，对于问题中的代码同样适用。节点搜索很容易迭代执行；完整遍历需要使用递归（使用系统栈或自定义栈）或双向链接树。 - Medinoc

可能你的意思是 Node* temp = this; 而不是 Node* temp = root;，以及 temp = left; 而不是 temp = temp->left; 等等。请查看原始代码，它看起来像是 Node 类中的内联方法。 - CiaPan

@Medinoc 谁说要遍历了。这是一个查找，OP问的是如何避免300,000行的限制。 - Santiago Varela

“谁说要遍历” → “二叉树遍历导致栈溢出” ಠ_ಠ - Medinoc

@Medinoc。哈哈，是的，你说得对，这在标题中，但不在答案中。 - Santiago Varela

Answer 2

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

- Rene

---

这种方法不允许在右子树中未找到所需值时返回递归并处理左子树。 - Codor

@Codor，没错，但示例代码中没有使用 (... else if ...) 这种方式。这是在有序二叉树中搜索时的正常流程。如果树没有排序且必须访问所有节点，则确实无法像这样运行。 - Rene

谢谢澄清，我忽略了那个。 - Codor

Answer 3

你可以通过不使用调用栈而使用自定义栈或类似的东西来实现递归；这可以通过现有的stack模板完成。方法是使用一个while循环，直到堆栈为空为止；由于现有实现使用深度优先搜索，因此可以在此处找到消除递归调用的方法。这里给出了伪代码。

- Codor

---

当堆栈溢出时，使用不同的堆栈 =P。 - Sava B.

Answer 4

当你所拥有的树是一个二叉搜索树，并且你想要做的仅是在其中查找具有特定值的节点时，那么事情就很简单：无需递归，可以使用简单的循环进行查找，就像其他人指出的那样。

在更一般的情况下，如果你拥有的树不一定是二叉搜索树，并且想要对其执行完全遍历，则最简单的方法是使用递归。但正如你已经了解到的，如果这棵树非常深，则递归将无法工作。

因此，为了避免递归，你必须在C++堆上实现一个栈。你需要声明一个新的StackElement类，它将包含每个本地变量以及原始递归函数所接受的每个参数的成员变量。 （你可能只需要较少的成员变量，当你让代码成功运行后再考虑这个问题。）

你可以将StackElement实例存储在堆栈集合中，也可以使每个StackElement实例包含一个指向其父级的指针，从而完全自己实现堆栈。

因此，你的函数不再以递归方式调用自身，而是简单包含一个循环。你的函数使用关于树的根节点的信息初始化当前StackElement进入循环。其父指针将为null，这是另一种说法，即堆栈为空。

在你的函数递归调用自身的每个位置上，新函数将分配一个新的StackElement实例，初始化它，并使用此新实例作为当前元素重复循环。

在递归版本的函数返回的每个位置上，新函数将释放当前StackElement，弹出位于堆栈顶部的元素，使其成为新的当前元素，并重复循环。

当你找到所要查找的节点时，你只需从循环中断开即可。

或者，如果你现有树的节点支持a）到其“父”节点的链接和b）用户数据（在其中可以存储“访问过”标志），则无需实现自己的堆栈，可以直接原地遍历树：在循环的每次迭代中，首先检查当前节点是否是您寻找的节点；如果不是，则枚举子项，直到找到尚未被访问的子项，然后访问该子项；当你到达叶子节点或所有子节点都已被访问的节点时，然后通过跟随指向父节点的链接进行回溯。此外，如果你有自由在遍历树时销毁树，则甚至不需要“用户数据”的概念：一旦你完成子节点，就释放它并使其为空。

- Mike Nakis

---

如果有一个栈，那仍然是递归，只是你移动了栈。对于双向链表的遍历，你实际上并不需要一个“visited”标志：除了当前节点之外，你只需要保持对先前访问过的节点的指针即可。 - Medinoc

Answer 5

好的，它可以通过增加一个本地变量和一些比较来进行尾递归优化：

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

- user2793784

---

对于这个想法我给一个赞，但请不要编写这样的代码。你的 else 分支可以通过直接初始化变量 tmp 来使得代码更易读、更少出错（最后，更短）：Node* tmp = value < v ? right : left;。 - Konrad Rudolph

Answer 6

遍历二叉树是一个递归过程，您将一直遍历，直到发现当前节点指向无处。

您需要一个适当的基本条件。类似于以下内容：

if (treeNode == NULL)
   return NULL;

通常情况下，遍历树的方法如下（使用C语言）：

void traverse(treeNode *pTree){
  if (pTree==0)
    return;
  printf("%d\n",pTree->nodeData);
  traverse(pTree->leftChild);
  traverse(pTree->rightChild);
}

- user4063679

---

这正是我想要避免的：递归。我甚至尝试了尾调用递归，但它不能直接工作，看起来需要编译器优化微调。 - Conjecture

@MarwanB “不work out of the box”是什么意思？它可以在每个现代的C++编译器上启用优化来工作。你正在进行编译优化，是吗？ - Konrad Rudolph

@KonradRudolph 我有一个疑问 - 如果递归函数有一个经过深思熟虑的基本情况，那么它不应该能够处理深度递归吗？就像问题中的300K级别一样。 - user4063679

如果它是尾递归的话，那绝对没问题：它可以处理任意深度。然而，这个函数实际上不是完全的尾递归（我认为也不能是）：第二次调用traverse（或find）可以变成尾调用，但第一次则不行。这与优化无关，事实上：这根本不可能。我应该在之前的评论中明确说明这一点。 - Konrad Rudolph