Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Условие
- Найти пути минимальной длины между корнем и листьями и удалить средние по значению вершины этих путей (левым удалением), если они существуют .
- Замечание.
- Если некоторая вершина является средней по значению для нескольких путей минимальной длины, то удаляется она только один раз.(см. Пример 2).
- Входные данные
- tst.in содержит последовательность чисел — ключей дерева.
- Выходные данные
- tst.out содержит массив вершин, полученный прямым левым обходом итогового дерева.
- Пример
- tst.in
- 10
- 15
- 13
- 18
- 5
- 8
- 3
- tst.out
- 10
- 3
- 18
- import java.io.*;
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.TreeSet;
- import static java.lang.System.out;
- /**
- * Created by IntelliJ IDEA.
- * User: Andrew
- * Date: 12.02.2011
- * Time: 19:53:21
- * To change this template use File | Settings | File Templates.
- */
- public class Solution {
- interface Position {
- public int element();
- }
- static class LinkedBinaryTree {
- public void setMinLen(int minLen) {
- this.minLen = minLen;
- }
- public void setCurLen(int curLen) {
- this.curLen = curLen;
- }
- public ArrayList<Integer> arrayOfLeafs = new ArrayList<Integer>();
- public int minLen;
- public int curLen;
- class BTNode implements Position {
- private int element;
- private BTNode left, right;
- public BTNode(int el, BTNode l, BTNode r) {
- setElement(el);
- setLeft(l);
- setRight(r);
- }
- public int element() {
- return element;
- }
- public void setElement(int el) {
- element = el;
- }
- public BTNode getLeft() {
- return left;
- }
- public void setLeft(BTNode v) {
- left = v;
- }
- public BTNode getRight() {
- return right;
- }
- public void setRight(BTNode v) {
- right = v;
- }
- }
- private Position root; // reference to the root
- private int size; // number of nodes
- public LinkedBinaryTree() {
- root = null;
- size = 0;
- }
- public LinkedBinaryTree(int rootEl) {
- root = new BTNode(rootEl, null, null);
- size = 1;
- }
- public int size() {
- return size;
- }
- public boolean isEmpty() {
- return (size == 0);
- }
- public boolean isExternalLeft(Position v) {
- return (((BTNode) v).getLeft() == null);
- }
- public boolean isExternalRight(Position v) {
- return (((BTNode) v).getRight() == null);
- }
- public boolean isRoot(Position v) {
- return (v == root());
- }
- public Position root() {
- return root;
- }
- public Position leftChild(Position v) {
- return ((BTNode) v).getLeft();
- }
- public Position rightChild(Position v) {
- return ((BTNode) v).getRight();
- }
- private int setElement(Position v, int o) {
- int temp = ((BTNode) v).element();
- ((BTNode) v).setElement(o);
- return temp;
- }
- private void expandExternalLeft(Position v) {
- if (isExternalLeft(v)) {
- ((BTNode) v).setLeft(new BTNode(0, null, null));
- size++;
- }
- }
- private void expandExternalRight(Position v) {
- if (isExternalRight(v)) {
- ((BTNode) v).setRight(new BTNode(0, null, null));
- size++;
- }
- }
- private void addElementFromRoot(Position pos, int el) {
- if (pos != null) {
- if (pos.element() == el)
- return;
- else {
- if (pos.element() < el) {
- if (isExternalRight(pos)) {
- expandExternalRight(pos);
- setElement(rightChild(pos), el);
- } else {
- addElementFromRoot(rightChild(pos), el);
- }
- } else {
- if (pos.element() > el) {
- if (isExternalLeft(pos)) {
- expandExternalLeft(pos);
- setElement(leftChild(pos), el);
- } else {
- addElementFromRoot(leftChild(pos), el);
- }
- }
- }
- }
- } else {
- root = new BTNode(el, null, null);
- size++;
- }
- }
- private void rootLeftRightFromRoot(Position pos, StringBuilder outString) {
- if (pos == null) {
- return;
- }
- outString.append(pos.element()+"\r\n");
- if (leftChild(pos) != null)
- rootLeftRightFromRoot(leftChild(pos), outString);
- if (rightChild(pos) != null)
- rootLeftRightFromRoot(rightChild(pos), outString);
- }
- public void addElement(int el) {
- addElementFromRoot(root(), el);
- }
- public void deleteElement(int el) {
- Position x = root, y = null;
- while (x != null) {
- if (el == x.element()) {
- break;
- } else {
- y = x;
- if (el < x.element()) {
- x = ((BTNode) x).getLeft();
- } else {
- x = ((BTNode) x).getRight();
- }
- }
- }
- if (x == null)
- return;
- if (((BTNode) x).getLeft() == null) {
- if (y == null) {
- root = ((BTNode) x).getLeft();
- } else {
- if (x == ((BTNode) y).getRight()) {
- ((BTNode) y).setRight(((BTNode) x).getRight());
- } else {
- ((BTNode) y).setLeft(((BTNode) x).getRight());
- }
- }
- } else {
- Position leftMost = ((BTNode) x).getLeft();
- y = null;
- while (((BTNode) leftMost).getRight() != null) {
- y = leftMost;
- leftMost = ((BTNode) leftMost).getRight();
- }
- if (y != null) {
- ((BTNode) y).setRight(((BTNode) leftMost).getLeft());
- } else {
- ((BTNode) x).setLeft(((BTNode) leftMost).getLeft());
- }
- ((BTNode) x).setElement((leftMost).element());
- }
- }
- public void rootLeftRight(String path) throws IOException {
- FileOutputStream fos = new FileOutputStream(path);
- DataOutputStream dos = new DataOutputStream(fos);
- StringBuilder temp = new StringBuilder();
- rootLeftRightFromRoot(root(), temp);
- dos.writeBytes(temp.toString());
- }
- public void assistRootLeftRight(Position pos) {
- if (pos == null) {
- return;
- }
- curLen++;
- if (rightChild(pos) == null && leftChild(pos) == null) {
- if (curLen == minLen) {
- arrayOfLeafs.add(pos.element());
- }
- if (curLen < minLen) {
- minLen = curLen;
- arrayOfLeafs.clear();
- arrayOfLeafs.add(pos.element());
- }
- }
- if (leftChild(pos) != null) {
- assistRootLeftRight(leftChild(pos));
- }
- if (rightChild(pos) != null) {
- assistRootLeftRight(rightChild(pos));
- }
- curLen--;
- }
- public void findAndDeleteElements() {
- if (minLen % 2 != 0) {
- TreeSet<Integer> setOfNodesToDelete = new TreeSet<Integer>();
- for (Integer li : arrayOfLeafs) {
- Position pos = root;
- ArrayList<Integer> tempArray = new ArrayList<Integer>();
- while (li != pos.element()) {
- tempArray.add(pos.element());
- if (li > pos.element())
- pos = ((BTNode) pos).getRight();
- else if (li < pos.element()) {
- pos = ((BTNode) pos).getLeft();
- }
- }
- tempArray.add(li);
- Collections.sort(tempArray);
- setOfNodesToDelete.add(tempArray.get(minLen / 2));
- }
- for (Integer li : setOfNodesToDelete) {
- this.deleteElement(li);
- }
- }
- }
- }
- public static void main(String[] args) {
- LinkedBinaryTree tree = new LinkedBinaryTree();
- FileInputStream fis = null;
- try {
- fis = new FileInputStream("tst.in");
- BufferedReader br = new BufferedReader(new InputStreamReader(fis));
- String newLine;
- while ((newLine = br.readLine()) != null){
- tree.addElement(Integer.parseInt(newLine));
- }
- tree.setCurLen(0);
- tree.setMinLen(tree.size());
- tree.assistRootLeftRight(tree.root());
- tree.findAndDeleteElements();
- tree.rootLeftRight("tst.out");
- } catch (FileNotFoundException e) {
- out.println("No Such File"); //To change body of catch statement use File | Settings | File Templates.
- } catch (IOException e) {
- out.println("File Exception"); //To change body of catch statement use File | Settings | File Templates.
- }
- }
- }
Add Comment
Please, Sign In to add comment