Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bst.h"
- #include <string.h>
- #include <stdlib.h>
- #include <stdio.h>
- /* structure from which binary search tree consists of */
- /* Initializes binary search tree.
- * Parameter root is pointer to pointer which points to the tree's root.
- */
- void bst_init(bst_node_t **root){
- bst_node_t *newNode = malloc(sizeof(bst_node_t));
- newNode->value = NULL;
- newNode->parent = NULL;
- newNode->left = NULL;
- newNode->right = NULL;
- *root = newNode;
- }
- /* Insert key to binary search tree.
- * Parameter root is pointer to pointer which points to the tree's root.
- * value is the string which is put to the tree (key), you're not supposed to
- * make copy of the string.
- * Returns 0 if succesful, -1 otherwise
- */
- int bst_insert(bst_node_t **root, char *value){
- bst_node_t *newNode = malloc(sizeof(bst_node_t));
- newNode->left = NULL;
- newNode->right = NULL;
- newNode->value = value;
- if((*root)->value == NULL){
- // printf("Empty tree, making new root\n");
- newNode->parent = NULL;
- *root = newNode;
- return 0;
- }
- bst_node_t *current = *root;
- while(1){
- int comparison = strcmp((current->value),value);
- // printf("Comparing %s and %s\n", current->value, value);
- if(comparison < 0){ //Current->value < value, mennaan oikealle
- if(current->right == NULL){
- // printf("Inserted right\n");
- current->right = newNode;
- newNode->parent = current;
- return 0;
- }
- else {
- current = current->right;
- continue;
- }
- }
- else if(comparison > 0){ //Current->value > value, mennaan vasemmalle
- if(current->left == NULL){
- current->left = newNode;
- newNode->parent = current;
- // printf("Inserted left\n");
- return 0;
- }
- else {
- current = current->left;
- continue;
- }
- }
- else{ // current->data == value, virhe
- // printf("Error\n");
- return -1;
- }
- }
- }
- void replaceNode(bst_node_t* node1, bst_node_t* node2){
- if(node1->parent != NULL){
- if(node1->parent->left == node1){
- node1->parent->left = node2;
- }
- else{
- node1->parent->right = node2;
- }
- }
- else{
- if(node2 != NULL) node2->parent = NULL;
- }
- if(node1->left != node2 && node2 != NULL){
- node2->left = node1->left;
- if(node1->left != NULL){
- node1->left->parent = node2;
- }
- }
- if(node1->right != node2 && node2 != NULL){
- node2->right = node1->right;
- if(node1->right != NULL){
- node1->right->parent = node2;
- }
- }
- }
- /* Delete key from binary search tree.
- * Parameter root is pointer to pointer which points to the tree's root.
- * Node is pointer to node which needs to be removed.
- * Returns pointer to value of the removed node if succesful, null otherwise.
- */
- char *bst_delete(bst_node_t **root, bst_node_t *node){
- char* value = node->value;
- bst_node_t* newRoot = NULL;
- int changingRoot = 0;
- if(node == *root) changingRoot = 1;
- if(node->left == NULL && node->right == NULL){ //No children
- replaceNode(node,NULL);
- if(changingRoot == 1){
- (*root)->value = NULL;
- return value;
- }
- free(node);
- }
- else if(!(node->left != NULL && node->right != NULL)){ // One child
- if(node->left != NULL){
- newRoot = node->left;
- replaceNode(node,node->left);
- free(node);
- }
- else{
- newRoot = node->right;
- replaceNode(node,node->right);
- free(node);
- }
- }
- else { //Two children
- bst_node_t* successor = bst_next(node);
- replaceNode(node,successor);
- if(node->left != NULL){
- newRoot = node->left;
- replaceNode(node,node->left);
- free(node);
- }
- else{
- newRoot = node->right;
- replaceNode(node,node->right);
- free(node);
- }
- }
- if(changingRoot == 1){
- *root = newRoot;
- }
- return value;
- }
- /* Find key from bst (binary search tree).
- * Parameter root is pointer to the trees root.
- * value is the key which we are searching
- * Returns pointer to the node which has the same value when compared using
- * strcmp.
- */
- bst_node_t *bst_find(bst_node_t *root, char *value){
- bst_node_t* current = root;
- while(1){
- // printf("Comparing %s and %s\n", current->value, value);
- int comparison = strcmp((current->value),value);
- if(comparison < 0){ //Current->data < value, mennaan oikealle
- if(current->right == NULL){ //Not found
- return NULL;
- }
- else {
- current = current->right;
- continue;
- }
- }
- else if(comparison > 0){ //Current->data > value, mennaan vasemmalle
- if(current->left == NULL){ //Not found
- return NULL;
- }
- else {
- current = current->left;
- continue;
- }
- }
- else{ // current->data == value, loytyi
- return current;
- }
- }
- }
- /* Find next node from the node passed in parameter (meaning that the value
- * of the node pointed by parameter node is smaller than the value of the
- * successor but there are no nodes in bst that have value smaller than
- * successor and greater than node pointed by parameter node)
- * Parameter node gives pointer to node which successor we are finding of.
- * Returns pointer to successor node.
- */
- bst_node_t *bst_next(bst_node_t *node){
- if(node->right == NULL){ //Mennaan ylos, kunnes siirrytaan oikealle
- bst_node_t* current = node;
- while(1){
- bst_node_t* parentNode = current->parent;
- if(parentNode == NULL){
- return NULL;
- }
- if(parentNode->left == current){
- return parentNode;
- }
- else{
- current = parentNode;
- }
- }
- }
- else{ //Yksi oikealle, ja sitten vasemmalle niin pitkalle, kuin paasee
- bst_node_t* current = node->right;
- while(current->left != NULL){
- current = current->left;
- }
- return current;
- }
- }
- /* Find node that has minimal value in bst.
- * Parameter root gives pointer to the root of the tree.
- * Returns pointer to node that has minimal value in bst.
- */
- bst_node_t *bst_find_min(bst_node_t *root){
- //Mennaan vasemmalle niin pitkalle kuin paasee
- bst_node_t* current = root;
- while(current->left != NULL){
- current = current->left;
- }
- return current;
- }
- /* Find node that has maximal value in bst.
- * Parameter root gives pointer to the root of the tree.
- * Returns pointer to node that has maximal value in bst.
- */
- bst_node_t *bst_find_max(bst_node_t *root){
- //Mennaan oikealle niin pitkalle kuin paasee
- bst_node_t* current = root;
- while(current->right != NULL){
- current = current->right;
- }
- return current;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement