codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <string.h> #include <stdlib.h> static struct tsnode* BinarySearchTreeString_addtreeImp(struct tsnode *p, const char *w) { if(p == NULL) { struct tsnode *newNode; if((newNode = (struct tsnode*)malloc(sizeof(struct tsnode))) == NULL) return NULL; newNode->word = strdup(w); newNode->left = NULL; newNode->right = NULL; return newNode; } else if(strcmp(w, p->word) < 0) p->left = BinarySearchTreeString_addtree(p->left, w); else p->right = BinarySearchTreeString_addtree(p->right, w); return p; } struct tsnode* BinarySearchTreeString_addtree(struct tsnode *p, const char *w) { struct tsnode *ptr; if((ptr = BinarySearchTreeString_lookup(p, w)) == NULL) return BinarySearchTreeString_addtreeImp(p, w); return ptr; } struct tsnode* BinarySearchTreeString_deletetree(struct tsnode *p, const char *w) { int cond; struct tsnode *currentp, *prevp; currentp = prevp = p; /* find the node to be deleted. prevp points to the parent of the node to be deleted and currentp points to the node to be deleted */ while(1) { if(currentp == NULL) /* cannot find the node to be deleted */ return p; if((cond = strcmp(w, currentp->word)) == 0) /* node found, break out of the loop */ { break; } else if(cond < 0) { prevp = currentp; currentp = currentp->left; } else { prevp = currentp; currentp = currentp->right; } } /* the right node is NULL */ if(currentp->right == NULL) { /* root node */ if(currentp == p) { p = currentp->left; } else if(prevp->right == currentp) { prevp->right = currentp->left; } else { prevp->left = currentp->left; } } else if(currentp->left == NULL) { /* root node */ if(currentp == p) { p = currentp->right; } else if(prevp->right == currentp) { prevp->right = currentp->right; } else { prevp->left = currentp->right; } } else { struct tsnode *ptr; ptr = currentp->right; if(ptr->left == NULL) { ptr->left = currentp->left; /* root node */ if(currentp == p) { p = ptr; } else if(prevp->right == currentp) { prevp->right = ptr; } else { prevp->left = ptr; } } else { struct tsnode *prevptr; for(prevptr = ptr; ptr->left; prevptr = ptr, ptr = ptr->left); prevptr->left = ptr->right; ptr->right = currentp->right; ptr->left = currentp->left; /* root node */ if(currentp == p) { p = ptr; } else if(prevp->right == currentp) { prevp->right = ptr; } else { prevp->left = ptr; } } } free(currentp->word); free(currentp); return p; } struct tsnode* BinarySearchTreeString_lookup(struct tsnode *p, const char *w) { int cond; LOOP: if(p == NULL) return NULL; if((cond = strcmp(w, p->word)) == 0) return p; else if(cond < 0) p = p->left; else p = p->right; goto LOOP; } void BinarySearchTreeString_free(struct tsnode *p) { if(p == NULL) return; BinarySearchTreeString_free(p->left); BinarySearchTreeString_free(p->right); free(p->word); free(p); }
Private
[
?
]
Run code
Submit