BinarySearchTree не добавляет элементы в дерево

zerocrys спросил: 12 мая 2018 в 05:02 в: java

Почему это, если я положил

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());
    }
}

1 ответ

user7 ответил: 12 мая 2018 в 05:15

Я подозреваю, что вы получаете StackOverflowError, поскольку вы передаете root.getLeft (и другие аналогично) вместо node.getLeft.

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

Приведенное выше создает корень при вставке элемента, который является правильным.

Логика обхода должна начинаться с текущего узла, переданного методу и а не root.

Вот исправленный:

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- Значение <T extends Comparable<T>>?

Ограниченные параметры типа Oracle Tutorial