2 
Leaf *findLeaf(Leaf *R,int data)
{
  if(R->data >= data )
  {
    if(R->left == NULL) return R;
    else return findLeaf(R->left,data);
  }
  else
  {
     if(R->right == NULL) return R;
     else return findLeaf(R->right,data);
  }
}


void traverse(Leaf *R)
{
 if(R==root){printf("ROOT is %d\n",R->data);}
 if(R->left != NULL)
 {
    printf("Left data %d\n",R->left->data);
    traverse(R->left);
 }
 if(R->right != NULL)
 {
    printf("Right data %d\n",R->right->data);
    traverse(R->right);
 }
}

这些代码片段工作正常，但我想知道它们是如何工作的？我需要一个关于递归的简要解释。感谢您的帮助。

4

5 回答 5

4

一个Leaf结构看起来像这样：

typedef struct struct_t {
    int data;
    Leaf * left;   //These allow structs to be chained together where each node 
    Leaf * right;  //has two pointers to two more nodes, causing exponential
} Leaf;            //growth.

该函数接受一个指向我们调用的 Leaf 的指针R和一些要搜索的数据，它返回一个指向 Leaf 的指针

Leaf *findLeaf(Leaf *R,int data){

这段代码决定了我们应该向左还是向右，这棵树是有序的，因为插入函数遵循相同的向左和向右规则。

  if(R->data >= data ){

这是函数递归性质的边缘情况，如果我们已经到达树中的最后一个节点，称为叶子，则返回该叶子。

递归函数的边缘情况具有结束递归并返回结果的任务。没有这个，函数将无法完成。

    if(R->left == NULL) return R;

这就是我们遍历树的方式，在这里，我们沿着左侧向下遍历，因为数据更大。（较大的数据总是插入到左边以保持有序。）现在我们用 调用 findLeaf() R->left，但想象一下，如果我们在下一次调用中再次到达这一点。

它将R->left->left参考第一次调用。如果数据小于我们正在操作的当前节点，我们将改为正确。

    else return findLeaf(R->left,data);

现在我们处于数据小于当前节点的情况，所以我们走对了。

  } else {

这与左边完全一样。

     if(R->right == NULL) return R;
     else return findLeaf(R->right,data);
  }
}

最后，函数的返回可以概念化为R->right->right->left->NULL.

让我们获取这棵树并使用 findLeaf() 对其进行操作；

BST

findLeaf(Leaf * root, 4) //In this example, root is already pointing to (8)

我们从树的顶部开始，其中包含 8。

首先，我们检查R->data >= data我们知道R->data的位置 is(8)和datais (4)。由于我们知道data小于R->data（当前节点），我们输入if语句。

这里我们对左边的 Leaf 进行操作，检查它是否为NULL. 它不是，所以我们跳到else.

现在我们 return findLeaf(R->left, data);，但要返回它，我们必须先解决它。这导致我们进入第二次迭代，我们将在其中进行比较并重(3)试(4)。

再过一遍整个过程，我们会比较(6) to (4)，最后在比较的时候找到我们的节点(4) to (4)。现在我们将回溯该函数并返回如下链：

R(8)->(3)->(6)->(4)

编辑：另外，巧合的是，我写了一篇关于遍历链表的博客文章，在这里解释了二叉搜索树的性质。

于 2013-05-01T14:15:02.413 回答
2

每个 Leaf 包含三个值：

  • data- 一个整数
  • left和right，两个指针都指向另一个叶子。

left或right两者都可能为 NULL，这意味着该方向没有另一片叶子。

所以这是一棵树。根有一个 Leaf，您可以跟踪left或跟踪right指针，直到达到 NULL。

递归的关键是，如果你沿着路径走一叶，剩下的问题与你在根时遇到的问题完全相同（但“小一个”）。所以你可以调用相同的函数来解决问题。最终，例程将位于以 NULL 为指针的 Leaf，并且您已经解决了问题。

在理解树之前理解列表可能是最容易的。所以不是一个有两个指针的叶子，left和right，你有一个只有一个指针的节点，next。递归地按照列表结束：

Node findEnd(Node node) {
     if(node->next == NULL) {
        return node; // Solved!!
     } else {
        return findEnd(node->next);
     }
}

您的 findLeaf 有什么不同？嗯，它使用data参数来决定是否跟随leftorright指针，但其他方面完全一样。

你应该能够理解traverse()这些知识。它使用相同的递归原理来访问结构中的每个 Leaf。

于 2013-05-01T14:12:36.373 回答
1

关于递归的一点评论，然后是关于在树上搜索的一点评论：

假设您要计算 n!。你可以做（​​伪代码）

fac 0     = 1
fac (n+1) = (n+1) * fac n

因此，递归是通过操纵用较小数据解决相同问题的结果来解决问题。请参阅http://en.wikipedia.org/wiki/Recursion。

所以现在，假设我们有一个数据结构树

T = (L, e, R)

L 是左子树，e 是根，R 是右子树......所以假设你想在那棵树中找到值 v，你会做

find v LEAF      = false // you cant find any value in an empty tree, base case
find v (L, e, R) = 

if v == e 
  then something(e) 
else
  if v < e 
    find v L  (here we have recursion, we say 'go and search for v in the left subtree)
  else
    find v R  (here we have recursion, we say 'go and search for v in the right subtree)
  end
end
于 2013-05-01T14:00:06.557 回答
1

递归是将问题分解为两种变体的函数：

  1. 解决问题的一步，然后用剩下的问题调用自己
  2. 解决问题的最后一步

递归只是循环代码的另一种方式。

于 2013-05-01T14:01:12.300 回答
1

递归算法通常与某种形式的数据结构一起工作 - 在您的情况下是树。您需要将递归（非常高级）想象为“在问题的子集上重新应用相同的逻辑”。

在您的情况下，问题的子集是右侧三个的分支或左侧三个的分支。

那么，让我们看一下遍历算法：

它把你传递给方法的叶子和 - 如果它是根叶子声明它然后，如果有一个“左”子叶子，它会显示附加到它的数据并重新启动算法（递归），这意味着......在左节点上如果左节点是ROOT，说明它（第一次递归后没有机会，因为ROOT在顶部）然后，如果我们的左节点有一个“左”子叶，显示它并重新启动左边的算法，左边

当到达左下角时，即当没有左叶时（跟随？:)），那么它在第一个右叶上做同样的事情。如果既没有左叶也没有右叶，这意味着我们在没有子叶的真实叶处，递归调用结束，这意味着算法从递归之前的位置重新开始，并且所有他们当时所处状态的变量。

在第一次递归终止后，您将从左下叶向上移动一叶，如果有一个则从右叶向下移动，然后再次开始打印并在左侧移动。

总而言之 - 最终结果是您以左侧第一方式穿过整棵树。

如果它不是很清楚，请告诉我，并尝试在 findLeaf 递归算法上应用相同的模式。

于 2013-05-01T14:08:29.903 回答