遞歸插入節點

Question

我想用遞歸方法在二叉樹中插入節點。但是一旦它脫離了方法，根將成爲新的節點，並且左側的孩子和右側的孩子都是空的。有了這個，我正試圖學習遞歸如何工作。另外，遞歸方法總是要返回一些東西。以下是代碼。

public class BinaryNode { 
    int key; 
    BinaryNode left; 
    BinaryNode right; 

    public BinaryNode(int key){ 
     this.key = key; 
     // this.left = left; 
     //this.right = right; 

    } 
} 

public class BinaryTree { 

    BinaryNode root; 


    public void insert(int key){ 

     BinaryNode newNode = new BinaryNode(key); 

      if(root == null){ 
       root = newNode; 

      }else{ 
        BinaryNode focusNode = root; 
        BinaryNode parent; 

       while(true){ 
        parent = focusNode; 
        if(key<focusNode.key){ 

         focusNode = focusNode.left; 
         if(focusNode==null){ 
          parent.left= newNode; 
          return; 
         } 

        }else{ 
         focusNode = focusNode.right; 
         if(focusNode==null){ 
          parent.right= newNode; 
          return; 
         } 
        } 

       } 

      } 





    } 

    public BinaryNode recursiveInsert(int key, BinaryNode node){ 
     BinaryNode newNode = new BinaryNode(key); 
     if (node == null){ 
      root = newNode; 

     } 

     else{ 

      if(key < node.key){ 


       root.left = recursiveInsert(key, node.left); 


      } 
      else{ 

       root.right = recursiveInsert(key, node.right); 


      } 
     } 

     return root; 
    } 




    public String toString(){ 
     String toTree = null; 



     return toTree; 
    } 

    public static void main(String[]args){ 
     BinaryTree tree = new BinaryTree(); 

     tree.recursiveInsert(7, tree.root); 
     tree.recursiveInsert(6, tree.root); 
     tree.recursiveInsert(4, tree.root); 
     tree.recursiveInsert(8, tree.root); 
     tree.recursiveInsert(9, tree.root); 
     tree.recursiveInsert(5, tree.root); 



    } 

} 

我想要的方法是recursiveInsert。謝謝！！

Answer 1

我想這個問題是來自

if (node == null){ 
     root = newNode; 
} 

您遍歷樹，並在最後一步，你是問葉節點的左/右孩子。這沒有，所以它的孩子是空的。 這是遞歸調用返回的值，最後它被分配給根。

要解決此問題，請在下降到節點之前確保存在子節點。

而且這是一個有點怪異

root.left = recursiveInsert(key, node.left); 

應該node，而不是root。

Answer 2

你的遞歸代碼應該是這樣的：

public BinaryNode recursiveInsert(int key, BinaryNode node) { 
    if (node == null) { 
     return root = new BinaryNode<>(key); 
    } else { 
     if (key < node.key) { 
      if (node.left == null) { 
       return node.left = newNode; 
      } else { 
       return recursiveInsert(key, node.left); 
      } 
     } else { 
      if (node.right == null) { 
       return node.right = newNode; 
      } else { 
       return recursiveInsert(key, node.right); 
      } 
     } 
    } 
} 

你的行爲是root節點上的遞歸函數，你更應被作用於node傳遞給遞歸函數。

Answer 3

您的代碼有幾個問題，我不一定會涉及，因爲我認爲他們會分心核心問題。

要回答你的第二個問題：不，沒有規則說遞歸方法必須返回任何東西。他們知道何時終止更重要。

至於你的錯誤，我認爲這可能是由於你的insert方法總是返回並在root上運行。您可能需要修改並返回newNode。

Answer 4

這是因爲您的recursiveInsert方法始終在root上運行。試試這個，而不是 -

public Node recursiveInsert(Node currentParent, Node newNode) { 

     if (currentParent == null) { 
      return newNode; 
     } else if (newNode.key > currentParent.key) { 
      currentParent.right = recursiveInsert(currentParent.right, newNode); 
     } else if (newNode.key < currentParent.key) { 
      currentParent.left = recursiveInsert(currentParent.left, newNode); 
     } 

     return currentParent; 
    }