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

论坛 期权论坛 期权     
x_0ve   2018-4-26 13:54   6798   5
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;
}

请问我这个递归函数,如果我在一棵很大的二叉树裏查找,会不会占用超大的内存?展开
分享到 :
0 人收藏

5 个回复

倒序浏览
2#
martinblack954  2级吧友 | 2018-4-30 01:58:24 发帖IP地址来自
首先,查找前,需要一定量的内存存储二叉树,这没得跑吧。。。- -
然后,内存还跟递归所使用的栈的空间有关。
这个空间的大小主要由每层需要存储的数据,与递归层数这两个因素影响。
每层存储的数据,包括函数中定义的局部变量与函数的参数。
递归的层数就是树的层数。
这个函数来看,每层的数据就是函数参数,一个TreeNode类型的指针与一个ElementType变量。
指针就是看你是32位程序还是64位程序罗。。。- -
ElementType变量看具体使用。
那消耗的内存大约就是层数乘以每层的数据罗~~~
3#
haibasan  1级新秀 | 2018-4-30 01:58:25 发帖IP地址来自
即使是非递归的,要在O(N)内完成,也是要占用超大的栈,本质是一样的。在这个以空间换时间的时代,超大的内存不是问题~~
4#
hzhwcmhf  1级新秀 | 2018-4-30 01:58:26 发帖IP地址来自
因为函数一次调用结束时会自动销毁内存
所以最大空间占用与树高成正比....
如果节点数为n 最优空间复杂度为O(logn)  最坏为O(n)

不建议用循环写..那样要写人工栈
5#
skies457  2级吧友 | 2018-4-30 01:58:27 发帖IP地址来自
只占用call stack的空间。因为栈容量的限制递归调用的层数也是有限的,可能递归到一定数量时就自动崩溃了。
6#
iChying  4级常客 | 2018-4-30 01:58:28 发帖IP地址来自
跟树高是线性关系吧
你可以改为while循环 这样子就不占内存了
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP