Описал дерево, заполнил его и при проверки увидел что заполняется только правая часть дерева. Нашел данный способ на англ. кластере ютуба и не могу понять что не так, у автора вроде все нормально работало.
Класс BinaryTree
Код:
package lab4;
public class BinaryTree {
Node root;
public void addNode(int key, String eng, String rus) {
Node newNode = new Node(key, eng, rus);
if (root == null) {
root = newNode;
} else {
Node focusNode = root;
Node parent;
while (true) {
parent = focusNode;
if (key < focusNode.key) {
focusNode = focusNode.leftChild;
if (focusNode == null) {
parent.leftChild = newNode;
return;
}
} else {
focusNode = focusNode.rightChild;
if (focusNode == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}
// Обход бинарного дерева
// Все узлы посещаются в порядке возрастания
// Рекурсия используется для перехода к одному узлу и
// затем перейти к его дочерним узлам и т.д.
// Сверху вниз
public void preorderTraverseTree(Node focusNode) {
if (focusNode != null) {
System.out.println(focusNode);
preorderTraverseTree(focusNode.leftChild);
preorderTraverseTree(focusNode.rightChild);
}
}
// Снизу вверх
public void postOrderTraverseTree(Node focusNode) {
if (focusNode != null) {
postOrderTraverseTree(focusNode.leftChild);
postOrderTraverseTree(focusNode.rightChild);
System.out.println(focusNode);
}
}
// Поиск узла
public Node findNode(int key) {
// Начать с верхушки дерева
Node focusNode = root;
// Пока мы не нашли узел
// Продолжать поиски
while (focusNode.key != key) {
// Если мы должны искать влево
if (key < focusNode.key) {
// Сдвиг фокуса узла к левому ребенку
focusNode = focusNode.leftChild;
} else {
// Сдвиг фокуса узла к правому ребенку
focusNode = focusNode.rightChild;
}
// Узел не найден
if (focusNode == null)
return null;
}
return focusNode;
}
// Удаление элемента
public boolean remove(int key) {
Node focusNode = root;
Node parent = root;
// Поиск в правой или в левой части
boolean isItALeftChild = true;
while (focusNode.key != key) {
parent = focusNode;
// Идентично метода поиска
if (key < focusNode.key) {
isItALeftChild = true;
focusNode = focusNode.leftChild;
} else {
isItALeftChild = false;
focusNode = focusNode.rightChild;
}
if (focusNode == null)
return false;
}
// Если узел не имеет детей то удалить его, присвоить нулл
if (focusNode.leftChild == null && focusNode.rightChild == null) {
// И если это корень
if (focusNode == root)
root = null;
// Если он помечен как левый ребенок удалить его как парент
else if (isItALeftChild)
parent.leftChild = null;
// И наоборот для правого ребенка
else
parent.rightChild = null;
}
// Если не правый ребенок
else if (focusNode.rightChild == null) {
if (focusNode == root)
root = focusNode.leftChild;
// Если фокус узла был слева от родительского
// Переместить фокус Узлов влево от ребенка до родительского узла
else if (isItALeftChild)
parent.leftChild = focusNode.leftChild;
// И наоборот для правого ребенка
else
parent.rightChild = focusNode.leftChild;
}
// Тоже самое делаем если не левый ребенок
else if (focusNode.leftChild == null) {
if (focusNode == root)
root = focusNode.rightChild;
else if (isItALeftChild)
parent.leftChild = focusNode.rightChild;
else
parent.rightChild = focusNode.rightChild;
}
// Двое детей, поэтому мне нужно, найти удаленную замену узлов
else {
Node replacement = getReplacementNode(focusNode);
// Если focusNode является корнем переставить корень с заменой
if (focusNode == root)
root = replacement;
// Если удаленный узел был левым потомком
// Сделать замену на левый ребенок
else if (isItALeftChild)
parent.leftChild = replacement;
// И наоборот для правого
else
parent.rightChild = replacement;
replacement.leftChild = focusNode.leftChild;
}
return true;
}
public Node getReplacementNode(Node replacedNode) {
Node replacementParent = replacedNode;
Node replacement = replacedNode;
Node focusNode = replacedNode.rightChild;
// Пока не закончатся левые потомки
while (focusNode != null) {
replacementParent = replacement;
replacement = focusNode;
focusNode = focusNode.leftChild;
}
// Если замена не является правильным ребенком
// Перемещаем замену в родителей
// LeftChild слот и перемещаем в него замененные узлы
// Правого ребенка на замену RightChild
if (replacement != replacedNode.rightChild) {
replacementParent.leftChild = replacement.rightChild;
replacement.rightChild = replacedNode.rightChild;
}
return replacement;
}
public static void printBinaryTree(Node root, int level){
if(root==null)
return;
printBinaryTree(root.rightChild, level+1);
if(level!=0){
for(int i=0;i<level-1;i++)
System.out.print("|\t");
System.out.println("|-------"+root.key);
}
else
System.out.println(root.key);
printBinaryTree(root.leftChild, level+1);
}
// Вложеный клас Node с конструктором
class Node {
private int key;
String eng;
String rus;
Node leftChild;
Node rightChild;
Node(int key, String eng, String rus) {
this.key = key;
this.eng = eng;
this.rus = rus;
}
public String toString() {
return "Ключ = " + key + " Слова: " + eng + " ----> " + rus;
}
}
}
Класс Main
Код:
package lab4;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
BinaryTree theTree = new BinaryTree();
String eng = null, rus = null;
Scanner in = new Scanner(System.in);
int n = 0;
System.out.println("Введите количество элементов, которые будут добавлены в дерево");
n = in.nextInt();
System.out.println("Заполнение дерева, индексы присваиваются от 1 до n");
for (int i = 1; i < n + 1; i++) {
System.out.println("Английское слово --> Entere --> Русское соответствие");
theTree.addNode(i, eng(eng), rus(rus));
}
int exit = 0;
theTree.printBinaryTree(theTree.root, n);
// .....................................................
}
public static String eng (String eng) {
Scanner in = new Scanner(System.in);
return eng = in.nextLine();
}
public static String rus (String rus) {
Scanner in = new Scanner(System.in);
return rus = in.nextLine();
}
}