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

Answer 2

您无需担心调用堆栈；它的工作原理被 C 编译器隐藏，除非您正在搜索非常深的树，否则它不会打扰您。

您的算法或多或少是正确的，但在访问另一个子树之前，您需要检查递归调用的返回值是否为空。像这样的东西：

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

Answer 3

您不需要自己创建调用堆栈。它是一种数据结构，由执行程序的运行时环境维护，例如操作系统或 Java 虚拟机（如果您使用 Java）。每当调用函数时，其参数和局部变量都会被压入堆栈。当函数存在时，它们会被弹出。

作为一名程序员，您通常不必担心这一点。了解调用堆栈是什么有助于准确理解递归函数调用（或任何函数调用）期间发生的情况，或者了解局部变量来自哪里或函数退出后它们会发生什么。

Answer 4

Ira Baxter 的答案和 Frédéric Hamidi 的答案中的所有特殊外壳都表明设计不太正确：

NodePtr SearchTree(int v, NodePtr T)
{
    if (T == NULL || T->value == v)
        return T;
    NodePtr R = SearchTree(v, T->Left);
    if (R == NULL)
        R = SearchTree(v, T->Right);
    return R;
}

我恭敬地认为，这是更简单的。当然，在处理 NULL 叶节点时，它会多进行一次函数调用，但分散的“if null”测试较少。

另外，我认为函数的参数（原版中名义上是 Tree）与 NodePtr 的类型相同，因此我选择仅使用 NodePtr 而不是 Tree。树由作为树的根节点的 NodePtr 表示。