如何使用递归在二叉树中进行回溯

Question

我正在尝试插入一个二进制节点。我的代码很混乱，没有挽救的希望，所以我计划重写它（基本上我没有考虑回溯并且没有仔细思考算法）。

我正在尝试使用中序遍历插入二进制节点，但我不理解如何回溯。

     D
    / \
   B   E 
  / \ / \
 A  C F 

我该如何在根节点为D的二叉树中搜索左子树，然后返回并搜索右子树？这可能是一个愚蠢的问题，但我被难住了。我能想到最好的方法是像这样进行：
def traverse(node): if node is not None: traverse(node.left) traverse(node.right)

 if (!root.hasLeftChild) {
      root = root.getLeftChild(); 
      recurse(root); 
 } 

但是当我到达底部时，我无法随着根节点返回。另外，它没有解决这样一个问题：如果我到达底部左侧节点，则必须先填写该节点的两个子节点，然后才能开始回溯。我想我这样考虑是错误的。

- Aire

Answer 1

树：

     D
    / \
   B   E 
  / \ / \
 A  C F 

递归实现：

使用中序遍历

  if (root == null) 
    return;

      recurse(root.getLeftChild()); 
      int rootData = root.getData();
      recurse(root.getRightChild()); 

现在，递归是如何工作的：

root.getLeftChild()将继续递归调用左子节点，直到遇到null节点（因此除非遇到null节点，否则控制不会转到recurse(root.getRightChild());）。

到目前为止已经遍历了的树：

         D
        / 
       B    
      / 
     A  
    /
  null <-- current Position

当它到达节点A时，A.left == null，因此它会递归回到node A（将节点的值分配给rootData）

     D
    / 
   B
  / 
 A  <-- current Position

然后，它进入下一次递归调用：recurse(root.getRightChild());

。

         D
        / 
       B    
      / 
     A  
      \
      null <-- current Position

现在，由于 A 的左右子节点 left 和 right 已经遍历完成，控制权将返回到调用 b.left = A 的节点 B，并查找 B.right

---

以此栈为例，考虑以下树形结构(节点，值)

     A
    / \
   B   E 
  / \ / \
 C  D F 

步骤：

• A 调用了它的左侧节点 B，所以A被压入栈中
• B 调用了它的左侧节点 C，所以B被压入栈中
• C 调用了它的左侧节点 null，所以C被压入栈中
• 现在C的左侧和右侧都是null，这标志着该节点的递归结束，因此它从栈中弹出
• 现在C已经遍历完成，所以控制权回到B并检查哪一行调用了这个命令
• 由于执行了b.left，所以现在将转到B.right并push D......此操作继续进行，这就是所谓的递归堆栈

- NoobEditor

---

好的，我有点困惑它如何进入下一个递归调用。当root == null时，该方法就返回了，那么它为什么还在继续下去呢？ - Aire

我认为你需要学习递归栈的知识...当程序被递归调用时，每个被调用的子程序都在一个新的内存“栈”中运行...一旦当前栈操作完成，控制权就会返回到调用刚刚完成的栈的那个点。 - NoobEditor

啊，我以前从未真正使用过递归堆栈，但我的教授在讲课时尝试解释它。我观看了一个YouTube视频，它更清楚地解释了它。所以基本上，堆栈看起来像DBA，然后它碰到空值并弹出A，并从int rootData = root.getData()解析并递归右子节点。由于没有其他事情要做，它回到B并做同样的事情，然后回到A并再次在右侧运行，然后尝试再次获取leftChild并通过该方法运行。 - Aire

其实，还有一件事。为什么A是最后一个？当D通过该方法时，它的两个子节点都为null，所以它也应该被弹出，对吧？这样看起来就像：ABD -> AB -> A -> E -> EF -> E -> G。 - Aire

请注意，递归发生在 B、B->C->null->C 弹出 -> 回到 B -> D -> null -> D 弹出 -> 回到 B -> B 弹出......这是因为，只有当两个子节点都被访问后，才会弹出父节点....在树中，如果您感到疑惑，只需了解最后一个父节点和叶子节点的操作方式，然后就能更好地理解它！ :) - NoobEditor

Answer 2

尝试这个例子。它使用递归按顺序访问所有节点：

public class Example {

    public static void main(String[] args) {
        visitInOrder(new Node("D",
            new Node("B", new Node("A"), new Node("C")),
            new Node("F", new Node("E"))));
    }

    public static void visitInOrder(Node node) {
        if (node != null) {
            visitInOrder(node.left());
            System.out.println(node.name());
            visitInOrder(node.right());
        }
    }
}

class Node {

    private final String name;
    private Node left;
    private Node right;

    public Node(String name) {
        this(name, null);
    }

    public Node(String name, Node left) {
        this(name, left, null);
    }

    public Node(String name, Node left, Node right) {
        this.name = name;
        this.left = left;
        this.right = right;
    }

    public String name() { return name; }    

    public Node left() { return left; }

    public Node right() { return right; }
}

输出：

A
B
C
D
E
F

- Harmlezz

---

你的方法 visitInOrder 实际上是在进行先序遍历，但是你得到的输出结果却是期望的中序遍历结果。最好修复一下这个方法。 - Seelenvirtuose

@Seelenvirtuose 是的，你说得对。现在我已经修正了顺序，但是错过了修正输出。我会立即处理。谢谢！ - Harmlezz

额嗯：你误解了我的意思！输出已经是正确的了。它是有序的。只是方法不正确。现在你修正了方法，但是却完全搞砸了输出。现在你必须将输出改回初始形式。 - Seelenvirtuose

但是in-order是：左，自身，右。输出结果没问题，但完全令人困惑。确认的答案已经找到了解决方案。我认为我的输出是正确的，不是吗？ - Harmlezz

准确地说：左、自己、右！对于一个父节点为“B”，左子节点为“A”，右子节点为“C”的子树（如问题中所示），中序输出为“ABC”。当访问当前节点B时，它会被放在A和C之间！此外，我没有检查您的答案是否正确回答了问题。我只看到您发布了一个中序输出，但建议使用前序方法。目前，您有一个中序方法和一个既不是前序也不是后序的输出。这很混乱。该示例的中序输出将是排序后的输出。 - Seelenvirtuose

我的示例树与问题中的树不同步，这就是为什么我的输出结果不同。但是感谢大家的许多评论。我搞砸了这个答案 :) - Harmlezz

Answer 3

所以你想要实现深度优先搜索 - 你可以在许多书籍或维基百科上找到相关内容。

关键是，你的函数需要递归地对每个子节点调用自身。例如：

public Node findSpot(Node node, List<Node> visits){
    visits.add(node);
    //condition check, return this node if its the right node.
    Node result = null;
    for(Node child : node.getListChildren()){
        if((result findSpot(child)) != null){
             return result
        }
    }
    return null;
}

因此，它递归地检查节点，在树的每个深度层上将一个新方法放在堆栈上。如果没有找到它正在寻找的内容，它会检查下一个分支。访问列表将让您看到它访问节点的顺序，以便您可以查看。这将帮助您了解它的工作原理。

- phil_20686