java - BinarySearchTree 不向树添加元素

Question

为什么如果我放

tree.addElement(10, tree.root);

它有效，但如果我再次这样做

tree.addElement(20, tree.root);

不起作用？我只想向树添加元素。我的方法有什么问题吗？编译器给我的错误很简单:

在LinkedBinarySearchTree.addElement(LinkedBinarySearchTree.java:68)

public void addElement(T element, BinaryTreeNode node) 
{
    if (!(element instanceof Comparable))
        throw new NonComparableElementException("LinkedBinarySearchTree");

    Comparable<T> comparableElement = (Comparable<T>)element;

    if (isEmpty())
        root = new BinaryTreeNode<T>(element);
    else 
    {
        if (comparableElement.compareTo(root.getElement()) < 0)
        {
            if (root.getLeft() == null) 
                this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
            else
                addElement(element, root.getLeft());
        }
        else
        {
            if (root.getRight() == null) 
                this.getRootNode().setRight(new BinaryTreeNode<T>(element));
            else
                addElement(element, root.getRight());
        }
    }
    modCount++;

}

这是其余的代码:

 public class BinaryTreeNode<T>
{
protected T element;
protected BinaryTreeNode<T> left, right;

/**
 * Creates a new tree node with the specified data.
 *
 * @param obj the element that will become a part of the new tree node
 */
public BinaryTreeNode(T obj) 
{
    element = obj;
    left = null;
    right = null;
}

/**
 * Creates a new tree node with the specified data.
 *
 * @param obj the element that will become a part of the new tree node
 * @param left the tree that will be the left subtree of this node
 * @param right the tree that will be the right subtree of this node
 */
public BinaryTreeNode(T obj, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right) 
{
    element = obj;
    if (left == null)
        this.left = null;
    else
        this.left = left.getRootNode();

    if (right == null)
        this.right = null;
    else
        this.right = right.getRootNode();
}

/**
 * Returns the number of non-null children of this node.
 *
 * @return the integer number of non-null children of this node 
 */
public int numChildren() 
{
    int children = 0;

    if (left != null)
        children = 1 + left.numChildren();

    if (right != null)
        children = children + 1 + right.numChildren();

    return children;
}

/**
 * Return true if this node is a leaf and false otherwise.
 *
 * @return true if this node is a leaf and false otherwise
 */
public boolean isLeaf() 
{
    return (numChildren() == 0);
}

/**
 * Return the element at this node.
 *
 * @return the element stored at this node
 */
public T getElement() 
{
    return element;
}

/**
 * Return the right child of this node.
 *
 * @return the right child of this node
 */
public BinaryTreeNode<T> getRight() 
{
    return right;
}

/**
 * Sets the right child of this node.
 *
 * @param node the right child of this node
 */
public void setRight(BinaryTreeNode<T> node) 
{
    right = node;
}

/**
 * Return the left child of this node.
 *
 * @return the left child of the node
 */
public BinaryTreeNode<T> getLeft() 
{
    return left;
}

/**
 * Sets the left child of this node.
 *
 * @param node the left child of this node
 */
public void setLeft(BinaryTreeNode<T> node) 
{
    left = node;
}

}

* Creates an empty binary search tree.
 */
public LinkedBinarySearchTree() 
{
    super();
}

/**
 * Creates a binary search with the specified element as its root.
 *
 * @param element the element that will be the root of the new binary
 *        search tree
 */
public LinkedBinarySearchTree(T element) 
{
    super(element);

    if (!(element instanceof Comparable))
        throw new NonComparableElementException("LinkedBinarySearchTree");
}

/**
 * Adds the specified object to the binary search tree in the
 * appropriate position according to its natural order.  Note that
 * equal elements are added to the right.
 *
 * @param element the element to be added to the binary search tree
 * @return 
 */
public void addElement(T element, BinaryTreeNode node) 
{
    if (!(element instanceof Comparable))
        throw new NonComparableElementException("LinkedBinarySearchTree");

    Comparable<T> comparableElement = (Comparable<T>)element;

    if (isEmpty())
        root = new BinaryTreeNode<T>(element);
    else 
    {
        if (comparableElement.compareTo(root.getElement()) < 0)
        {
            if (root.getLeft() == null) 
                this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
            else
                addElement(element, root.getLeft());
        }
        else
        {
            if (root.getRight() == null) 
                this.getRootNode().setRight(new BinaryTreeNode<T>(element));
            else
                addElement(element, root.getRight());
        }
    }
    modCount++;

}

/**
 * Adds the specified object to the binary search tree in the
 * appropriate position according to its natural order.  Note that
 * equal elements are added to the right.
 *
 * @param element the element to be added to the binary search tree
 */
public  LinkedBinarySearchTree(T element, BinaryTreeNode<T> node) 
{
    Comparable<T> comparableElement = (Comparable<T>)element;

    if (comparableElement.compareTo(node.getElement()) < 0)
    {
        if (node.getLeft() == null) 
            node.setLeft(new BinaryTreeNode<T>(element));
        else
            addElement(element, node.getLeft());
    }
    else
    {
        if (node.getRight() == null) 
            node.setRight(new BinaryTreeNode<T>(element));
        else
            addElement(element, node.getRight());
    }
}

Answer 1

我怀疑你得到了 StackOverflowError因为你正在路过root.getLeft (其他类似)而不是 node.getLeft .

if (isEmpty())
    root = new BinaryTreeNode<T>(element);

上面的内容在第一次插入元素时创建一个根，这是正确的。

遍历逻辑必须从传递给方法的当前节点开始，而不是从根开始。

这里是一个更正的:

else 
{
    if (comparableElement.compareTo(node.getElement()) < 0)
    {
        if (node.getLeft() == null) 
            node.setLeft(new BinaryTreeNode<T>(element));
        else
            addElement(element, node.getLeft());
    }
    else
    {
        if (node.getRight() == null) 
            node.setRight(new BinaryTreeNode<T>(element));
        else
            addElement(element, node.getRight());
    }
}

奖金:您可以将类型参数设置为 T有界摆脱Comparable检查。

引用文献:

Java- The meaning of <T extends Comparable<T>> ?

Bounded Type Parameters Oracle Tutorial