Advertisement
Guest User

Untitled

a guest
May 24th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 9.42 KB | None | 0 0
  1. //Изначальный план действий:
  2. //1. Получить массив чисел
  3. //2. Отсортировать этот массив по возрастанию
  4. //3. Написать алгоритм который структурирует всё это дерьмо складывая попарно наименьшие элементы
  5. //3.1 Реадизовать алгоритм который удаляет из используемого массива числа которые мы уже использовали и заменять
  6.             // их на новые полученные(?)
  7. //4. Преобразовать массив в дерево по алгоритму хаффмана
  8.  
  9. import java.io.BufferedReader;
  10. import java.io.IOException;
  11. import java.io.InputStreamReader;
  12. import java.util.*;
  13.  
  14.  
  15. class  SortedByValue implements Comparator<TreeNode> {
  16.     public int compare(TreeNode obj1, TreeNode obj2)
  17.     {
  18.         int val1 = obj1.getValue();
  19.         int val2 = obj2.getValue();
  20.         if(val1 < val2)
  21.             return -1;
  22.         else if(val1 > val2)
  23.             return 1;
  24.         return 0;
  25.     }
  26. }
  27. class TreeNode {
  28.     private TreeNode left;
  29.     private TreeNode right;
  30.     private int value;
  31.     private TreeNode parent;
  32.  
  33.     public void setValue(int value) {
  34.         this.value = value;
  35.     }
  36.  
  37.     public void setLeft(TreeNode left) {
  38.         this.left = left;
  39.     }
  40.  
  41.     public void setRight(TreeNode right) {
  42.         this.right = right;
  43.     }
  44.  
  45.     public int getValue() {
  46.         return value;
  47.     }
  48.  
  49.     public TreeNode getLeft() {
  50.         return left;
  51.     }
  52.  
  53.     public TreeNode getRight() {
  54.         return right;
  55.     }
  56.  
  57.     public void setParent(TreeNode parent) {
  58.         this.parent = parent;
  59.     }
  60.  
  61.     public TreeNode getParent() {
  62.         return parent;
  63.     }
  64.  
  65.     public TreeNode(int value)
  66.     {
  67.  
  68.         this.value = value;
  69.         this.left = null;
  70.         this.right = null;
  71.     }
  72.  
  73.  
  74. }
  75. public class TreeContainer {
  76.  
  77.     public static int max(int val1, int val2)
  78.     {
  79.         if(val1>val2)
  80.             return val1;
  81.         else if(val1<val2)
  82.             return val2;
  83.         return val1;
  84.     }
  85.     public static LinkedList<TreeNode> ScanArr() throws IOException{
  86.         LinkedList<TreeNode> list = new LinkedList<TreeNode>();
  87.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  88.         String secretString;
  89.         System.out.println("Вводите элемента, для остановки ввода элементов введите \"stop\"");
  90.         while(true)
  91.         {
  92.             secretString = reader.readLine();
  93.             if(secretString.equals("stop"))
  94.                 break;
  95.             list.add(new TreeNode(Integer.parseInt(secretString)));
  96.         }
  97.         return list;
  98.     } //метод считывающий список. Статус: проверено
  99.  
  100.  
  101.     public static void printList(List<TreeNode> list)
  102.     {
  103.         Iterator<TreeNode> it = list.iterator();
  104.         while(it.hasNext())
  105.         {
  106.             System.out.println(it.next().getValue());
  107.         }
  108.     } //метод выводящий список значений дерева. Статус: проверено
  109.  
  110.  
  111.     public static void printTree(TreeNode head)
  112.     {
  113.         System.out.println(head.getValue());
  114.         if(head.getLeft() != null)
  115.             printTree(head.getLeft());
  116.         if(head.getRight() != null)
  117.             printTree(head.getRight());
  118.     } //метод выводящий список значений дерева. Костыльная версия для проверки утери элементов. Статус: проверено
  119.  
  120.     public static int treeHeigh(TreeNode head)
  121.     {
  122.         TreeNode temp = head;
  123.         int h1 = 0,h2 = 0;
  124.         if(head == null)
  125.             return 0;
  126.         if(head.getLeft()!=null)
  127.         {
  128.             h1 = treeHeigh(head.getLeft());
  129.         }
  130.         if(head.getRight()!=null)
  131.         {
  132.             h2 = treeHeigh(head.getRight());
  133.         }
  134.  
  135.         return (max(h1,h2)+1);
  136.     } // Функция, возвращающая высоту дерева(невероятно). Статус: проверено
  137.  
  138.     public static void reverse(TreeNode head)
  139.     {
  140.         TreeNode temp = new TreeNode(0);
  141.         if(head != null)
  142.         {
  143.             if(head.getLeft() != null && head.getRight() !=null)
  144.             {
  145.                 temp = head.getLeft();
  146.                 head.setLeft(head.getRight());
  147.                 head.setRight(temp);
  148.                 reverse(head.getRight());
  149.             }
  150.             else if(head.getLeft() != null && head.getRight() == null)
  151.                 reverse(head.getLeft());
  152.             else if(head.getLeft()==null && head.getRight() != null)
  153.                 reverse(head.getRight());
  154.  
  155.         }
  156.     }//Функция создающая зеркальную версию дерева. Статус: вроде работает) Сложно проверить, из-за
  157.         //больной реализации вывода, но на бумажке всё сошлось
  158.  
  159.     public static int lookup(TreeNode head, int target)
  160.     {
  161.         if(head == null)
  162.             return 0;
  163.         else{
  164.             if(target == head.getValue())
  165.                 return 1;
  166.             else
  167.             {
  168.                 if(target < head.getValue())
  169.                     return lookup(head.getLeft(),target);
  170.                 else
  171.                     return lookup(head.getRight(),target);
  172.             }
  173.         }
  174.     }//Проверка нахождения элемента в дереве. Статус: проверено
  175.  
  176.     public static int getMaxWidth(TreeNode head)
  177.     {
  178.         int maxWidth = 0;
  179.         int i = 0;
  180.         int width = 0;
  181.         int h = treeHeigh(head);
  182.         for(i = 1;i<h;i++)
  183.         {
  184.             width = getWidth(head, i);
  185.             if(width > maxWidth)
  186.                 maxWidth = width;
  187.         }
  188.         return maxWidth;
  189.     } //Поиск максимальной ширины дерева. Статус: Oo
  190.  
  191.     public static int getWidth(TreeNode head, int level)
  192.     {
  193.         if(head == null)
  194.             return 0;
  195.         if(level == 1)
  196.             return 1;
  197.         else if(level > 1)
  198.             return getWidth(head.getLeft(), level - 1) + getWidth(head.getRight(), level-1);
  199.         return getWidth(head.getRight(),level-1);
  200.     }
  201.  
  202.     public static int size(TreeNode head)
  203.     {
  204.         if(head == null)
  205.             return 0;
  206.         else
  207.             return size(head.getLeft()) + 1 + size(head.getRight());
  208.     } // Возвращает количество элементов в дереве. Статус: проверено
  209.  
  210.     public static boolean sameTree(TreeNode a, TreeNode b)
  211.     {
  212.         if(a == null && b == null) return true;
  213.         else if(a!= null && b != null)
  214.         {
  215.             return((a.getValue() == b.getValue()) && sameTree(a.getLeft(),b.getLeft()) && sameTree(a.getRight(),b.getRight()));
  216.         }
  217.         else return false;
  218.     }//Проверка деревьев на равенство. Статус: поверю на слово :peka:
  219.  
  220.     public static void main(String[] args) throws IOException {
  221.         LinkedList<TreeNode> list = ScanArr();
  222.         list.sort(new SortedByValue());
  223.         System.out.println("Изначальный список: ");
  224.         printList(list);
  225.  
  226.         while(list.size()>1) {
  227.             int newVal = 0;
  228.             Iterator<TreeNode> it = list.listIterator();
  229.             for (int i = 0; i < 2; i++) {
  230.                 newVal += list.get(i).getValue();
  231.             }
  232.             TreeNode temp = new TreeNode(newVal);
  233.             temp.setLeft(list.get(0));
  234.             temp.setRight(list.get(1));
  235.             list.removeFirst();
  236.             list.removeFirst();
  237.             list.add(temp);
  238.             list.sort(new SortedByValue());
  239.             System.out.println("\n Список после итерации:");
  240.             printList(list);
  241.         } //почему-то этот алгоритм работает. Я сам в шоке.
  242.             //Прим: list.get(0) - это последний оставшийся элемент в результате работы этого алгоритма и
  243.                                                         // является конечной вершиной созданного дерева
  244.         System.out.println("\nПроверка функции вывода элементов дерева:");
  245.         printTree(list.get(0));
  246.         System.out.println("Высота этого дерева: " + treeHeigh(list.get(0)));
  247.         System.out.println("\n Проверка работы функции зеркализации: ");
  248.         reverse(list.get(0));
  249.         printTree(list.get(0));
  250.         System.out.println("Проверка нахождения элемента 26 в дерева. Результат: " + lookup(list.get(0),26));
  251.         System.out.println("Проверка нахождения элемента 25 в дерева. Результат: " + lookup(list.get(0),25));
  252.         System.out.println("Проверка нахождения максимальной ширины дерева. Результат: " + getMaxWidth(list.get(0)));
  253.         System.out.println("Количество элементов в дереве: " + size(list.get(0)));
  254.  
  255.  
  256.     }
  257. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement