Как получить преемника узла бинарного дерева поиска java - PullRequest
Новая
       24

Как получить преемника узла бинарного дерева поиска java

0 голосов
/ 19 июня 2020

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

public class NonEmptyBinaryTree <T extends Comparable<T>> extends BinaryTree<T> {

    T data;     // data of the root node of this tree
    BinaryTree<T> left, right;  // left and right sub-trees



    /**
     * Create a NonEmptyBinaryTree tree with root node.
     * The tree will not have sub-trees.
     * 
     * @param data the data of the root node.
     */
    public NonEmptyBinaryTree(T data) {
        this.data = data;
        left = new EmptyBinaryTree<T>();
        right = new EmptyBinaryTree<T>();
    }

    public static void main(String[] args) {
        NonEmptyBinaryTree tree = new NonEmptyBinaryTree(7); //Root node
        tree.insert(3);
        tree.insert(4);
        tree.insert(12);
        tree.insert(10);
        tree.insert(2);
        tree.insert(9);
        tree.insert(18);


        System.out.println(tree.successor(12));

    }

    /** 
     * Create a NonEmptyBinaryTree with left and right sub-trees
     * @param data value of the root node
     * @param left sub-tree of the new NonEmptyBinaryTree tree
     * @param right sub-tree of the new NonEmptyBinaryTree tree
     */
    public NonEmptyBinaryTree(T data, BinaryTree<T> left, BinaryTree<T> right) {

        this.data = data;
        this.left = left;
        this.right = right;
    }


    @Override
    public T successor(T d) {

        T datas = null;
//      T parent;

        if (d.compareTo(this.data) < 0){ //If its less than the root
            parent = this.data;
            return left.successor(d);}

        if (d.compareTo(this.data) > 0){ //If its less than the root
            parent = this.data;
            return right.successor(d);}


        if (d.equals(this.data)){ //We found the node
            datas = this.data;
            if (this.right!=null)
            datas = this.right.smallest();
//          if (this.right==null)
                //When there is no right child
        }

        return datas;
    }
...