Kame3

Inorder следбеник - [дрво]

Jan 17th, 2021 (edited)
765
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Inorder следбеник Problem 2 (0 / 0)
  2.  
  3. Дадено ви е бинарно пребарувачко дрво. Напишете рекурзивна функција inorderSuccessor која што за дадена вредност во дрвото ќе го најде нејзиниот следбеник.
  4.  
  5. Име на класата: InorderSuccessor
  6.  
  7.  
  8. import java.io.BufferedReader;
  9. import java.io.InputStreamReader;
  10.  
  11. class BNode<E extends Comparable<E>> {
  12.    
  13.     public E info;
  14.     public BNode<E> left;
  15.     public BNode<E> right;
  16.    
  17.     public BNode(E info) {
  18.         this.info = info;
  19.         left = null;
  20.         right = null;
  21.     }
  22.    
  23.     public BNode(E info, BNode<E> left, BNode<E> right) {
  24.         this.info = info;
  25.         this.left = left;
  26.         this.right = right;
  27.     }
  28.    
  29. }
  30.  
  31. class BinarySearchTree<E extends Comparable<E>> {
  32.    
  33.     /** The tree root. */
  34.     private BNode<E> root;
  35.    
  36.     /**
  37.      * Construct the tree.
  38.      */
  39.     public BinarySearchTree() {
  40.         root = null;
  41.     }
  42.  
  43.     /**
  44.      * Insert into the tree; duplicates are ignored.
  45.      * @param x the item to insert.
  46.      */
  47.     public void insert(E x) {
  48.         root = insert(x, root);
  49.     }
  50.  
  51.     /**
  52.      * Remove from the tree. Nothing is done if x is not found.
  53.      * @param x the item to remove.
  54.      */
  55.     public void remove(E x) {
  56.         root = remove(x, root);
  57.     }
  58.  
  59.     /**
  60.      * Find the smallest item in the tree.
  61.      * @return smallest item or null if empty.
  62.      */
  63.     public E findMin() {
  64.         return elementAt(findMin(root));
  65.     }
  66.  
  67.     /**
  68.      * Find the largest item in the tree.
  69.      * @return the largest item of null if empty.
  70.      */
  71.     public E findMax() {
  72.         return elementAt(findMax(root));
  73.     }
  74.  
  75.     /**
  76.      * Find an item in the tree.
  77.      * @param x the item to search for.
  78.      * @return the matching item or null if not found.
  79.      */
  80.     public BNode<E> find(E x) {
  81.         return find(x, root);
  82.     }
  83.  
  84.     /**
  85.      * Make the tree logically empty.
  86.      */
  87.     public void makeEmpty() {
  88.         root = null;
  89.     }
  90.  
  91.     /**
  92.      * Test if the tree is logically empty.
  93.      * @return true if empty, false otherwise.
  94.      */
  95.     public boolean isEmpty() {
  96.         return root == null;
  97.     }
  98.  
  99.     /**
  100.      * Print the tree contents in sorted order.
  101.      */
  102.     public void printTree() {
  103.         if (isEmpty()) {
  104.             System.out.println("Empty tree");
  105.         } else {
  106.             printTree(root);
  107.         }
  108.     }
  109.  
  110.     /**
  111.      * Internal method to get element field.
  112.      * @param t the node.
  113.      * @return the element field or null if t is null.
  114.      */
  115.     private E elementAt(BNode<E> t) {
  116.         if (t == null)
  117.             return null;
  118.         return t.info;
  119.     }
  120.  
  121.     /**
  122.      * Internal method to insert into a subtree.
  123.      * @param x the item to insert.
  124.      * @param t the node that roots the tree.
  125.      * @return the new root.
  126.      */
  127.     private BNode<E> insert(E x, BNode<E> t) {
  128.         if (t == null) {
  129.             t = new BNode<E>(x, null, null);
  130.         } else if (x.compareTo(t.info) < 0) {
  131.             t.left = insert(x, t.left);
  132.         } else if (x.compareTo(t.info) > 0) {
  133.             t.right = insert(x, t.right);
  134.         } else;  // Duplicate; do nothing
  135.         return t;
  136.     }
  137.  
  138.     /**
  139.      * Internal method to remove from a subtree.
  140.      * @param x the item to remove.
  141.      * @param t the node that roots the tree.
  142.      * @return the new root.
  143.      */
  144.     private BNode<E> remove(Comparable x, BNode<E> t) {
  145.         if (t == null)
  146.             return t;   // Item not found; do nothing
  147.        
  148.         if (x.compareTo(t.info) < 0) {
  149.             t.left = remove(x, t.left);
  150.         } else if (x.compareTo(t.info) > 0) {
  151.             t.right = remove(x, t.right);
  152.         } else if (t.left != null && t.right != null) { // Two children
  153.             t.info = findMin(t.right).info;
  154.             t.right = remove(t.info, t.right);
  155.         } else {
  156.             if (t.left != null)
  157.                 return t.left;
  158.             else
  159.                 return t.right;
  160.         }
  161.         return t;
  162.     }
  163.  
  164.     /**
  165.      * Internal method to find the smallest item in a subtree.
  166.      * @param t the node that roots the tree.
  167.      * @return node containing the smallest item.
  168.      */
  169.     private BNode<E> findMin(BNode<E> t) {
  170.         if (t == null) {
  171.             return null;
  172.         } else if (t.left == null) {
  173.             return t;
  174.         }
  175.         return findMin(t.left);
  176.     }
  177.  
  178.     /**
  179.      * Internal method to find the largest item in a subtree.
  180.      * @param t the node that roots the tree.
  181.      * @return node containing the largest item.
  182.      */
  183.     private BNode<E> findMax(BNode<E> t) {
  184.         if (t == null) {
  185.             return null;
  186.         } else if (t.right == null) {
  187.             return t;
  188.         }
  189.         return findMax(t.right);
  190.     }
  191.  
  192.     /**
  193.      * Internal method to find an item in a subtree.
  194.      * @param x is item to search for.
  195.      * @param t the node that roots the tree.
  196.      * @return node containing the matched item.
  197.      */
  198.     private BNode<E> find(E x, BNode<E> t) {
  199.         if (t == null)
  200.             return null;
  201.        
  202.         if (x.compareTo(t.info) < 0) {
  203.             return find(x, t.left);
  204.         } else if (x.compareTo(t.info) > 0) {
  205.             return find(x, t.right);
  206.         } else {
  207.             return t;    // Match
  208.         }
  209.     }
  210.  
  211.     /**
  212.      * Internal method to print a subtree in sorted order.
  213.      * @param t the node that roots the tree.
  214.      */
  215.     private void printTree(BNode<E> t) {
  216.         if (t != null) {
  217.             printTree(t.left);
  218.             System.out.println(t.info);
  219.             printTree(t.right);
  220.         }
  221.     }
  222.    
  223.     public E getSuccessor(BNode<E> t, E x) {
  224.         E succ = null;
  225.         if(t.info.equals(x) && t.right != null)
  226.             return findMin(t.right).info;
  227.         if(t.info.equals(x) && t.right == null)
  228.             return succ;
  229.         if(t.info.compareTo(x) > 0){
  230.             E tmp = t.info;
  231.             succ = getSuccessor(t.left,x);
  232.             if(succ == null)
  233.                 succ = tmp;
  234.         }
  235.         if(t.info.compareTo(x) < 0)
  236.             succ = getSuccessor(t.right,x);
  237.        
  238.         return succ;
  239.     }
  240.    
  241.     public E getSuccessor(E x) {
  242.         return getSuccessor(root, x);
  243.     }
  244.    
  245. }
  246.  
  247. public class InorderSuccessor {
  248.    
  249.     public static void main(String[] args) throws Exception {
  250.         int i,j,k;
  251.        
  252.         BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
  253.        
  254.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  255.         int N = Integer.parseInt(br.readLine());
  256.        
  257.         for (i=0;i<N;i++) {
  258.             int num = Integer.parseInt(br.readLine());
  259.             tree.insert(new Integer(num));
  260.         }
  261.        
  262.         br.close();
  263.        
  264.         int prev = tree.findMin();
  265.         System.out.println(prev);
  266.  
  267.         for (i=1;i<N;i++) {
  268.             int tmp = tree.getSuccessor(prev);
  269.             System.out.println(tmp);
  270.             prev = tmp;
  271.         }
  272.        
  273.     }
  274.    
  275. }
  276.  
  277.  
  278.  
  279. Sample input
  280.  
  281. 10
  282. 8
  283. 2
  284. 11
  285. 6
  286. 0
  287. 9
  288. 19
  289. 3
  290. 14
  291. 16
  292.  
  293. Sample output
  294.  
  295. 0
  296. 2
  297. 3
  298. 6
  299. 8
  300. 9
  301. 11
  302. 14
  303. 16
  304. 19
  305.  
  306.  
RAW Paste Data