java - 如何在二叉树中使用递归完成回溯

Question

我正在尝试插入二进制节点。我的代码很复杂，没有希望挽救它，所以我打算重写它(基本上我没有考虑回溯，也没有仔细考虑算法)。

我正在尝试使用顺序遍历插入二进制节点，但我不明白我应该如何回溯。

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

我如何搜索根 D 的左子树，然后返回搜索右子树？这可能是一个愚蠢的问题，但我很困惑。我能想到的最好的是这样的:

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

但是当我到达底部时，我无法再回到根部。此外，它没有解决如果我到达左下角节点我必须在开始回溯之前填满该节点的两个子节点的问题。

我想我是在以错误的方式思考这个问题。

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 节点(因此控制不会转到 recurse (root.getRightChild()); 除非 null 节点被命中 )

树走了这么远:

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

所以一旦它到达节点A，A.left == null，所以它递归回到节点A(分配节点的值到 rootData)

     D
    / 
   B
  / 
 A  <-- current Position

在此之后，它进入下一个递归调用，recurse(root.getRightChild());

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

现在，由于 A 的 left 和 right 已经遍历，控制权将返回到节点 B(调用了 b.left = A)并将寻找 B.right

---

以这个 Stack 为例，对于下面的树 ( node , value )

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

步骤:

• A 调用它左边的 B，所以 A 入栈
• B调用它的左边C，所以B入栈
• C调用它的左边null，所以C压入栈
• 现在 C 的 left 和 right 都为 null...所以这标志着该节点递归的结束，因此它的 pop出栈
• 现在，C 被完全遍历，因此，当 B 调用 C 时，控制权返回 B 并检查哪一行调用了此命令
• 随着 b.left 被执行，它现在将转到 B.right 和 push D...... 这样下去，这叫做递归栈