在Java中实现二叉搜索树插入操作

Question

我有一个表示二叉树节点的树节点的树节点。

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要做的就是，如果所讨论的节点没有左子节点，那么创建一个左子节点并将当前节点的左侧对象设置为子对象。

如果有问题的节点有一个左边的子节点，那么检查这个子节点，并通过为有问题的节点的子节点调用相同的函数来查看新节点应该插入左边还是右边...我不明白为什么当我设置孩子的键值时，node的(传递的TreeNode对象)键会更新。

Answer 1

我不太明白你的意思

问题是，当我创建一个子节点并设置父子链接时。父节点（我传递的节点对象）的值也会更新并引用子对象。

但是我注意到了一件会导致错误的事情:

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

当 node.getKey（） == 元素时，这意味着 bst 已经有一个以“元素”为键的节点，这应该是另一种特殊情况。相反，你仍然在穿越它正确的孩子。

另外，如果你能更清楚地阐述你的错误就好了…

Answer 2

为什么您的key和value是静态对象？这意味着所有TreeNodes将共享相同的键/值。删除静态关键字，它应该可以正常工作。