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

Question

我正在尝试插入二进制节点.我的代码很复杂,没有希望拯救它,所以我打算重写它(基本上我没有考虑回溯,并没有考虑所有密切关注的算法).

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

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

我如何搜索根D的左子树,然后返回并搜索正确的子树？这可能是一个愚蠢的问题,但我很难过.我能想到的最好的是这样的:

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

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

我想我正在以错误的方式思考这个问题.

Answer 1

树:

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

递送:

使用InOrder Traverse

  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所以它会递归到node A(指定节点的值rootData)

     D
    / 
   B
  / 
 A  <-- current Position

然后,它进入下一个递归调用, recurse(root.getRightChild());

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

而现在,由于left和right中A已经走过,控制将返回到节点B(即要求b.left = A),并会寻找B.right

以此堆栈为例,对于下面的树(节点,值)

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

脚步 :