#define NULL (void *) 0
 
struct tree_node {
	int value;
	struct tree_node *left;
	struct tree_node *right;
};
 
typedef struct {
	struct tree_node *root;
} tree;
 
int tree_insert(tree *my_tree, int value)
{
	//check argument
	if(!my_tree) return 0;
	
	//create new node to insert
	struct tree_node *insert_node = NULL;
	insert_node = (struct tree_node *)malloc(sizeof(struct tree_node));
	if(!insert_node) return 0;
 
	//init node value
	insert_node->value = value;
	insert_node->right = NULL;
	insert_node->left = NULL;
 
	//transversing tree for the right spot to insert new node
	if(!my_tree->root) {
		my_tree->root = insert_node;
	} else {
		struct tree_node *node = my_tree->root;
		while(node) {
			if(value < node->value) {
				if(node->left) {
					node = node->left;
				} else {
					node->left = insert_node;
					node = NULL;
				}
			} else if(value > node->value) {
				if(node->right) {
					node = node->right;
				} else {
					node->right = insert_node;
					node = NULL;
				}
			} else {
				return 0;
			}
		}
	}
 
	return 1;
}
 
void tr(struct tree_node *node, struct tree_node **result, int value)
{
	if(node) {
		if(value == node->value) {
			*result = node;
		} else if(value < node->value) {
			tr(node->left, result, value);
		} else if(value > node->value) {
			tr(node->right, result, value);
		}
	}
}
 
struct tree_node *tree_search(tree *my_tree, int value)
{
	if(my_tree->root) {
		struct tree_node *result;
		result = NULL;
		
		tr(my_tree->root, &result, value);
		
		return result;
	} else {
		return NULL;
	}
}
 
struct tree_node **dsr(struct tree_node **node, int value)
{
	while(1) {
		if(value == (*node)->value) {
			return node;
		} else if (value < (*node)->value) {
			if((*node)->left) {
				node = &((*node)->left);
			} else {
				return NULL;
			}
		} else if (value > (*node)->value) {
			if((*node)->right) {
				node = &((*node)->right);
			} else {
				return NULL;
			}
		} else {
			//harusnya ngak nyampe sini tapi buat jaga-jaga
			//biar ngak ngeloop selamanya
			return NULL;
		}
	}
}
 
void dr(struct tree_node **del_node)
{
	if((*del_node)->left) {
		//node yg hendak dihapus memiliki anak di kiri
		//cari node paling gede disebelah kiri
		struct tree_node **max_node;
		max_node = &((*del_node)->left);
		while((*max_node)->right) {
			max_node = &((*max_node)->right);
		}
 
		//tuker nilai node yg mo diapus ama
		//nilai yg paling gede tadi
		//n dihapus deh
		if((*max_node)->left) {
			(*del_node)->value = (*max_node)->value;
			dr(max_node);
		} else {
			(*del_node)->value = (*max_node)->value;
			free(*max_node);
			*max_node = NULL;
		}
	} else if((*del_node)->right) {
		//node yg hendak dihapus memiliki anak di kanan
		//cari node paling kecil disebelah kanan
		struct tree_node **min_node;
		min_node = &((*del_node)->right);
		while((*min_node)->left) {
			min_node = &((*min_node)->left);
		}
 
		//mirip-mirip dah cuma kebalikannya doank
		if((*min_node)->right) {
			(*del_node)->value = (*min_node)->value;
			dr(min_node);
		} else {
			(*del_node)->value = (*min_node)->value;
			free(*min_node);
			*min_node = NULL;
		}
	} else {
		//node yg hendak dihapus merupakan leaf
		//(tidak ada anaknya)
		//langsung aja dihapus
		free(*del_node);
		*del_node = NULL;
	}
}
 
int tree_delete(tree *my_tree, int value)
{
	if(my_tree->root) {
		//search node to be deleted
		struct tree_node **del_node;
		del_node = dsr(&(my_tree->root), value);
		if(!del_node) {
			//ngak ketemu
			return 0;
		}
 
		//proses penghapusan
		dr(del_node);
	}
}
 
void pr(struct tree_node *node)
{
	//contoh penggunaan rekursif
	if(node) {
		pr(node->left);
		printf("%d ", node->value);
		pr(node->right);
	}
}
 
void tree_print(tree *my_tree)
{
	pr(my_tree->root);
	printf("\n");
}
 
void cr(struct tree_node *node)
{
	if(node) {
		cr(node->left);
		cr(node->right);
		free(node);
	}
}
 
void tree_clear(tree *my_tree)
{
	if(my_tree->root) {
		cr(my_tree->root);
	}
}
 
int main(void)
{
	int a[5];
	a[0] = 5;
	a[1] = 3;
	a[2] = 7;
	a[3] = 4;
	a[4] = 6;
 
	tree pohon;
	pohon.root = NULL;
 
	int i;
	for(i = 0; i < 5; i++) {
		if(!tree_insert(&pohon, a[i])) {
			printf("eerr %d\n", i);
		}
	}
 
	tree_print(&pohon);
 
	struct tree_node *r;
	r = tree_search(&pohon, 100);
	if(r) {
		printf("ketemu %d %d\n", 4, r->value);
	} else {
		printf("tidak ketemu\n");
	}
 
	tree_delete(&pohon, 6);
	tree_print(&pohon);
 
	tree_clear(&pohon);
}
 

Referensi gue: Wikipedia: Binary search tree]]> Programming http://rahmanpujianto.org/index.php?itemid=5 Thu, 11 Jan 2007 21:13:38 +0700 http://rahmanpujianto.org/index.php?itemid=3