Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Изначальный план действий:
- //1. Получить массив чисел
- //2. Отсортировать этот массив по возрастанию
- //3. Написать алгоритм который структурирует всё это дерьмо складывая попарно наименьшие элементы
- //3.1 Реадизовать алгоритм который удаляет из используемого массива числа которые мы уже использовали и заменять
- // их на новые полученные(?)
- //4. Преобразовать массив в дерево по алгоритму хаффмана
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.*;
- class SortedByValue implements Comparator<TreeNode> {
- public int compare(TreeNode obj1, TreeNode obj2)
- {
- int val1 = obj1.getValue();
- int val2 = obj2.getValue();
- if(val1 < val2)
- return -1;
- else if(val1 > val2)
- return 1;
- return 0;
- }
- }
- class TreeNode {
- private TreeNode left;
- private TreeNode right;
- private int value;
- private TreeNode parent;
- public void setValue(int value) {
- this.value = value;
- }
- public void setLeft(TreeNode left) {
- this.left = left;
- }
- public void setRight(TreeNode right) {
- this.right = right;
- }
- public int getValue() {
- return value;
- }
- public TreeNode getLeft() {
- return left;
- }
- public TreeNode getRight() {
- return right;
- }
- public void setParent(TreeNode parent) {
- this.parent = parent;
- }
- public TreeNode getParent() {
- return parent;
- }
- public TreeNode(int value)
- {
- this.value = value;
- this.left = null;
- this.right = null;
- }
- }
- public class TreeContainer {
- public static int max(int val1, int val2)
- {
- if(val1>val2)
- return val1;
- else if(val1<val2)
- return val2;
- return val1;
- }
- public static LinkedList<TreeNode> ScanArr() throws IOException{
- LinkedList<TreeNode> list = new LinkedList<TreeNode>();
- BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
- String secretString;
- System.out.println("Вводите элемента, для остановки ввода элементов введите \"stop\"");
- while(true)
- {
- secretString = reader.readLine();
- if(secretString.equals("stop"))
- break;
- list.add(new TreeNode(Integer.parseInt(secretString)));
- }
- return list;
- } //метод считывающий список. Статус: проверено
- public static void printList(List<TreeNode> list)
- {
- Iterator<TreeNode> it = list.iterator();
- while(it.hasNext())
- {
- System.out.println(it.next().getValue());
- }
- } //метод выводящий список значений дерева. Статус: проверено
- public static void printTree(TreeNode head)
- {
- System.out.println(head.getValue());
- if(head.getLeft() != null)
- printTree(head.getLeft());
- if(head.getRight() != null)
- printTree(head.getRight());
- } //метод выводящий список значений дерева. Костыльная версия для проверки утери элементов. Статус: проверено
- public static int treeHeigh(TreeNode head)
- {
- TreeNode temp = head;
- int h1 = 0,h2 = 0;
- if(head == null)
- return 0;
- if(head.getLeft()!=null)
- {
- h1 = treeHeigh(head.getLeft());
- }
- if(head.getRight()!=null)
- {
- h2 = treeHeigh(head.getRight());
- }
- return (max(h1,h2)+1);
- } // Функция, возвращающая высоту дерева(невероятно). Статус: проверено
- public static void reverse(TreeNode head)
- {
- TreeNode temp = new TreeNode(0);
- if(head != null)
- {
- if(head.getLeft() != null && head.getRight() !=null)
- {
- temp = head.getLeft();
- head.setLeft(head.getRight());
- head.setRight(temp);
- reverse(head.getRight());
- }
- else if(head.getLeft() != null && head.getRight() == null)
- reverse(head.getLeft());
- else if(head.getLeft()==null && head.getRight() != null)
- reverse(head.getRight());
- }
- }//Функция создающая зеркальную версию дерева. Статус: вроде работает) Сложно проверить, из-за
- //больной реализации вывода, но на бумажке всё сошлось
- public static int lookup(TreeNode head, int target)
- {
- if(head == null)
- return 0;
- else{
- if(target == head.getValue())
- return 1;
- else
- {
- if(target < head.getValue())
- return lookup(head.getLeft(),target);
- else
- return lookup(head.getRight(),target);
- }
- }
- }//Проверка нахождения элемента в дереве. Статус: проверено
- public static int getMaxWidth(TreeNode head)
- {
- int maxWidth = 0;
- int i = 0;
- int width = 0;
- int h = treeHeigh(head);
- for(i = 1;i<h;i++)
- {
- width = getWidth(head, i);
- if(width > maxWidth)
- maxWidth = width;
- }
- return maxWidth;
- } //Поиск максимальной ширины дерева. Статус: Oo
- public static int getWidth(TreeNode head, int level)
- {
- if(head == null)
- return 0;
- if(level == 1)
- return 1;
- else if(level > 1)
- return getWidth(head.getLeft(), level - 1) + getWidth(head.getRight(), level-1);
- return getWidth(head.getRight(),level-1);
- }
- public static int size(TreeNode head)
- {
- if(head == null)
- return 0;
- else
- return size(head.getLeft()) + 1 + size(head.getRight());
- } // Возвращает количество элементов в дереве. Статус: проверено
- public static boolean sameTree(TreeNode a, TreeNode b)
- {
- if(a == null && b == null) return true;
- else if(a!= null && b != null)
- {
- return((a.getValue() == b.getValue()) && sameTree(a.getLeft(),b.getLeft()) && sameTree(a.getRight(),b.getRight()));
- }
- else return false;
- }//Проверка деревьев на равенство. Статус: поверю на слово :peka:
- public static void main(String[] args) throws IOException {
- LinkedList<TreeNode> list = ScanArr();
- list.sort(new SortedByValue());
- System.out.println("Изначальный список: ");
- printList(list);
- while(list.size()>1) {
- int newVal = 0;
- Iterator<TreeNode> it = list.listIterator();
- for (int i = 0; i < 2; i++) {
- newVal += list.get(i).getValue();
- }
- TreeNode temp = new TreeNode(newVal);
- temp.setLeft(list.get(0));
- temp.setRight(list.get(1));
- list.removeFirst();
- list.removeFirst();
- list.add(temp);
- list.sort(new SortedByValue());
- System.out.println("\n Список после итерации:");
- printList(list);
- } //почему-то этот алгоритм работает. Я сам в шоке.
- //Прим: list.get(0) - это последний оставшийся элемент в результате работы этого алгоритма и
- // является конечной вершиной созданного дерева
- System.out.println("\nПроверка функции вывода элементов дерева:");
- printTree(list.get(0));
- System.out.println("Высота этого дерева: " + treeHeigh(list.get(0)));
- System.out.println("\n Проверка работы функции зеркализации: ");
- reverse(list.get(0));
- printTree(list.get(0));
- System.out.println("Проверка нахождения элемента 26 в дерева. Результат: " + lookup(list.get(0),26));
- System.out.println("Проверка нахождения элемента 25 в дерева. Результат: " + lookup(list.get(0),25));
- System.out.println("Проверка нахождения максимальной ширины дерева. Результат: " + getMaxWidth(list.get(0)));
- System.out.println("Количество элементов в дереве: " + size(list.get(0)));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement