Как сделать метод добавления с BinarySearchTree в Java? - PullRequest
Новая
       38

Как сделать метод добавления с BinarySearchTree в Java?

0 голосов
/ 30 апреля 2019

У меня проблемы с моим методом add, я полагаю, что ошибка возникает в параметрах, передаваемых в public-методе, однако я не уверен, что мой приватный вспомогательный метод также не добавляет правильные переменные.

Вот инструкция к моему addMethod

Метод add (E) может дополнительно вызвать метод assignFirst () для назначения первого атрибута в случае его изменения. Вспомогательный метод add теперь должен назначать ссылки «parent» и «next» каждого узла при создании нового узла.

• Параметр «parent» должен ссылаться на родительский узел вновь созданного узла, поэтому, когда Создав новый узел, вы можете просто назначить его родителя этому параметру.

• Параметр «prev» должен ссылаться на предыдущий узел вновь созданного узла, поэтому, когда Создав новый узел, вы можете просто обновить «следующие» ссылки в соответствующих узлы. Самое сложное - это узнать, какие значения передать при вызове надстройки. вспомогательный метод. Вот логика:

• Если возвращаемое значение вспомогательного помощника должно быть правильным потомком, то этот правильный потомок предыдущий узел должен быть таким же, как его родитель. Необязательный getPrevNode не поможет здесь, так как предыдущий узел будет родителем нового узла, а новый узел не еще прилагается к дереву.

• Если возвращаемое значение вспомогательного помощника должно быть левым потомком, то предыдущий узел этого левого потомка может быть определен необязательным методом getPrevNode, запрашивая его для узла, который перед текущим параметром узла.

Вот мой код: 

public void add(E value)
{
    this.root = add(root, value, root, null);
    assignFirst();
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value, BSTNode<E> parent, BSTNode<E> prev)
{
    if (node == null)
    {
        node = new BSTNode<E>(value);
        node.parent = parent;
        node.next = prev;

        this.numElements++;
    }
    else if (node.data.compareTo(value) > 0)
    {
        node.left = add(node.left, value, node , getPrevNode(node));
    }
    else if (node.data.compareTo(value) < 0)
    {
        node.right = add(node.right, value, node, node.parent);
    }
    return node;
}
private void assignFirst()
{
    BSTNode<E> node = root;
    while(node.left != null)
    {
        node = node.left;
    }
    first = node;
}
 private BSTNode<E> getPrevNode(BSTNode<E> node)
{
    if(node.left != null)
    {
        node = node.left;
        while(node.right != null)
        {
            node = node.right;
        }
        return node;
    }
    else if(node.parent != null)
    {
        if(node.parent.right == node)
        {
            return node.parent;
        }
        if(node.parent.left == node)
        {
            while(node.parent != null && node.parent.left == node)
            {
                node = node.parent;
            }
            if(node == root)
            {
              return null;
            }
            else
            {
              return node.parent;
            }
        }
    }
    return null;
}

Вот некоторая справочная информация, однако я опускаю некоторые методы, поскольку они не имеют отношения к тому, что я пытаюсь выяснить. Поэтому я сокращаю это. 

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;
private BSTNode<E> first;
// post: constructs an empty search tree
public BinarySearchTree()
{
    this.root = null;
    this.numElements = 0;
}
 public class Iterator
{
    private BSTNode<E> currentNode;

    public Iterator()
    {
        currentNode = first;
    }

    public boolean hasNext()
    {
        return currentNode != null;
    }

    public E next()
    {
        E value = currentNode.data;
        currentNode = currentNode.next;
        return value;
    }
}
private static class BSTNode<E>
{
    public E data;
    public BSTNode<E> left;
    public BSTNode<E> right;
    public BSTNode<E> parent;
    public BSTNode<E> next;

    public BSTNode(E data)
    {
        this(data, null, null, null, null);
    }

    public BSTNode(E data, BSTNode<E> left, BSTNode<E> right, BSTNode<E> parent, BSTNode<E> next)
    {
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
        this.next = next;
    }
  }
}

1 Ответ

0 голосов
/ 02 мая 2019

Это был строгий процесс, вот что я получил 

public void add(E value)
{
    this.root = add(root, value, root, null);
    assignFirst();
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value, BSTNode<E> parent, BSTNode<E> prev)
{
    if (node == null)
    {
        node = new BSTNode<E>(value);
        node.parent = parent;
        if(prev == null)
        {
            node.next = parent;
        }
        else
        {
            node.next = prev.next;
            prev.next = node;
        }
        this.numElements++;
    }
    else if (node.data.compareTo(value) > 0)
    {
        node.left = add(node.left, value, node , getPrevNode(node));
    }
    else if (node.data.compareTo(value) < 0)
    {
        node.right = add(node.right, value, node, node);
    }
    return node;
}
...