Когда вы пишете рекурсивный метод, первое, что вам нужно, это условие, которое завершает рекурсию. В вашем случае есть два следующих условия.
- Вы нашли сотрудника, которого ищете.
- Вы достигли конца дерева.
Рекурсия должна быть прекращена, если выполняется одно из вышеуказанных условий. В вашем случае завершение рекурсии означает, что метод должен возвращать значение.
Если условие завершения не истинно, метод должен вызвать сам себя, но с другими значениями для параметров метода.
Вот мой рекурсивный метод поиска. Дополнительные пояснения появляются после кода.
int search(int employee, int manager, Node node) {
if (node != null) {
if (employee == node.key) {
return manager;
}
manager = node.key;
if (employee < node.key) {
return search(employee, manager, node.left);
}
else {
return search(employee, manager, node.right);
}
}
else {
return -1;
}
}
Параметры метода следующие:
- сотрудник - сотрудник, для которого выполняется поиск
- менеджер - руководитель следующий параметр
- узел - узел в дереве, который будет проверяться, чтобы узнать, является ли его
key сотрудником, которого мы ищем
Мы начинаем поиск с root дерева и пройти вниз по узлам дерева. Следовательно, первоначальный вызов метода, который, вероятно, будет в методе main(), будет выглядеть следующим образом:
tree.search(sch, -1, tree.root)
Согласно вашим примерным данным, sch равно 55. Обратите внимание, что при первоначальном вызове менеджер равно -1, поскольку root дерева не имеет менеджера. Таким образом, если sch равно root key, метод вернет -1.
Поскольку мы знаем, что key в левом дочернем узле ниже, а правый дочерний key выше, нам не нужно перебирать каждый узел. Таким образом, метод вызывает себя с соответствующим дочерним узлом. Также мы сохраняем текущий key, потому что если key дочернего узла - это тот, который мы ищем, то key этого узла является менеджером.
Если параметр node в методе search() имеет значение null, это означает, что мы достигли конца дерева, что означает, что мы не нашли искомое значение. Значение -1 (минус один) является условным обозначением значения, которое указывает, что поиск завершился неудачно. Метод indexOf() в классе String является примером метода, также использующего это соглашение.
Наконец, я использовал код, который вы разместили в своем вопросе. Я добавил только указанный выше метод, а также вызов этого метода из метода main(). Я добавил начальный вызов метода search() в качестве последней строки в методе main().
Для полноты, вот весь код:
import java.util.Scanner;
public class BinarySearchTree {
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
// The method I added.
int search(int employee, int manager, Node node) {
if (node != null) {
if (employee == node.key) {
return manager;
}
manager = node.key;
if (employee < node.key) {
return search(employee, manager, node.left);
}
else {
return search(employee, manager, node.right);
}
}
else {
return -1;
}
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int sch = sc.nextInt();
for (int i = 0; i < num; i++) {
tree.insert(sc.nextInt());
}
tree.inorder();
System.out.printf("Manager is %d%n", tree.search(sch, -1, tree.root)); // changed this line to print only manager.
}
}