如何使用二叉树中的recusrion完成回溯

问题描述

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

I'm trying to insert a Binary Node. My code is convoluted and there's no hope of rescuing it so I plan to rewrite it (basically I didn't account for backtracking and didn't think about the algorithm all that closely).

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

I'm trying to insert a Binary Node using in order traversal, but I don't understand how I'm supposed to backtrack.

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

我如何搜索根D的左子树，然后返回并搜索正确对象，真爱？这可能是一个愚蠢的问题，但我很难过。我能想到的最好的是这样的：

How would I search through the left subtree of root D and then go back and search through the right one? It might be a stupid question, but I'm stumped. The best I can come up with is something like this:

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

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

But when I reach the bottom, I can't go back up with the root. Also, it doesn't solve the problem where if I reach the bottom left node I have to fill up both children of that node before starting to backtrack.

我想我正在考虑这个问题。

I think I'm thinking about this the wrong way.

推荐答案

树：

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

对于递归：

使用InOrder Traverse

Using InOrder Traverse

  if (root == null) 
    return;

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

现在，它如何递归：

root.getLeftChild（）将继续以递归方式调用左子子，除非它命中 null node（所以控制不会转到 recurse（root.getRightChild（））; 除非 null 节点被击中）

root.getLeftChild() will go on calling the left sub-child recursively unless it hits null node ( so control wont go to recurse(root.getRightChild()); unless null node is hit )

到目前为止树已走过：

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

所以一旦到达节点 A ， A.left == null ，所以它递归到节点A （将节点的值赋给 rootData ）

So once it reaches node A, A.left == null, so it recurses back to node A (assigning value of node to rootData)

     D
    / 
   B
  / 
 A  <-- current Position

然后进入下一个递归调用， recurse（root.getRightChild） （））;

and after this, it goes to next recursive call, recurse(root.getRightChild());

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

现在，因为左和正确 A 已遍历，控制权将返回节点 B （称为 b.left = A ）并寻找 B.right

and now, since left and right of A have been traversed, control will go back to node B (which called b.left = A) and will look for B.right

以此堆栈为例，对于下面的树（节点，值）

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

步骤：

• A 来电它的左边 B ，所以A推入堆栈


• B 调用它的左边 C ，所以B推入堆栈


• C 调用其左 null ，所以C推入堆栈


• 现在C有左和右为 null ...所以这标志着这个节点的递归结束，因此它的 pop 从堆栈中删除


• 现在，C完全遍历，所以，当B称为C，控制返回B并检查哪一行称为此命令


• 当 b.left 被执行时，它现在将转到 B.right 和推送 D ...... 然后继续，这叫做Recursion Stack

• A calls its left B, so A pushed in stack
• B calls its left C, so B pushed in stack
• C calls its left null, so C pushed in stack
• Now C has both left and right as null...so this marks the end of recursion for this node, hence its popped out of Stack
• Now, C is traversed completely, so, as B called C , control goes back to B and check which line called this command
• As b.left was executed, it will now go to B.right and push D...... and this goes on , this is called Recursion Stack

这篇关于如何使用二叉树中的recusrion完成回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！