在Java中實現二進制搜索樹插入操作

Question

我有一個TreeNode類，它表示二叉樹的節點。

public class TreeNode { 

private static Object key=null; 
private static Object value=null; 
private TreeNode parent; 
private TreeNode left=null; 
private TreeNode right=null;  
/** 
* @return the value 
*/ 
public static Object getValue() { 
    return value; 
} 

/** 
* @param aValue the value to set 
*/ 
public static void setValue(Object aValue) { 
    value = aValue; 
} 


public TreeNode() 
{ 
    this(key,value); 
} 
public TreeNode(Object key,Object value) 
{ 
    this.key = key; 
    this.value = value; 
} 
/** 
* @return the key 
*/ 
public Object getKey() { 
    return key; 
} 

/** 
* @param key the key to set 
*/ 
public void setKey(Object key) { 
    this.key = key; 
} 

/** 
* @return the parent 
*/ 
public TreeNode getParent() { 
    return parent; 
} 

/** 
* @param parent the parent to set 
*/ 
public void setParent(TreeNode parent) { 
    this.parent = parent; 
} 

/** 
* @return the left 
*/ 
public TreeNode getLeftChild() { 
    return left; 
} 

/** 
* @param left the left to set 
*/ 
public void setLeftChild(TreeNode left) { 
    this.left = left; 
} 

/** 
* @return the right 
*/ 
public TreeNode getRightChild() { 
    return right; 
} 

/** 
* @param right the right to set 
*/ 
public void setRightChild(TreeNode right) { 
    this.right = right; 
} 

}

我有一個BinarySearchTree類

public class BinarySearchTree implements DataStructures.interfaces.BinarySearchTree { 
private int size=0; 
private TreeNode root = new TreeNode(); 

@Override 
public void insert(Object key, Object value) 
{ 
    insertOperation(key,value,root); 
} 

private void insertOperation(Object element, Object value, TreeNode node) 
{ 

    if(node.getKey() == null) { 
     node.setKey(element); 
     node.setValue(value);    
    } 
    else 
    { 
     if((int) node.getKey() > (int) element) 
     { 
      if(node.getLeftChild() != null) 
       insertOperation(element,value,node.getLeftChild()); 
      else 
      { 
       TreeNode child = new TreeNode(element, value); 
       child.setKey(element); 
       child.setValue(value); 
       child.setParent(node); 
       node.setLeftChild(child); 

       size++; 
      } 
     } 
     else if((int) node.getKey() <= (int) element) 
     { 
      if(node.getRightChild() != null) 
       insertOperation(element,value,node.getRightChild()); 
      else 
      { 
       TreeNode child = new TreeNode(element, value); 
       child.setKey(element); 
       child.setValue(value); 
       child.setParent(node); 
       node.setRightChild(child); 

       size++; 
      } 
     } 
    } 

    } 
    ///more methods 
} 

的問題是，當我創建一個子節點並設置父子鏈接。父節點（我傳遞的節點對象）的值也被更新並引用子對象。

這不是我的意圖。

我想創建一個treenode對象鏈，可以通過「根」treenode對象訪問。

但是這沒有發生，我不明白我做錯了什麼。

我知道問題在於這段代碼的邏輯（不僅僅是插入左側，而是插入左側子元素和右側元素），但我不明白究竟是什麼。

  if(node.getLeftChild() != null) 
       insertOperation(element,value,node.getLeftChild()); 
      else 
      { 
       TreeNode child = new TreeNode(element, value); 
       child.setKey(element); 
       child.setValue(value); 
       child.setParent(node); 
       node.setLeftChild(child); 

       size++; 
      } 

所有我告訴java做的是，如果有問題的節點沒有左子然後創建一個左子節點和當前節點的左側對象設置爲子對象。

如果有問題的節點確實有一個左邊的孩子，然後檢查該孩子，並通過爲該節點的孩子調用相同的函數來查看是否應該向左或向右插入新節點......我不'理解爲什麼節點的（TreeNode對象通過）鍵被更新，當我設置孩子的鍵值。

Answer 1

爲什麼你key和value靜態對象？這意味着所有TreeNodes將共享相同的鍵/值。刪除靜態關鍵字，它應該工作正常。

Answer 2

我不太讓你通過

The problem is that when I create a child node and set the parent child link. The value of parent node (the node object that I passed) also gets updated and refers to child object.

的意思，但我確實注意到一兩件事，這將導致一個錯誤：

else if((int) node.getKey() <= (int) element) 

當node.getKey（）==元素，這意味着bst已經有一個以「element」作爲關鍵字的節點，這應該是另一個特例。相反，你仍然在穿過其正確的孩子。

而且，這將是很好，如果你可以更清晰地闡述您的錯誤......