lib_vbtree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "lib_vbtree.h"
   6
   7 /*
   8 TreeNode *buildTree(FILE *in)
   9 {
  10         TreeNode *p = (TreeNode *)malloc(sizeof(TreeNode));
  11         char str[MAX_WORD_SIZE+1];
  12
  13         fscanf(in, "%s", str);
  14         if(strcmp(str, "@")==0) return NULL;
  15         strcpy(p->data.word, str);
  16         p->left = buildTree(in);
  17         p->right = buildTree(in);
  18         return p;
  19 }
  20 */
  21
  22 void vbtree_pre_order(TreeNode *node)
  23 {
  24         if(node != NULL)
  25         {
  26                 vbtree_pre_order(node->left);
  27                 vbtree_pre_order(node->right);
  28         }
  29 }
  30
  31 void vbtree_in_order(TreeNode *node)
  32 {
  33         if(node != NULL)
  34         {
  35                 vbtree_in_order(node->left);
  36                 vbtree_in_order(node->right);
  37         }
  38 }
  39
  40 void vbtree_post_order(TreeNode *node)
  41 {
  42         if(node != NULL) {
  43                 vbtree_post_order(node->left);
  44                 vbtree_post_order(node->right);
  45         }
  46 }
  47
  48 TreeNode *newTreeNode(void *d)
  49 {
  50         TreeNode *p = (TreeNode *)malloc(sizeof(TreeNode));
  51         p->pData = d;
  52         p->left = p->right = NULL;
  53         return p;
  54 }
  55
  56 /*
  57 TreeNode *vbtree_find_insert(BinaryTree bt, TreeNode d)
  58 {
  59         int cmp;
  60         TreeNode *curr = bt.root;
  61
  62         if(bt.root == NULL) return newTreeNode(NULL);
  63         while((cmp = strcmp(d.word, curr->pData.word))!= 0)
  64         {
  65                 if(cmp < 0)
  66                 {
  67                         if(curr->left == NULL) return curr->left = newTreeNode(d);
  68                         curr = curr->left;
  69                 } else {
  70                         if(curr->right == NULL) return curr->right = newTreeNode(d);
  71                         curr = curr->right;
  72                 }
  73         }
  74         return curr;
  75 }
  76 */
  77 int vbtree_node_count(TreeNode *root)
  78 {
  79         if(root == NULL) return 0;
  80         return 1 + vbtree_node_count(root->left) + vbtree_node_count(root->right);
  81 }
  82
  83 int vbtree_leave_count(TreeNode *root)
  84 {
  85         if(root == NULL) return 0;
  86         if(root->left == NULL && root->right == NULL) return 1;
  87         return vbtree_leave_count(root->left) + vbtree_leave_count(root->right);
  88 }
  89
  90 int vbtree_height(TreeNode *root)
  91 {
  92         int left = 0, right = 0;
  93         if(root == NULL) return 0;
  94         left = vbtree_height(root->left);
  95         right = vbtree_height(root->right);
  96
  97         if(left > right) return 1 + left;
  98         else return 1 + right;
  99 }
 100
 101 /*
 102  * FUNCTION NOT COMPLETED
 103 void deleteNode(TreeNode T)
 104 {
 105         if(T == NULL) return NULL;
 106         if(right(T) ++ NULL) return left(T)
 107 */
 108
 109 int vbtree_node_level(int n)
 110 {
 111         int level = 0;
 112         while(n % 2 == 0)
 113         {
 114                 level++;
 115                 n /= 2;
 116         }
 117         return level;
 118 }
 119
 120 void vbtree_insert_best(TreeNode *lastNode[])
 121 {
 122         static int numNodes = 0;
 123         int level = vbtree_node_level(numNodes);
 124         TreeNode *p = newTreeNode(NULL);
 125
 126         numNodes++;
 127         if(level > 0) p->left = lastNode[level-1];
 128         if(lastNode[level+1] != NULL)
 129                 if(lastNode[level+1]->right == NULL)
 130                         lastNode[level+1]->right = p;
 131         lastNode[level] = p;
 132 }
 133
 134 TreeNode *vbtree_finalize_best(TreeNode *lastNode[])
 135 {
 136         int m, n = MAX_HEIGHT - 1;
 137         TreeNode *root = lastNode[n];
 138         while(n > 0 && lastNode[n] == NULL) n--;
 139         while(n > 0)
 140         {
 141                 if(lastNode[n]->right != NULL) n--;
 142                 else {
 143                         TreeNode *tn = lastNode[n]->left;
 144                         m = n - 1;
 145                         while(m >= 0 && tn == lastNode[m])
 146                         {
 147                                 tn = tn->right;
 148                                 m--;
 149                         }
 150                         if(m >= 0) lastNode[n]->right = lastNode[m];
 151                         n = m;
 152                 }
 153         }
 154         return root;
 155 }