在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”作为关键字的节点，这应该是另一个特例。相反，你仍然在穿过其正确的孩子。

而且，这将是很好，如果你可以更清晰地阐述您的错误......