0

Я уже написал несколько методов, связанных с моей проблемой. Сейчас у меня есть два метода, написанных с использованием рекурсии (addBSTRecursion (int element) и searchBSTRecursion (int element)). И теперь мне нужно реализовать (итеративно) метод поиска BST (Pair <BinaryTreeNode, BinaryTreeNode> searchBST (int element)), возвращающий узел, содержащий искомое значение и его предшественник.

  • если искомый элемент отсутствует в дереве, первый элемент пары равен нулю.
  • если первый элемент пары является корнем (у него нет предшественника), то второй элемент пары равен нулю. Вот мой класс Pair:
public class Pair<T1, T2> {
    public T1 first;
    public T2 second;

    public Pair(T1 a, T2 b) {
        first = a;
        second = b;
    }
}

Вот как мне удалось реализовать метод (Pair <BinaryTreeNode, BinaryTreeNode> searchBST (int element)), но, к сожалению, он не работает должным образом.

@Override
public Pair<BinaryTreeNode, BinaryTreeNode> searchBST(int element) {
    int current = 0;
    while (element != data) {
        if (element < data) {
            current = left.data;
        } else {
            current = right.data;
        }
    }
    Pair pair = new Pair(element, current);
    return pair;
}

К примеру у меня есть следущее бинарное дерево(это дерево как раз у меня в программе):

        1
    3
            4
        6
            7
8
    10
            13
        14

Что я хочу получить по выполнению метода (Pair<BinaryTreeNode, BinaryTreeNode> searchBST(int element))
Например когда я выполню object.searchBSTRecursion(6) (где object - обьект класса Node), в консоле я хочу получить следующее:

6, 3

Где 6 - узел который я написал для поиска, а 3 - это его родительский узел
Если я бы выполнил следующее object.searchBSTRecursion(8), я хотел бы получить:

8, null

Где 8 - узел который я написал для поиска, а null - я получил потому что у этого узла нету родительского
Так же если я выполню например object.searchBSTRecursion(25) (а такого узла вообще нету в моем дереве), то я должен получить следующее:

null, null

Где первый null - потому что узел который я подал для поиска - не существует, а второй - null - потому что если нету узла которого я ищу, то и родительского узла у него тоже нету.
Сейчас же, когда я проверяю работу своего метода, то вообще получаю какой то бесконечный цикл while с его то условием. (Не советую запускать этот метод, без его модификации)
Если честно, пока не знаю, как правильно реализовать этот метод, буду рад любым подсказкам. А также внизу я добавляю остальные классы.

public abstract class BinaryTreeNode {
    protected int data; // value stored in the node
    protected BinaryTreeNode left, right; // left and right sub-trees

    // constructor
    public BinaryTreeNode(int data) {
        this.data = data;
    }

    // recursively adds an item to the BST
    // @param new data to be stored in the new node
    public abstract void addBSTRecursion(int element);

    // prints the tree
    // for example, for a tree:
    //        7
    //    6        8
    // 2     7  4     9
    //
    // write:
    //
    //      2
    //   6
    //      7
    // 7
    //      4
    //   8
    //      9

    // method pseudocode
    // if there is a left subtree then print the left one (recursive call)
    // write out gaps (depending on level), write out data, go to new line
    // if it is right, print the right one (recursive call)
    // @param level the distance of the node from the root. We start from 0.
    public abstract void print(int level);

    // recursive searches the BST.
    // returns true if it finds an element with the given value
    // @param searched value searched
    // @return true if the given value is in the tree, false otherwise
    public abstract boolean searchBSTRecursion(int element);

    // iterative lookup of values in the BST
    // returns a pair: node containing the searched element and its predecessor.
    // if the searched element is not in the tree, the first element of the pair is null.
    // if the first element of the pair is a root (it has no predecessor), then the second element of the pair is null.
    // @param searched value searched
    // @return pair of nodes: the first is the node containing the value searched for, or null if not found;
    // the second element of the pair is the parent of the node (or null if the value is at the root of the tree)
    public abstract Pair < BinaryTreeNode, BinaryTreeNode > searchBST(int element);
}
public class Node extends BinaryTreeNode {
    public Node(int data) {
        super(data);
    }

    @Override
    public void addBSTRecursion(int element) {
        Node node = new Node(element);
        if (element < data) {
            if (left != null) {
                left.addBSTRecursion(element);
            } else {
                left = node;
            }
        } else {
            if (right != null) {
                right.addBSTRecursion(element);
            } else {
                right = node;
            }
        }
    }

    @Override
    public void print(int level) {
        if (left != null) {
            left.print(level + 4);
        }
        for (int i = 0; i < level; i++) {
            System.out.print(" ");
        }

        System.out.print(data + "\n");

        if (right != null) {
            right.print(level + 4);
        }
    }

    @Override
    public boolean searchBSTRecursion(int element) {
        if (element == data) {
            return true;
        } else if (element < data) {
            if (left != null && left.searchBSTRecursion(element)) {
                return true;
            } else {
                return false;
            }
        } else {
            if (right != null && right.searchBSTRecursion(element)) {
                return true;
            } else {
                return false;
            }
        }
    }

    @Override
    public Pair<BinaryTreeNode, BinaryTreeNode> searchBST(int element) {
        int current = 0;
        while (element != data) {
            if (element < data) {
                current = left.data;
            } else {
                current = right.data;
            }
        }
        Pair pair = new Pair(element, current);
        return pair;
    }
}

public class Main {

    public static void main(String[] args) {
        Node node = new Node(8);

        node.addBSTRecursion(3);
        node.addBSTRecursion(10);

        node.addBSTRecursion(1);
        node.addBSTRecursion(6);

        node.addBSTRecursion(14);

        node.addBSTRecursion(4);
        node.addBSTRecursion(7);

        node.addBSTRecursion(13);


        node.print(0);

        System.out.print(node.searchBSTRecursion(15));
    }
}

16
  • Этот код не компилируется.
    – user176262
    12 дек 2021 в 4:07
  • в чем именно проблема?
    – qqq
    12 дек 2021 в 4:08
  • Откуда я знаю, в чем проблема, что Вы поместили в вопрос код, который не компилируется?
    – user176262
    12 дек 2021 в 4:09
  • @Igor, отредактировал вопрос, попробуйте сейчас!
    – qqq
    12 дек 2021 в 4:17
  • Вы шутите? Я не буду ничего "пробовать". Если я вижу, что в вопросе код, который не скомпилируется (глазами, без никакого компилирования), я ставлю минус и голосую за закрытие вопроса. Это Вам повезло, что я сегодня добрый и написал за что минус.
    – user176262
    12 дек 2021 в 4:23

1 ответ 1

1
@Override
public Pair<BinaryTreeNode, BinaryTreeNode> searchBST(int element) {
    int current = 0;
    while (element != data) {
        if (element < data) {
            current = left.data;
        } else {
            current = right.data;
        }
    }
    Pair pair = new Pair(element, current);
    return pair;
}

Как может "работать" метод, у которого в сигнатуре объявлен возвращаемый тип Pair<BinaryTreeNode, BinaryTreeNode>, а возвращать Вы пытаетесь new Pair(element, current); с двумя целыми?

  return new Pair<BinaryTreeNode, BinaryTreeNode>(current, parent);

Теперь про цикл while.

Предположим, element не равен data. Так он и не станет ей никогда равным, так как ни element ни data в цикле не меняются. Таким образом, этот цикл никогда не закончится. Значит current должен быть не ноль (откуда здесь, вообще, ноль? почему ноль?), a

BinaryTreeNode current = this;

Так как Вам нужен еще и родитель, то понадобится еще одна локальная переменная

BinaryTreeNode parent = null;
1
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – Grundy
    12 дек 2021 в 16:51

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.