API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
223
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 16.30 KB | None | 0 0
raw download clone embed print report
  1. /****************************************************************************/
  2. /* DSA tree program example   D.F. ROSS        AVL - TREE                   */
  3. /****************************************************************************/
  4.  
  5. /****************************************************************************/
  6. /* include files and  global data objects                                   */
  7. /****************************************************************************/
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <math.h>
  12.  
  13. /****************************************************************************/
  14. /* define constants & types                                                 */
  15. /****************************************************************************/
  16.  
  17. #define ARRLEN    100
  18. #define NULLREF   NULL
  19.  
  20. /****************************************************************************/
  21. /* tree element definition (this is hidden!)                                */
  22. /****************************************************************************/
  23.  
  24. typedef struct treenode * treeref;
  25. typedef struct treenode
  26. {
  27.     int value;
  28.     int height;
  29.     treeref LC;
  30.     treeref RC;
  31. } treenode;
  32.  
  33. /****************************************************************************/
  34. /* define tree instance                                                     */
  35. /****************************************************************************/
  36.  
  37. static treeref T     = (treeref) NULL;
  38.  
  39. /****************************************************************************/
  40. /* define tree array                                                        */
  41. /****************************************************************************/
  42.  
  43. static treeref treearray[ARRLEN];
  44.  
  45. /****************************************************************************/
  46. /*  basic operations on the tree                                            */
  47. /****************************************************************************/
  48.  
  49. static int      is_empty(treeref T)             { return T == NULLREF; }
  50.  
  51. static int      get_value(treeref T)            { return T->value; }
  52. static int      get_height(treeref T)           { return T->height; }
  53. static treeref  get_LC(treeref T)               { return T->LC; }
  54. static treeref  get_RC(treeref T)               { return T->RC; }
  55.  
  56. static treeref  set_value(treeref T,  int v)    { T->value  = v; return T; }
  57. static treeref  set_height(treeref T, int h)    { T->height = h; return T; }
  58. static treeref  set_LC(treeref T, treeref L)    { T->LC     = L; return T; }
  59. static treeref  set_RC(treeref T, treeref R)    { T->RC     = R; return T; }
  60.  
  61.  
  62.  
  63. /****************************************************************************/
  64. /* create and initialise an element in the tree                             */
  65. /****************************************************************************/
  66.  
  67. static treeref create_node(int v)
  68. {
  69.   return set_RC(
  70.              set_LC(
  71.                 set_height(
  72.                    set_value(malloc(sizeof(treenode)), v),
  73.                 0),
  74.              NULLREF),
  75.           NULLREF);
  76. }
  77.  
  78. /****************************************************************************/
  79. /* basic operations on the tree                                             */
  80. /* LC, Node, RC - a RECURSIVE view of the tree                              */
  81. /****************************************************************************/
  82.  
  83. static treeref node(treeref T)             { return T; }
  84. static treeref LC(treeref T)               { return get_LC(T); }
  85. static treeref RC(treeref T)               { return get_RC(T); }
  86.  
  87. /****************************************************************************/
  88. /* CONStruct a new tree from a LC, Node and RC                              */
  89. /****************************************************************************/
  90.  
  91. static treeref cons(treeref LC, treeref N, treeref RC) {
  92.    set_LC(N, LC); set_RC(N, RC); return N;
  93.    }
  94.  
  95. /****************************************************************************/
  96. /* FIND the height of the tree                                              */
  97. /****************************************************************************/
  98.  
  99. static int max(int a, int b) { return a>b ? a : b; }
  100.  
  101.  
  102.  
  103. static int b_height(treeref T)
  104. {
  105.     if(T == NULL)
  106.         return 0;
  107.     else{
  108.         T->height = 1 + max(b_height(T->LC), b_height(T->RC));
  109.         return T->height;
  110.     }
  111. }
  112.  
  113. /****************************************************************************/
  114. /* FIND the minimum value node                          */
  115. /****************************************************************************/
  116.  
  117. int min(treeref T)
  118. {
  119.     if (LC(T) == NULL) return get_value(T);
  120.     else return min(LC(T));
  121. }
  122.  
  123. /****************************************************************************/
  124. /* ADD to the tree in BST order                                             */
  125. /****************************************************************************/
  126.  
  127. static treeref b_add(treeref T, treeref N)
  128. {
  129.   return   is_empty(T) ? N
  130.          : is_empty(N) ? T
  131.          : get_value(node(N)) < get_value(node(T)) ?
  132.              cons(b_add(LC(T), N), node(T), RC(T))
  133.          : get_value(node(N)) > get_value(node(T)) ?
  134.              cons(LC(T), node(T), b_add(RC(T), N))
  135.          : T;
  136. }
  137.  
  138. /****************************************************************************/
  139. /* REMove an element from the tree / BST order                              */
  140. /****************************************************************************/
  141.  
  142. static treeref b_rem(treeref T, int v)  //Remove given element from tree and return reordered tree
  143.  
  144. {
  145.     if (T == NULL){
  146.         printf("\n Value [%d] could NOT be removed! (not found...) ");     
  147.         return NULL;
  148.     }
  149.  
  150.     if (v == get_value(T)) {
  151.         // Remove node T
  152.         printf("\n Value [%d] removed! ", v);  
  153.         if (LC(T) == NULL && RC(T) == NULL) return NULL;
  154.         if (LC(T) == NULL) return RC(T);
  155.         if (RC(T) == NULL) return LC(T);
  156.         // If there is 2 children
  157.         int tmp = min(RC(T));
  158.         // Copy tmp to T
  159.         set_value(T, tmp);
  160.         // Delete tmp from T right
  161.         set_RC(T, (b_rem(RC(T), tmp)));
  162.         return T;
  163.     }
  164.     else if (v < get_value(T)) return set_LC(T, (b_rem(LC(T), v)));
  165.     else return set_RC(T, (b_rem(RC(T), v)));
  166.  
  167. }
  168.  
  169.     /* Simple method, gets unbalanced easy
  170.     if(is_empty(T)){
  171.         printf("\n Tree empty.. ");
  172.         return T;
  173.     }
  174.     if(v < get_value(T)){ // Check left child
  175.         printf("\n Checking left child: %d < %d ", v, get_value(T));
  176.         return cons(b_rem(LC(T), v), T, RC(T));
  177.     }
  178.     if(v > get_value(T)){ // Check right child
  179.         printf("\n Checking right child: %d > %d ", v, get_value(T));
  180.         return cons(LC(T), T, b_rem(RC(T), v));
  181.  
  182.     }
  183.     return b_add(LC(T), RC(T));
  184.     */
  185.  
  186. /****************************************************************************/
  187. /* FIND an element in the BST (Binary Search Tree)                          */
  188. /****************************************************************************/
  189.  
  190. static int b_findb(treeref T, int v)
  191. {
  192.     if (T == NULL){
  193.         printf("\n Value NOT found! ");
  194.         return -1;
  195.     }
  196.     if (v == get_value(T)) {
  197.         printf("\n Value found! ");
  198.         return 1;
  199.     }
  200.     else if (v < get_value(T)) return b_findb(get_LC(T),v);
  201.     else return b_findb(get_RC(T),v);
  202. }
  203.  
  204.  
  205.  
  206. /****************************************************************************/
  207. /* FIND the number of elements in the tree (cardinality)                    */
  208. /****************************************************************************/
  209.  
  210. static int b_size(treeref T)
  211. {
  212.     int elements = 1;
  213.     if(T == NULL)
  214.         return 0;
  215.     elements+=b_size(T->LC);
  216.     elements+=b_size(T->RC);
  217.     return elements;
  218. }
  219.  
  220. /****************************************************************************/
  221. /* display the tree ELEMENT                                                 */
  222. /****************************************************************************/
  223.  
  224. static void b_disp_el(treeref T)
  225. {
  226.    // if (!is_empty(T)) printf(" %2d[%d]  ", get_value(node(T)), b_height(T));
  227.    if (!is_empty(T)) printf(" %2d ", get_value(node(T)));
  228.    else printf("  * ");
  229. }
  230.  
  231. /****************************************************************************/
  232. /* display the tree (pre-order)                                             */
  233. /****************************************************************************/
  234.  
  235. static void b_disp_pre(treeref T) {
  236.     if (!is_empty(T)){
  237.         b_disp_el(node(T));
  238.         b_disp_pre(LC(T));
  239.         b_disp_pre(RC(T));
  240.     }  
  241. }
  242.  
  243. /****************************************************************************/
  244. /* display the tree (in-order)                                              */
  245. /****************************************************************************/
  246.  
  247. static void b_disp_in(treeref T) {
  248.   if (!is_empty(T)) {
  249.      b_disp_in(LC(T));
  250.      b_disp_el(node(T));
  251.      b_disp_in(RC(T));
  252.      }
  253. }
  254.  
  255. /****************************************************************************/
  256. /* display the tree (post-order)                                            */
  257. /****************************************************************************/
  258. static void b_disp_post(treeref T) {
  259.    //printf("\n TO BE DONE b_disp_post");
  260.     if (!is_empty(T)){
  261.         b_disp_post(LC(T));
  262.         b_disp_post(RC(T));
  263.         b_disp_el(T);
  264.     }
  265. }
  266.  
  267. /****************************************************************************/
  268. /* display the treearray array                                              */
  269. /****************************************************************************/
  270.  
  271. static void b_disp_array()
  272. {
  273.     int k, count = 0;
  274.     printf(" Treearray is:                           ");
  275.     for(k = 0; k < ARRLEN-1; k++){
  276.         if(treearray[k] == NULL)
  277.             printf(" *  ");
  278.         else{
  279.             printf(" %d  ", treearray[k]);
  280.             count++;
  281.         }
  282.         if(count == be_size())
  283.             break;
  284.     }
  285.     printf("\n");
  286.    }
  287.  
  288. /****************************************************************************/
  289. /* Tree to array via a treearray (breadth-first search)                     */
  290. /****************************************************************************/
  291. /* Transforms a binary tree to a sequence (including NULL (*) references)   */
  292. /* e.g.  the following tree:                    5                           */
  293. /*                                      2              7                    */
  294. /*                                  *       3      6        *               */
  295. /*                                                                          */
  296. /* becomes: [5] [2] [7] [*] [3] [6] [*]                                     */
  297. /****************************************************************************/
  298.  
  299. static void T2Q(treeref T, int qpos) {
  300.     if(T != NULL){ 
  301.         if(qpos < ARRLEN-1) {
  302.             treearray[qpos-1] = get_value(T);
  303.             //printf("\n Arr[%d] = [%d]", qpos-1, get_value(T));
  304.             T2Q(LC(T), qpos*2);
  305.             T2Q(RC(T), qpos*2+1);
  306.         }
  307.     }  
  308. }
  309.  
  310. /****************************************************************************/
  311. /* display the tree in 2D                                                   */
  312. /****************************************************************************/
  313. /* step 1: transform the tree to an array (Q) using T2Q() above             */
  314. /* e.g. array [5] | [2] [7] | [*] [3] [6] [*]   | etc.                      */
  315. /*      index (1) | (2) (3) | (4) (5) (6) (7)   | (8) ...                   */
  316. /*      level (1) | (2) (2) | (3) (3) (3) (3)   | (4) ...                   */
  317. /* step 2: then print the nodes at each level of the tree to give           */
  318. /*                             5                                            */
  319. /*                     2              7                                     */
  320. /*                *        3      6        *                                */
  321. /****************************************************************************/
  322.  
  323. treeref left_rotation(treeref T)
  324. {
  325.     printf("\nRotating left...\n");
  326.     treeref temp = get_RC(T);   // Temporärt träd höger nod som root
  327.     set_RC(T,get_LC(temp));     // Sätt höger nod
  328.     set_LC(temp,T);         // Sätt vänster nod
  329.     return temp;
  330. }
  331. treeref right_rotation(treeref T)
  332. {
  333.     printf("\nRotating right...\n");
  334.     treeref temp = get_LC(T);   // Temporärt träd vänster nod som root
  335.     set_LC(T,get_RC(temp));     // Sätt vänster nod
  336.     set_RC(temp,T);         // Sätt höger nod
  337.     return temp;
  338. }
  339. /*
  340. static int      is_empty(treeref T)             { return T == NULLREF; }
  341.  
  342. static int      get_value(treeref T)            { return T->value; }
  343. static int      get_height(treeref T)           { return T->height; }
  344. static treeref  get_LC(treeref T)               { return T->LC; }
  345. static treeref  get_RC(treeref T)               { return T->RC; }
  346.  
  347. static treeref  set_value(treeref T,  int v)    { T->value  = v; return T; }
  348. static treeref  set_height(treeref T, int h)    { T->height = h; return T; }
  349. static treeref  set_LC(treeref T, treeref L)    { T->LC     = L; return T; }
  350. static treeref  set_RC(treeref T, treeref R)    { T->RC     = R; return T; }
  351. */
  352. void empty_array()
  353. {
  354.     int i;
  355.     for(i = 0; i < ARRLEN; i++){
  356.         treearray[i] = NULL;
  357.     }
  358. }
  359.  
  360. static void b_disp_2D()
  361. {
  362.    
  363.     int kuk = isBalanced(T);
  364.  
  365.     empty_array();
  366.     T2Q(T, 1);
  367.     printf("\n TREE (%d nodes, height %d) is inorder:   ", be_size(), be_height());
  368.         be_disp_in();
  369.     printf("\n");
  370.     be_disp_array();
  371.  
  372.     // Pretty print the tree
  373.     int i = 0, j = 1;
  374.     for(i; i < ARRLEN-1; i++){
  375.         if(i == (myPow(2, j)-2)/2){ // Indent
  376.             indent(j);     
  377.         }
  378.         if(treearray[i] == NULL)
  379.             printf("*");
  380.         else
  381.             printf("%d", treearray[i]);
  382.         spacing(j);         // Spacing on same line
  383.         if(i == myPow(2, j)-2){     // New line for childs
  384.             if(j < be_height()){
  385.                 printf("\n");
  386.                 j++;
  387.             }
  388.             else
  389.                 break;         
  390.         }
  391.     }
  392.  
  393.     if(kuk == 2)
  394.     {
  395.                 printf("\nTree left heavy!");  
  396.         T = right_rotation(T);
  397.         b_disp_2D();
  398.     }
  399.  
  400.     if(kuk == 3)
  401.     {
  402.                 printf("\nTree right heavy!");  
  403.         T = left_rotation(T);
  404.         b_disp_2D();
  405.     }
  406. }
  407.  
  408.  
  409.  
  410. /****************************************************************************/
  411. /* Custom functions added by students.                                      */
  412. /****************************************************************************/
  413.  
  414. void indent(int level){             // Indent calculated 2 ^ (max level - level) - 1
  415.     int i, n = myPow(2, be_height()-level);
  416.     for(i=0; i<n-1; i++)
  417.         printf(" ");
  418. }
  419.  
  420. void spacing(int level){            // Spacing calculated 2 ^ (max level - level + 1) - 1
  421.     int i, n = myPow(2, be_height()-level+1);
  422.     for(i=0; i<n-1; i++)
  423.         printf(" ");
  424. }
  425.  
  426. int myPow(int base, int exponent) {     // myPow calculates powerd by ( base^exponent )
  427.     int i, n = 1;
  428.     for (i = 0; i < exponent; i++) {
  429.         n *= base;
  430.     }
  431.     return n;
  432. }
  433.  
  434. int isBalanced(treeref T)           // Madda fakking AVL träääääd
  435. {
  436.         int lh;     // height left subtree
  437.         int rh;         // height right subtree
  438.  
  439.         // tree empty, return true
  440.         if(T == NULL){
  441.                 return 1;
  442.         }
  443.  
  444.         // Get height of sub trees
  445.         lh = b_height(T->LC);
  446.         rh = b_height(T->RC);
  447.  
  448.         // Tree balanced?  
  449.         if( abs(lh-rh) <= 1 && isBalanced(T->LC) && isBalanced(T->RC)){        
  450.                 return 1;
  451.         }
  452.  
  453.         // Tree not balanced, left or right heavy?
  454.         if( lh-rh == 2){  
  455.                 //printf("\nTree left heavy!");          
  456.                 return 2;
  457.         }else{
  458.                 //printf("\nTree right heavy!");  
  459.                 return 3;
  460.         }
  461. }
  462.  
  463. /****************************************************************************/
  464. /* public operations on the tree                                            */
  465. /****************************************************************************/
  466. void be_disp_2D()                { b_disp_2D();   }
  467. void be_disp_array()             { b_disp_array();  }
  468.  
  469. void be_disp_pre()               { b_disp_pre(T);  }
  470. void be_disp_in()                { b_disp_in(T);   }
  471. void be_disp_post()              { b_disp_post(T); }
  472.  
  473. void be_add(int v)               { T = b_add(T, create_node(v)); }
  474. void be_rem(int v)               { T = b_rem(T, v); }
  475.  
  476. int  be_is_memberb(int v)        { return b_findb(T, v); }
  477. int  be_size()                   { return b_size(T); }
  478. int  be_height()                 { return b_height(T); }
  479. /****************************************************************************/
  480. /* end of basic functions                                                   */
  481. /****************************************************************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!