• API
• FAQ
• Tools
• Archive
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;
8.         countSubtrees(a, cont);
9.         return cont;
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++;
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++;
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.

Top