二叉搜索樹遞歸插入不顯示任何東西

我在二叉搜索樹上做了一個小型的Java工作，但是當我將一個節點遞歸插入到樹中並顯示它時，我什麼也沒得到。我已經有一段時間了，我不知道，但我認爲這是一個通過引用的問題。二叉搜索樹遞歸插入不顯示任何東西

這裏是我的代碼：

public class BST { 

    private BSTNode root; 

    public BST() { 
     root = null; 
    } 

    public BSTNode getRoot() { 
     return root; 
    } 

    public void insertR(BSTNode root, Comparable elem) { 

     if (root == null) { 
      root = new BSTNode(elem); 
     } 
     else { 
      if (elem.compareTo(root.element) < 0) { 
       insertR(root.left, elem); 
      } else { 
       insertR(root.right, elem); 
      } 
     } 

    } 

    public void printInOrder (BSTNode root) { 
     if (root != null) { 

      printInOrder(root.left); 
      System.out.println(root.element); 
      printInOrder(root.right); 

     } 
    } 
} 

class BSTNode { 

    protected Comparable element; 
    protected BSTNode left; 
    protected BSTNode right; 

    protected BSTNode (Comparable elem) { 

     element = elem; 
     left = null; 
     right = null; 

    } 

}

我執行了一系列insertR與根是一個節點插入到與ELEM是一個字符串，但它不打印任何東西了，因爲如果樹是根本沒有填寫。我敢肯定，這是我的遞歸插入問題，但我不知道在哪裏，我需要使用遞歸插入方法，返回什麼，我認爲是不可能的。

任何幫助將是偉大的。

來源

2012-12-06 Syafiq Kamarul Azman

Shudn't第二行將是私人BSTNode根？ –

同樣你也可以添加可比元素的構造函數 –

是的，它應該是BSTNode根，抱歉沒有檢查那個部分。可比較的元素可以是任何東西，在這種情況下，我正在使用字符串 –

您的BSTNodes的左側，右側元素爲空。您需要在插入之前創建它們。否則，他們創建一個空的BSTNode（）並插入它，而不連接到樹的其餘部分。

您可以更改線路，

  if (elem.compareTo(root.element) < 0) { 
       insertR(root.left, elem); 
      } else { 
       insertR(root.right, elem); 
      }

到

if (elem.compareTo(root.element) < 0) { 
     if (root.left == null) 
      root.left = new BSTNode(elem); 
     else 
      insertR(root.left, elem); 
    } else { 
     if (root.right == null) 
      root.right = new BSTNode(elem); 
     else 
      insertR(root.right, elem); 
    }

來源

2012-12-06 04:24:35 Arcturus

我試過你的代碼，似乎根本沒有設置任何東西，我試圖打印一些虛假的字符串，如果它曾經傳入其他'if（root = = null）'所以我還是不確定。 –

嘿，我終於明白了，在你的代碼片段和一個額外的if語句的幫助下，我得到了它的工作，謝謝！順便說一句，這是我添加的行：'root（）= new BSTNode（elem）'後面的'if（root.element！= null）this.root = root'; –

這臺BST根和允許類正常工作，改變

if (root == null) { 
     root = new BSTNode(elem); 
    }

到

if (root == null) { 
     root = new BSTNode(elem); 
     if (root.element != null) { 
      this.root = root; 
     } 
    }

來源

2012-12-06 05:33:03

雖然遞歸插入到BST中看起來微不足道，但讓參數傳遞錯誤非常容易，它會使您的嘗試失效。要遞歸調用插入函數，必須將對象BSTNode root作爲參數之一傳遞，並對其內容進行更改，而不是指向它的內容。

在以下代碼中，root = new BSTNode(elem);僅更改本地變量root指向的地址，並且更改對this.root不可見。在作業之前，root的值爲null，當BST爲空時，該值從this.root進行了值複製。分配後，root指向一些新創建的BSTNode，其數據來自elem。代碼的意圖是使this.root指向相同的新BSTNode，但是無法通過使本地root指向它來實現該目的。當insertR返回時，this.root仍指向null！

同樣的錯誤發生在insertR(root.left, elem);和insertR(root.right, elem);。參數已通過，但由於沒有進行內容更改，函數調用只會返回而不會更新BST的信息。

public void insert(Comparable elem) { 
    insertR(this.root, elem); 
} 

public void insertR(BSTNode root, Comparable elem) { 

    if (root == null) { 
     root = new BSTNode(elem); 
    } 
    else { 
     if (elem.compareTo(root.element) < 0) { 
      insertR(root.left, elem); 
     } else { 
      insertR(root.right, elem); 
     } 
    } 

}

要遞歸地更改BST，應對對象包含的變量進行更改，而不是對象變量指向的變量。因此，當this.root是null，你應該處理的第一插入別人，而不是內部insertR的地方，如下所示：

public void insert(Comparable elem) { 
    if (this.root == null) { 
     this.root = new BSTNode(elem); 
    } else { 
     insertR(this.root, elem); 
    } 
}

由大角星額外插入的代碼是正確的，因爲這些變化到root內容作出立即展開到this.root，因爲它們指向相同的BSTNode對象。當然這裏root需要不是null，這是滿意的，因爲null已經在上面的代碼中處理過了。

if (elem.compareTo(root.element) < 0) { 
    if (root.left == null) 
     root.left = new BSTNode(elem); 
    else 
     insertR(root.left, elem); 
} else { 
    if (root.right == null) 
     root.right = new BSTNode(elem); 
    else 
     insertR(root.right, elem); 
}

來源

2013-07-27 06:00:28 lcn

二叉搜索樹遞歸插入不顯示任何東西

回答

相關問題