请问递归查找二叉树，消不消耗很大的内存？

TreeNode *Find(TreeNode *T,ElementType x)
{
if(T==NULL)
      return NULL;
if(T->cRight,x);
else if(T->c>x)
      return Find(T->Left,x);
else
      return T;
}

请问我这个递归函数...TreeNode *Find(TreeNode *T,ElementType x)
{
if(T==NULL)
      return NULL;
if(T->cRight,x);
else if(T->c>x)
      return Find(T->Left,x);
else
      return T;
}

请问我这个递归函数，如果我在一棵很大的二叉树裏查找，会不会占用超大的内存？展开

martinblack954 · 2018-4-30 01:58:24

首先，查找前，需要一定量的内存存储二叉树，这没得跑吧。。。- -
然后，内存还跟递归所使用的栈的空间有关。
这个空间的大小主要由每层需要存储的数据，与递归层数这两个因素影响。
每层存储的数据，包括函数中定义的局部变量与函数的参数。
递归的层数就是树的层数。
这个函数来看，每层的数据就是函数参数，一个TreeNode类型的指针与一个ElementType变量。
指针就是看你是32位程序还是64位程序罗。。。- -
ElementType变量看具体使用。
那消耗的内存大约就是层数乘以每层的数据罗~~~

haibasan · 2018-4-30 01:58:25

即使是非递归的，要在O（N）内完成，也是要占用超大的栈，本质是一样的。在这个以空间换时间的时代，超大的内存不是问题~~

hzhwcmhf · 2018-4-30 01:58:26

因为函数一次调用结束时会自动销毁内存
所以最大空间占用与树高成正比....
如果节点数为n 最优空间复杂度为O(logn) 最坏为O(n)

不建议用循环写..那样要写人工栈

skies457 · 2018-4-30 01:58:27

只占用call stack的空间。因为栈容量的限制递归调用的层数也是有限的，可能递归到一定数量时就自动崩溃了。

iChying · 2018-4-30 01:58:28

跟树高是线性关系吧
你可以改为while循环这样子就不占内存了

请问递归查找二叉树，消不消耗很大的内存？

5 个回复