C中的递归和树搜索？

Question

一种新的树木和递归功能....

我知道如何创建堆栈以及如何创建递归函数的基础知识.

我正在进行预先排序的遍历搜索,当搜索的值与该节点的值匹配时,该搜索应返回树中节点的地址.

我在返回部分遇到问题...我试着在调用堆栈上读取一些东西......但我不明白如何实现它.它已经存在或者我必须制作这个堆栈吗？如果我必须制作它,我该如何制作这个堆栈？我读到它需要与树的高度成正比...是找到树高的最佳方法来制作另一个函数吗？

这是我到目前为止编写的一些代码:Tree和NodePtr是一个指向节点的指针......

NodePtr SearchTree(int v, Tree T)
{
    //printf(" %i \n", T->value);

    if(T->value == v) 
    {
        return T;
    }
    else
    {
        if(T->Left != NULL) SearchTree(value, T->Left);
        if(T->Right != NULL) SearchTree(value, T->Right);
    }

    return NULL;
}

Answer 1

首先,看看 递归.

现在,您希望返回返回的递归调用SearchTree(),因为您正在使用递归将问题委派给自己的两个实例,因此如果您没有获得上游的返回值,则无法执行任何操作:

NodePtr SearchTree(int v, Tree t)
{
    printf(" %i \n", t->value);
    if (t->value == v) {
        return t;
    } else {
        if (t->Left != NULL) {
            NodePtr left = SearchTree(v, t->Left);
            if (left != NULL) {
                return left;
            }
        }
        if (t->Right != NULL) {
            return SearchTree(v, t->Right);
        }
    }

    return NULL;
}