Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 13.02.2017, 16:04   #1
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию Заполняется только правая часть дерева

Описал дерево, заполнил его и при проверки увидел что заполняется только правая часть дерева. Нашел данный способ на англ. кластере ютуба и не могу понять что не так, у автора вроде все нормально работало.
Класс 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();
    }
}
Max00766 вне форума Ответить с цитированием
Старый 13.02.2017, 16:20   #2
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Я понял что я тормоз) Ключи то заполняются циклически по порядку, поэтому одна сторона и заполняется) Я правильно понял?
Max00766 вне форума Ответить с цитированием
Старый 13.02.2017, 19:19   #3
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

Дерево (при условии двух развилок) - это что вроде такого:

10.jpg

а у тебя получается обычный массив - это когда каждый последующий экземпляр класса расположен после предыдущего :

11.jpg


Но, если ты будешь переделывать логику работы программы, подумай по какому принципу будет строится дерево, - учти то что тебе надо будет потом искать английские слова.
Т.е., логично предположить, что английские слова будут как-то участвовать в формировании внешнего вида этого самого дерева, - чтобы потом путь к слову (по дереву) легко был найден.

Последний раз редактировалось ura_111; 13.02.2017 в 19:44.
ura_111 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Пропадает правая часть сайта, при уменьшении окна браузера vodolas HTML и CSS 4 27.02.2016 14:54
Правая колонка IE Shaman-King HTML и CSS 3 27.11.2013 23:02
Правая часть окна консоли YourLastSong Общие вопросы C/C++ 0 19.12.2010 23:09
Как вытащить только часть символов из ячейки? Berkley Microsoft Office Excel 5 22.12.2006 00:43