二叉树溢出堆栈中的节点搜索
二叉树溢出堆栈中的节点搜索
提问于 2017-03-28 17:06:34
我使用下面的方法来遍历*一棵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);
}然而，由于堆栈溢出，我得到了一个分段错误。关于如何在没有递归函数调用开销的情况下遍历深层树，您有什么想法吗？
*“遍历”我的意思是“搜索具有给定值的节点”，而不是完整的树遍历。
回答 4
Stack Overflow用户
发布于 2017-03-28 17:12:19
一个简单的循环，其中有一个Node*类型的变量，您将其设置为下一个节点，然后再次循环...
不要忘记您要搜索的值不存在的情况！
Stack Overflow用户
发布于 2017-03-28 17:09:28
Stack Overflow用户
发布于 2017-03-29 07:36:12
嗯，它可以以一个额外的局部变量和一些比较为代价来实现尾递归：
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);
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43065230
复制相关文章
相似问题