將節點插入java中的二叉樹問題

Question

即時通訊從C++到java，我很困惑與java的二叉樹。有一個Node類是使它成爲內部靜態類的唯一方法？我看到的所有例子都是這樣做的。然而，我這樣做的方式是我有一個節點類和二元樹類使用此節點類。但是當我嘗試在第二次插入後插入樹中時，我不斷收到錯誤。我在這條線上得到一個例外if(dataIn <= nodeIn.getLeft().getData()){

我很困惑，我做錯了什麼....這裏是我的代碼插入，我有。在此先感謝..

public void insert(int dataIn){ 
    root = insert(root, dataIn); 
} 

private Node insert(Node nodeIn, int dataIn){ 
    if(nodeIn==null){ 
     nodeIn = new Node(null, null, dataIn); 
    }else{ 
     if(dataIn <= nodeIn.getLeft().getData()){ 
      nodeIn.setLeft(insert(nodeIn.getLeft(), dataIn)); 
     }else{ 
      nodeIn.setRight(insert(nodeIn.getRight(), dataIn)); 
     } 
    } 

    return nodeIn; 
} 

Answer 1

您需要測試是否nodeIn.getLeft() == null。

Answer 2

是唯一能讓Node類成爲內部靜態類的方法嗎？我看到的所有例子都是這樣做的。

號

Node類不需要是內或嵌套類。 （嚴格來說，「靜態內部」類是嵌套類。）

但是，只有內部類或嵌套類可以是private。如果您的Node類是常規類，那麼您將實現細節公佈給（至少）同一個包中的其他類。這是一個糟糕的主意......這就解釋了爲什麼你會看到Node類被聲明爲這樣。

Answer 3

令人困惑的部分原因是「Node」不應該是插入方法的參數，您應該調用在節點中定義的插入方法。

因此，假設您在「正常代碼」中持有「根」節點 - 我們稱其爲「rootNode」，只是爲了模糊。

好了，你的代碼插入到樹將是：

rootNode.insert(newValue); 

很容易的。

現在定義該方法。

public class Node { 
    private int value; 
    private Node lower; 
    private Node higher; 

    public void insert(int newValue) { 
     if (newValue < value) 
      if(lower == null) 
       lower=new Node(value); 
      else 
       lower.insert(newValue); 
     else 
      if(higher == null) 
       higher=new Node(value); 
      else 
       higher.insert(newValue); 
     } 

// and you'll need a constructor 
    public Node(int value) { 
     this.value=value; 
    } 
} 

這應該更清楚。我要打「Post」，然後我要編輯它，並弄清楚如何輕鬆折射這個邪惡的邪惡副本&粘貼代碼。

第二個想法，我會留在那裏，因爲它更具可讀性。我能看到的最好的解決方法是使節點的數組，然後你：

public class Node { 

    private int value; 
    private Node[] nodes=new Node[2]; 
    private final int LOWER=0; 
    private final int HIGHER=1; 

    public void insert(int newValue) { 
     int index=LOWER; 
     if (newValue > value) 
      index=HIGHER; 

     if(nodes[index] == null) 
      nodes[index]=new Node(value); 
      else 
       nodes[index].insert(newValue); 
     } 
    } 

但我不會取代原來的，因爲，正如我所說，它更清晰。

我推薦這本重構書。一旦你真的得到面向對象，它確實有助於簡化你的代碼。將一個對象傳遞給靜態方法（不使用成員變量的方法）是一種無用的方式。

關於@ ted的評論和OO的更多考慮 - getLeft和getRight不應該成爲問題。在抽象之外不是必需的。

一般來說你可能需要在節點這些方法：

public boolean doesContain(int value) { 
    if(value == this.value) 
     return true 
    else 
     return nodes[ this.value < value ? LOWER : HIGHER].doesContain(value); 
} 

，也許

public void getValuesSorted(LinkedList l) { 
    nodes[LOWER].getValuesSorted(l); 
    l.put(value); 
    nodes[HIGHER].getValuesSorted(l); 
} 

然後，你甚至都不需要公開，它是你正在處理與 - 一棵樹 - 拜託OO抽象。

Answer 4

相反的：

if (dataIn <= nodeIn.getLeft().getData()) { 

...你想：

if (dataIn < nodeIn.getData()) { 

，則需要比較是與在當前節點的值被插入的值。

我將<=標誌更改爲<標誌，以避免重複。

所以你重構的代碼是：

public void insert(int dataIn) { 
    root = insert(root, dataIn); 
} 

private Node insert(Node nodeIn, int dataIn){ 
    if (nodeIn == null) { 
    nodeIn = new Node(null, null, dataIn); 
    } else { 
    if (dataIn < nodeIn.getData()) { 
     nodeIn.setLeft(insert(nodeIn.getLeft(), dataIn)); 
    } else { 
     nodeIn.setRight(insert(nodeIn.getRight(), dataIn)); 
    } 
    } 
    return nodeIn; 
} 

Answer 5

您的所有解決方案都沒有考慮到accoount如果節點是樹的中間插入會發生什麼。你假設它也是最小的或最大的。當你在樹的中間插入一些東西時，你會意識到操作變得更加複雜。

Answer 6

您可以使用下面的代碼來清除您的理解。大多數情況下，我們不使用任何其他類，一切都可以在單個Node類本身內完成。這裏是一個非常基本的例子，我認爲這可能會有幫助...另外，當我看到你有兩種方法只提供數據而不是根。相信我，最好是在你的主課堂上有根。推理我們有它方便我們需要緩存的地方。

public Node insert(Node root, Node newNode) { 
if (root == null) { 
    root = newNode; 
} else { 
    if(root.data > newNode.data) { 
     root.left = insert(root.left, newNode); 
    } else { 
     root.right = insert(root.right, newNode); 
    } 
} 
return root; 

}

直接從已初始化的任何類調用此方法。這裏是一個樣本PLZ檢查..

Node root = new Node(10); 
    root.insert(root, new Node(5)); 
    root.insert(root, new Node(3)); 
    root.insert(root, new Node(6)); 
    root.insert(root, new Node(1)); 

Answer 7

實際上，對於二叉樹沒有必要檢查插入元素是否或者是大於或左比父節點。我認爲沒有必要檢查這些條件。我們必須從用戶那裏輸入是右鍵還是左鍵。

Answer 8

public class TreeNode 
{ 
    private int data; 
    private TreeNode left; 
    private TreeNode right; 

    public Tree() 
    { 
     data = 0; 
     left = null; 
     right = null; 
    } 

    public Tree(int initialInfo, TreeNode initialLeft, TreeNode initialRight) 
    { 
     data = initialInfo; 
     left = initialLeft; 
     right = initialRight; 
    } 

    public void setLeft(TreeNode newLeft) 
    { 
     left = newLeft; 
    } 

    public void setRight(TreeNode newRight) 
    { 
     right = newRight; 
    } 

    public void insert(int element) 
    { 
     if(element <= data) 
     { 
      if(left == null) 
       setLeft(new TreeNode(element, null, null)); 
      else 
       left.insert(element); 
     } 
     else 
     { 
      if(right == null) 
       setRight(new TreeNode(element, null, null)); 
      else 
       right.insert(element); 
     } 
    } 

}