8

当谈到递归函数时，我绝望地迷失了方向。我需要创建一个递归函数来遍历二叉树并在特定值之间插入一个新节点。我需要重新复制我的遍历函数并在我使用它的所有其他函数中修改它吗？有人可以评估遍历功能吗？

我认为我的遍历代码没问题。

Node traverse (Node currentNode){
    if (!currentNode.left.equals(null)){
        traverse (currentNode.left);
        return currentNode.left;
    }
    if (!currentNode.right.equals(null)){
        traverse (currentNode.right);
        return currentNode.right;
    }
    return currentNode;
}
4

3 回答 3

15

对于二叉树，有几种不同类型的遍历可以递归完成。它们是按照它们被引用然后访问的顺序编写的（L = 左孩子，V = 访问该节点，R = 右孩子）。

  • 中序遍历 (LVR)
  • 逆序遍历 (RVL)
  • 前序遍历（VLR）
  • 后序遍历 (LRV)

您的代码似乎正在执行后序遍历方法，但您混淆了一些东西。首先，节点就是你要遍历的；数据就是您要访问的内容。其次，您没有理由以实现方式返回节点本身。您的代码不允许有条件说“我正在寻找这个特定的数据，你有 Node@0xdeadbeef 先生吗？”，可以通过某种额外的搜索参数找到它。

学术 BST 遍历只打印节点本身。如果你想添加一个搜索功能，它只是一个额外的参数，以及对正确节点的额外检查。

这是一个片段：

// Academic

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
    if (root.left != null){
        traverse (root.left);
    }
    System.out.println(root.data);
    if (root.right != null){
        traverse (root.right);
    }
}

// Search with a valid node returned, assuming int

public Node traverse (Node root, int data){ // What data are you looking for again?
    if(root.data == data) {
        return root;
    }
    if (root.left != null && data < root.data) {
        return traverse (root.left, data);
    }
    if (root.right != null && data > root.data) {
        return traverse (root.right, data);
    }
    return null;
}
于 2012-04-12T04:18:13.053 回答
1

看起来您正在遍历预购方法，但我有点怀疑您到底希望完成什么而不实际将您的当前节点与一些定义您已到达目的地的基本值进行比较。我建议画出一棵简单的树并可视化这些步骤。然后尝试将其放入代码中。

于 2012-04-12T04:06:35.243 回答
0

递归函数通过修改的参数或终止（退出）条件返回自身的值。例如，阶乘：

int factorial( int param ) {
   if ( param > 1 ) {
      return param * factorial( param -1 );
   } else {
      return 1;
   }
}

在您的代码中，您调用了“遍历”，但随后对结果不执行任何操作...当您的递归函数结束时，您的最终返回将是第一个左孩子（如果存在），否则是第一个右孩子（如果存在），否则是根节点。

请详细说明为什么需要遍历树（另外，不确定“复制函数并在每个其他函数中修改它”是什么意思，函数的整个想法是编码一次调用多次)

于 2012-04-12T04:03:19.583 回答