Advertisement
Guest User

Untitled

a guest
Feb 27th, 2012
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 7.36 KB | None | 0 0
  1. #include "bst.h"
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5.  
  6. /* structure from which binary search tree consists of */
  7.  
  8. /* Initializes binary search tree.
  9.  * Parameter root is pointer to pointer which points to the tree's root.
  10.  */
  11. void bst_init(bst_node_t **root){
  12.     bst_node_t *newNode = malloc(sizeof(bst_node_t));
  13.     newNode->value = NULL;
  14.     newNode->parent = NULL;
  15.     newNode->left = NULL;
  16.     newNode->right = NULL;
  17.     *root = newNode;
  18. }
  19.  
  20. /* Insert key to binary search tree.
  21.  * Parameter root is pointer to pointer which points to the tree's root.
  22.  * value is the string which is put to the tree (key), you're not supposed to
  23.  * make copy of the string.
  24.  * Returns 0 if succesful, -1 otherwise
  25.  */
  26. int bst_insert(bst_node_t **root, char *value){
  27.     bst_node_t *newNode = malloc(sizeof(bst_node_t));
  28.     newNode->left = NULL;
  29.     newNode->right = NULL;
  30.     newNode->value = value;
  31.     if((*root)->value == NULL){
  32.      //   printf("Empty tree, making new root\n");
  33.         newNode->parent = NULL;
  34.         *root = newNode;
  35.         return 0;
  36.     }
  37.  
  38.     bst_node_t *current = *root;
  39.  
  40.     while(1){
  41.         int comparison = strcmp((current->value),value);
  42.       //  printf("Comparing %s and %s\n", current->value, value);
  43.         if(comparison < 0){ //Current->value < value, mennaan oikealle
  44.             if(current->right == NULL){
  45.               //  printf("Inserted right\n");
  46.                 current->right = newNode;
  47.                 newNode->parent = current;
  48.                 return 0;
  49.             }
  50.             else {
  51.                 current = current->right;
  52.                 continue;
  53.             }
  54.         }
  55.         else if(comparison > 0){ //Current->value > value, mennaan vasemmalle
  56.             if(current->left == NULL){
  57.                 current->left = newNode;
  58.                 newNode->parent = current;
  59.              //   printf("Inserted left\n");
  60.                 return 0;
  61.             }
  62.             else {
  63.                 current = current->left;
  64.                 continue;
  65.             }
  66.         }
  67.         else{ // current->data == value, virhe
  68.           //  printf("Error\n");
  69.             return -1;
  70.         }
  71.     }
  72. }
  73.  
  74. void replaceNode(bst_node_t* node1, bst_node_t* node2){
  75.     if(node1->parent != NULL){
  76.         if(node1->parent->left == node1){
  77.             node1->parent->left = node2;
  78.         }
  79.         else{
  80.             node1->parent->right = node2;
  81.         }
  82.     }
  83.     else{
  84.         if(node2 != NULL) node2->parent = NULL;
  85.     }
  86.     if(node1->left != node2 && node2 != NULL){
  87.         node2->left = node1->left;
  88.         if(node1->left != NULL){
  89.             node1->left->parent = node2;
  90.         }
  91.     }
  92.     if(node1->right != node2 && node2 != NULL){
  93.         node2->right = node1->right;
  94.         if(node1->right != NULL){
  95.             node1->right->parent = node2;
  96.         }
  97.     }
  98. }
  99.  
  100. /* Delete key from binary search tree.
  101.  * Parameter root is pointer to pointer which points to the tree's root.
  102.  * Node is pointer to node which needs to be removed.
  103.  * Returns pointer to value of the removed node if succesful, null otherwise.
  104.  */
  105. char *bst_delete(bst_node_t **root, bst_node_t *node){
  106.  
  107.     char* value = node->value;
  108.     bst_node_t* newRoot = NULL;
  109.     int changingRoot = 0;
  110.     if(node == *root) changingRoot = 1;
  111.  
  112.     if(node->left == NULL && node->right == NULL){ //No children
  113.  
  114.         replaceNode(node,NULL);
  115.         if(changingRoot == 1){
  116.             (*root)->value = NULL;
  117.             return value;
  118.         }
  119.         free(node);
  120.     }
  121.     else if(!(node->left != NULL && node->right != NULL)){ // One child
  122.         if(node->left != NULL){
  123.             newRoot = node->left;
  124.             replaceNode(node,node->left);
  125.             free(node);
  126.         }
  127.         else{
  128.             newRoot = node->right;
  129.             replaceNode(node,node->right);
  130.             free(node);
  131.         }
  132.     }
  133.     else { //Two children
  134.         bst_node_t* successor = bst_next(node);
  135.         replaceNode(node,successor);
  136.         if(node->left != NULL){
  137.             newRoot = node->left;
  138.             replaceNode(node,node->left);
  139.             free(node);
  140.         }
  141.         else{
  142.             newRoot = node->right;
  143.             replaceNode(node,node->right);
  144.             free(node);
  145.         }
  146.     }
  147.  
  148.     if(changingRoot == 1){
  149.         *root = newRoot;
  150.     }
  151.  
  152.     return value;
  153. }
  154.  
  155. /* Find key from bst (binary search tree).
  156.  * Parameter root is pointer to the trees root.
  157.  * value is the key which we are searching
  158.  * Returns pointer to the node which has the same value when compared using
  159.  * strcmp.
  160.  */
  161. bst_node_t *bst_find(bst_node_t *root, char *value){
  162.     bst_node_t* current = root;
  163.     while(1){
  164.      //   printf("Comparing %s and %s\n", current->value, value);
  165.         int comparison = strcmp((current->value),value);
  166.         if(comparison < 0){ //Current->data < value, mennaan oikealle
  167.             if(current->right == NULL){ //Not found
  168.                 return NULL;
  169.             }
  170.             else {
  171.                 current = current->right;
  172.                 continue;
  173.             }
  174.         }
  175.         else if(comparison > 0){ //Current->data > value, mennaan vasemmalle
  176.             if(current->left == NULL){ //Not found
  177.                 return NULL;
  178.             }
  179.             else {
  180.                 current = current->left;
  181.                 continue;
  182.             }
  183.         }
  184.         else{ // current->data == value, loytyi
  185.             return current;
  186.         }
  187.     }
  188. }
  189.  
  190. /* Find next node from the node passed in parameter (meaning that the value
  191.  * of the node pointed by parameter node is smaller than the value of the
  192.  * successor but there are no nodes in bst that have value smaller than
  193.  * successor and greater than node pointed by parameter node)
  194.  * Parameter node gives pointer to node which successor we are finding of.
  195.  * Returns pointer to successor node.
  196.  */
  197. bst_node_t *bst_next(bst_node_t *node){
  198.     if(node->right == NULL){ //Mennaan ylos, kunnes siirrytaan oikealle
  199.         bst_node_t* current = node;
  200.         while(1){
  201.             bst_node_t* parentNode = current->parent;
  202.             if(parentNode == NULL){
  203.                 return NULL;
  204.             }
  205.             if(parentNode->left == current){
  206.                 return parentNode;
  207.             }
  208.             else{
  209.                 current = parentNode;
  210.             }
  211.         }
  212.     }
  213.  
  214.     else{ //Yksi oikealle, ja sitten vasemmalle niin pitkalle, kuin paasee
  215.         bst_node_t* current = node->right;
  216.         while(current->left != NULL){
  217.             current = current->left;
  218.         }
  219.         return current;
  220.     }
  221. }
  222.  
  223. /* Find node that has minimal value in bst.
  224.  * Parameter root gives pointer to the root of the tree.
  225.  * Returns pointer to node that has minimal value in bst.
  226.  */
  227. bst_node_t *bst_find_min(bst_node_t *root){
  228.     //Mennaan vasemmalle niin pitkalle kuin paasee
  229.     bst_node_t* current = root;
  230.     while(current->left != NULL){
  231.         current = current->left;
  232.     }
  233.     return current;
  234.  
  235. }
  236.  
  237. /* Find node that has maximal value in bst.
  238.  * Parameter root gives pointer to the root of the tree.
  239.  * Returns pointer to node that has maximal value in bst.
  240.  */
  241. bst_node_t *bst_find_max(bst_node_t *root){
  242.     //Mennaan oikealle niin pitkalle kuin paasee
  243.     bst_node_t* current = root;
  244.     while(current->right != NULL){
  245.         current = current->right;
  246.     }
  247.     return current;
  248. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement