Guest User

Untitled

a guest
Feb 27th, 2012
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 7.99 KB | None | 0 0
  1. Условие
  2. Найти пути минимальной длины между корнем и листьями и удалить средние по значению вершины этих путей (левым удалением), если они существуют .
  3. Замечание.
  4. Если некоторая вершина является средней по значению для нескольких путей минимальной длины, то удаляется она только один раз.(см. Пример 2).
  5.  
  6.  
  7. Входные данные
  8. tst.in содержит последовательность чисел — ключей дерева.
  9.  
  10. Выходные данные
  11. tst.out содержит массив вершин, полученный прямым левым обходом итогового дерева.
  12.  
  13. Пример
  14. tst.in
  15. 10
  16. 15
  17. 13
  18. 18
  19. 5
  20. 8
  21. 3
  22.  
  23. tst.out
  24. 10
  25. 3
  26. 18
  27.  
  28.  
  29. import java.io.*;
  30. import java.util.ArrayList;
  31. import java.util.Collections;
  32. import java.util.TreeSet;
  33.  
  34. import static java.lang.System.out;
  35.  
  36. /**
  37.  * Created by IntelliJ IDEA.
  38.  * User: Andrew
  39.  * Date: 12.02.2011
  40.  * Time: 19:53:21
  41.  * To change this template use File | Settings | File Templates.
  42.  */
  43.  
  44.  
  45. public class Solution {
  46.     interface Position {
  47.         public int element();
  48.     }
  49.  
  50.     static class LinkedBinaryTree {
  51.         public void setMinLen(int minLen) {
  52.             this.minLen = minLen;
  53.         }
  54.  
  55.         public void setCurLen(int curLen) {
  56.             this.curLen = curLen;
  57.         }
  58.  
  59.         public ArrayList<Integer> arrayOfLeafs = new ArrayList<Integer>();
  60.         public int minLen;
  61.         public int curLen;
  62.  
  63.         class BTNode implements Position {
  64.             private int element;
  65.             private BTNode left, right;
  66.  
  67.             public BTNode(int el, BTNode l, BTNode r) {
  68.                 setElement(el);
  69.                 setLeft(l);
  70.                 setRight(r);
  71.             }
  72.  
  73.             public int element() {
  74.                 return element;
  75.             }
  76.  
  77.             public void setElement(int el) {
  78.                 element = el;
  79.             }
  80.  
  81.             public BTNode getLeft() {
  82.                 return left;
  83.             }
  84.  
  85.             public void setLeft(BTNode v) {
  86.                 left = v;
  87.             }
  88.  
  89.             public BTNode getRight() {
  90.                 return right;
  91.             }
  92.  
  93.             public void setRight(BTNode v) {
  94.                 right = v;
  95.             }
  96.         }
  97.  
  98.         private Position root; // reference to the root
  99.         private int size; // number of nodes
  100.  
  101.         public LinkedBinaryTree() {
  102.             root = null;
  103.             size = 0;
  104.         }
  105.  
  106.         public LinkedBinaryTree(int rootEl) {
  107.             root = new BTNode(rootEl, null, null);
  108.             size = 1;
  109.         }
  110.  
  111.         public int size() {
  112.             return size;
  113.         }
  114.  
  115.         public boolean isEmpty() {
  116.             return (size == 0);
  117.         }
  118.  
  119.         public boolean isExternalLeft(Position v) {
  120.             return (((BTNode) v).getLeft() == null);
  121.         }
  122.  
  123.         public boolean isExternalRight(Position v) {
  124.             return (((BTNode) v).getRight() == null);
  125.         }
  126.  
  127.         public boolean isRoot(Position v) {
  128.             return (v == root());
  129.         }
  130.  
  131.         public Position root() {
  132.             return root;
  133.         }
  134.  
  135.         public Position leftChild(Position v) {
  136.             return ((BTNode) v).getLeft();
  137.         }
  138.  
  139.         public Position rightChild(Position v) {
  140.             return ((BTNode) v).getRight();
  141.         }
  142.  
  143.         private int setElement(Position v, int o) {
  144.             int temp = ((BTNode) v).element();
  145.             ((BTNode) v).setElement(o);
  146.             return temp;
  147.         }
  148.  
  149.         private void expandExternalLeft(Position v) {
  150.             if (isExternalLeft(v)) {
  151.                 ((BTNode) v).setLeft(new BTNode(0, null, null));
  152.                 size++;
  153.             }
  154.         }
  155.  
  156.         private void expandExternalRight(Position v) {
  157.             if (isExternalRight(v)) {
  158.                 ((BTNode) v).setRight(new BTNode(0, null, null));
  159.                 size++;
  160.             }
  161.         }
  162.  
  163.         private void addElementFromRoot(Position pos, int el) {
  164.             if (pos != null) {
  165.                 if (pos.element() == el)
  166.                     return;
  167.                 else {
  168.                     if (pos.element() < el) {
  169.                         if (isExternalRight(pos)) {
  170.                             expandExternalRight(pos);
  171.                             setElement(rightChild(pos), el);
  172.                         } else {
  173.                             addElementFromRoot(rightChild(pos), el);
  174.                         }
  175.                     } else {
  176.                         if (pos.element() > el) {
  177.                             if (isExternalLeft(pos)) {
  178.                                 expandExternalLeft(pos);
  179.                                 setElement(leftChild(pos), el);
  180.                             } else {
  181.                                 addElementFromRoot(leftChild(pos), el);
  182.                             }
  183.                         }
  184.                     }
  185.                 }
  186.             } else {
  187.                 root = new BTNode(el, null, null);
  188.                 size++;
  189.             }
  190.         }
  191.  
  192.  
  193.         private void rootLeftRightFromRoot(Position pos, StringBuilder outString) {
  194.             if (pos == null) {
  195.                 return;
  196.             }
  197.             outString.append(pos.element()+"\r\n");
  198.             if (leftChild(pos) != null)
  199.                 rootLeftRightFromRoot(leftChild(pos), outString);
  200.             if (rightChild(pos) != null)
  201.                 rootLeftRightFromRoot(rightChild(pos), outString);
  202.         }
  203.  
  204.  
  205.         public void addElement(int el) {
  206.             addElementFromRoot(root(), el);
  207.         }
  208.  
  209.         public void deleteElement(int el) {
  210.             Position x = root, y = null;
  211.  
  212.             while (x != null) {
  213.                 if (el == x.element()) {
  214.                     break;
  215.                 } else {
  216.                     y = x;
  217.                     if (el < x.element()) {
  218.                         x = ((BTNode) x).getLeft();
  219.                     } else {
  220.                         x = ((BTNode) x).getRight();
  221.                     }
  222.                 }
  223.  
  224.             }
  225.  
  226.             if (x == null)
  227.                 return;
  228.  
  229.             if (((BTNode) x).getLeft() == null) {
  230.                 if (y == null) {
  231.                     root = ((BTNode) x).getLeft();
  232.                 } else {
  233.                     if (x == ((BTNode) y).getRight()) {
  234.                         ((BTNode) y).setRight(((BTNode) x).getRight());
  235.                     } else {
  236.                         ((BTNode) y).setLeft(((BTNode) x).getRight());
  237.                     }
  238.                 }
  239.             } else {
  240.                 Position leftMost = ((BTNode) x).getLeft();
  241.                 y = null;
  242.                 while (((BTNode) leftMost).getRight() != null) {
  243.                     y = leftMost;
  244.                     leftMost = ((BTNode) leftMost).getRight();
  245.                 }
  246.                 if (y != null) {
  247.                     ((BTNode) y).setRight(((BTNode) leftMost).getLeft());
  248.                 } else {
  249.                     ((BTNode) x).setLeft(((BTNode) leftMost).getLeft());
  250.                 }
  251.                 ((BTNode) x).setElement((leftMost).element());
  252.             }
  253.         }
  254.  
  255.         public void rootLeftRight(String path) throws IOException {
  256.             FileOutputStream fos = new FileOutputStream(path);
  257.             DataOutputStream dos = new DataOutputStream(fos);
  258.             StringBuilder temp = new StringBuilder();
  259.  
  260.             rootLeftRightFromRoot(root(), temp);
  261.  
  262.             dos.writeBytes(temp.toString());
  263.  
  264.         }
  265.  
  266.         public void assistRootLeftRight(Position pos) {
  267.             if (pos == null) {
  268.                 return;
  269.             }
  270.  
  271.             curLen++;
  272.             if (rightChild(pos) == null && leftChild(pos) == null) {
  273.                 if (curLen == minLen) {
  274.                     arrayOfLeafs.add(pos.element());
  275.                 }
  276.                 if (curLen < minLen) {
  277.                     minLen = curLen;
  278.                     arrayOfLeafs.clear();
  279.                     arrayOfLeafs.add(pos.element());
  280.                 }
  281.             }
  282.             if (leftChild(pos) != null) {
  283.                 assistRootLeftRight(leftChild(pos));
  284.             }
  285.             if (rightChild(pos) != null) {
  286.                 assistRootLeftRight(rightChild(pos));
  287.             }
  288.  
  289.             curLen--;
  290.  
  291.         }
  292.  
  293.         public void findAndDeleteElements() {
  294.             if (minLen % 2 != 0) {
  295.                 TreeSet<Integer> setOfNodesToDelete = new TreeSet<Integer>();
  296.                 for (Integer li : arrayOfLeafs) {
  297.                     Position pos = root;
  298.                     ArrayList<Integer> tempArray = new ArrayList<Integer>();
  299.  
  300.                     while (li != pos.element()) {
  301.                         tempArray.add(pos.element());
  302.                         if (li > pos.element())
  303.                             pos = ((BTNode) pos).getRight();
  304.                         else if (li < pos.element()) {
  305.                             pos = ((BTNode) pos).getLeft();
  306.                         }
  307.                     }
  308.                     tempArray.add(li);
  309.  
  310.                     Collections.sort(tempArray);
  311.                     setOfNodesToDelete.add(tempArray.get(minLen / 2));
  312.                 }
  313.  
  314.                 for (Integer li : setOfNodesToDelete) {
  315.                     this.deleteElement(li);
  316.                 }
  317.             }
  318.         }
  319.     }
  320.     public static void main(String[] args) {
  321.  
  322.         LinkedBinaryTree tree = new LinkedBinaryTree();
  323.  
  324.         FileInputStream fis = null;
  325.         try {
  326.             fis = new FileInputStream("tst.in");
  327.             BufferedReader br = new BufferedReader(new InputStreamReader(fis));
  328.             String newLine;
  329.             while ((newLine = br.readLine()) != null){
  330.                 tree.addElement(Integer.parseInt(newLine));
  331.             }
  332.  
  333.             tree.setCurLen(0);
  334.             tree.setMinLen(tree.size());
  335.  
  336.             tree.assistRootLeftRight(tree.root());
  337.             tree.findAndDeleteElements();
  338.             tree.rootLeftRight("tst.out");
  339.  
  340.  
  341.         } catch (FileNotFoundException e) {
  342.             out.println("No Such File");  //To change body of catch statement use File | Settings | File Templates.
  343.         } catch (IOException e) {
  344.             out.println("File Exception");  //To change body of catch statement use File | Settings | File Templates.
  345.         }
  346.     }
  347. }
Add Comment
Please, Sign In to add comment