SHARE
TWEET

Untitled

a guest May 20th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.      * CTM = CTP = theta(n) serve visitare l'intero albero
  3.      * CSM = theta(log(n)) albero bilanciato
  4.      * CSP = theta(n) albero degenere
  5.      */
  6.     public static int countSubtrees(AlberoBin<Integer> a){
  7.         int[] cont = new int[1];
  8.         countSubtrees(a, cont);
  9.         return cont[0];
  10.     }
  11.    
  12.    
  13.     // The function returns the value of the root node if all nodes in subtree
  14.     // rooted at root have same values, else it returns infinity
  15.     // Here count stores the result and it is passed by reference
  16.     private static int countSubtrees(AlberoBin<Integer> a, int[] cont) {
  17.         // base case: empty tree
  18.         if (a == null)
  19.             return Integer.MAX_VALUE;
  20.         // if root is a leaf node, increase the count and return root node data
  21.         if (a.sin() == null && a.des() == null) {
  22.             cont[0]++;
  23.             return a.val();
  24.         }
  25.         // recurse for left subtree and right subtree
  26.         int sin = countSubtrees(a.sin(), cont);
  27.         int des = countSubtrees(a.des(), cont);
  28.  
  29.         // 1. left subtree is empty & right subtree data matches with root
  30.         // 2. right subtree is empty & left subtree data matches with root
  31.         // 3. both left & right subtree are non-empty & their data matches with
  32.         // root
  33.         if ((sin == Integer.MAX_VALUE && des == a.val()) || (des == Integer.MAX_VALUE && sin == a.val())
  34.                 || (sin == a.val() && des == a.val())) {
  35.             cont[0]++;
  36.             return a.val();
  37.         }
  38.         // return infinity if root's data doesn't match with left or right
  39.         // subtree
  40.         return Integer.MAX_VALUE;
  41.  
  42.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top