Java二叉搜索樹實現問題。

Question

我正在開發一個在java中的二叉搜索樹。但是我面臨着一些困難。下面是代碼

class Node { 

    Node left, right; 
    Integer data; 

    Node(Integer d, Node left, Node right) { 
     this.data = d; 
     this.left = left; 
     this.right = right; 
    } 
} 

class BinaryTree { 

    Node root; 

    public BinaryTree(Node root) { 
     this.root = root; 
    } 

    void insert(int d) 
    { 
     if(root==null) 
      root= new Node(d, null, null); 
     insert(root,d); 
    } 
    void insert(Node root, int d) { 
     if (root == null) { 
      root=new Node(d,null,null); 
     } else if (d > root.data) { 
      insert(root.right, d); 
     } else if (d < root.data) { 
      insert(root.left, d); 
     } 
    } 

    void inorder(Node root) { 
     if (root != null) { 
      inorder(root.left); 
      System.out.println(root.data); 
      inorder(root.right); 
     } 
    } 
} 

public class BST { 

    public static void main(String[] args) throws IOException { 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     String str = null; 
     BinaryTree bt=new BinaryTree(null); 
     while (!(str = br.readLine()).equalsIgnoreCase("0")) { 
      bt.insert(Integer.parseInt(str)); 
     } 
     bt.inorder(bt.root); 
    } 
} 

我面對這裏的問題是，在Java中只按值傳遞。除了第一個將新創建的根傳遞給它的第一種情況外，我在每種情況下都將root設置爲null。在這裏，當我通過傳遞根值的左邊或右邊的值來對插入函數進行遞歸調用，然後在新的調用中，如果需要創建新的根，但是當函數結束時，它的值不會被反映到調用者函數的變量。 總之，這個問題是由於Java所遵循的值的調用。

任何人都可以請建議解決這個問題？

Answer 1

您對insert(root.right/left, d)調用不會改變原來的左/右節點，如果他們是空的，而只是使方法參數點到一個新的變量（如你注意到它，在Java中不會改變原始參考）。您對第一個根的更改會生效，因爲您調用了其他方法，insert(int)。

您是否考慮過製作左右BinaryTree而不是Node s？另外，不要使用「空」，而應考慮使用「空」BinaryTree（具有空根和isEmpty方法）。

注意概念，左右都是樹，而不是節點，這樣的設計會更乾淨。

---

示例代碼。未經測試，但思路應該是正確的：

class Node { 

    BinaryTree left, right; 
    Integer data; 

    Node(Integer d, BinaryTree left, BinaryTree right) { 
     this.data = d; 
     this.left = left; 
     this.right = right; 
    } 
} 

class BinaryTree { 

    Node root; 

    // Empty tree 
    BinaryTree() { 
     this(null); 
    } 

    BinaryTree(Node root) { 
     this.root == root; 
    } 

    void insert(int d) { 

     if (this.root == null) { 

      // The tree was empty, so it creates a new root with empty subtrees 
      this.root = new Node(d, new BinaryTree(), new BinaryTree()); 

     } else if (d > this.root.data) { 
      this.root.right.insert(d); 
     } else if (d < this.root.data) { 
      this.root.left.insert(d); 
     } 
    } 
} 

注：

• 我尊重你的現有代碼的風格。
• 此實現將跳過重複的元素。

Answer 2

建議，

• 如果你的意思是使用int值我不會用一個Integer。
• 如果你正在複製已經在JVM中的代碼，我會先閱讀代碼如何工作（並複製你需要的）
• 當我在我的代碼中有一個錯誤時，我使用調試器來解決出了什麼問題。
• 我從一個最簡單的單位開始展示問題，並修復了這種簡單的情況。

我會發布最簡單的單元測試，任何人都可以重現，以及在調試器中看到的東西如果沒有任何意義。

這並不真正回答你的問題，但太長的評論。 ;）