本文共 2273 字，大约阅读时间需要 7 分钟。

一，性质

（1）二分搜索树是一颗二叉树（但不一定是完全二叉树），满足二叉树的所有定义；

（2）二分搜索树每个节点的左子树的值都小于该节点的值，每个节点右子树的值都大于该节点的值。 (3）以左右孩子为根的子树仍为二分搜索树

二，意义

（1）在查找元素时，我们于根节点进行对比后，就能每次近乎一半的去除掉查找范围，这就大大的加快了我们的查询速度，插入元素时也是一样。

（2）用来实现字典数据结构（查找表） （3）高效，动态地维护数据 （4）min，max，floor，ceil，rank，select

三，基本操作

#include
   
    #include
    
     #include 
     
      #define maxsize 100struct node{	int key;	char value;};typedef struct BST{	struct node data;	struct BST *left;	struct BST *right;}bs,*bst;bst find(int key,bst T){	if(T==NULL) return NULL;	if(key
      
       data.key) return find(key,T->left);	else if(key>T->data.key) return find(key,T->right);	else return T;}bst findMin(bst T){	if(T==NULL) return NULL;	else if(T->left==NULL) return T;	else  return findMin(T->left);}bst findMax(bst T){	if(T!=NULL){		while(T->right!=NULL){			T=T->right;		}	}	return T;}void visit(bst T){	if(T!=NULL){	 	printf("%c ",T->data.value);		visit(T->left);		visit(T->right);	}}bst createTree(bst newtree,struct node a){//即insert 		if(newtree==NULL) {			newtree=(struct BST *)malloc(sizeof(bs));			newtree->data.key = a.key;			newtree->data.value = a.value;			newtree->left=newtree->right=NULL;   		}	    else if(a.key
       
        data.key) newtree->left=createTree(newtree->left,a);	    else if(a.key>newtree->data.key) newtree->right=createTree(newtree->right,a);	    return newtree;}bst DeleteNode(bst T,int key){	if(T==NULL){		printf("空树\n");		return NULL;	} 	  else if(key
        
         data.key) delete(T->left); else if(key>T->data.key) delete(T->right); else if(T->left&&T->right){ bst Tmp = findMin(T->right); T->data = Tmp->data; T->right=DeleteNode(T->right,key); }else{ bst Tmp = T; if(T->left == NULL) T=T->right; else if(T->right == NULL) T=T->left; free(Tmp); } return T;}int main(){ bst tree=NULL; bst T,T1; struct node a[4]={ {5,'a'},{15,'b'},{7,'c'},{21,'d'}}; tree=createTree(tree,a[0]); tree=createTree(tree,a[1]); tree=createTree(tree,a[2]); tree=createTree(tree,a[3]); visit(tree); T=find(5,tree); printf(" %c ",T->data.value); printf("min:%d_%c ",findMin(tree)->data.key,findMin(tree)->data.value); printf("max:%d_%c ",findMax(tree)->data.key,findMax(tree)->data.value); T1 =DeleteNode(tree,5); visit(T1); return 0;}
        
       
      
     
    
   

主要是删除有点难，但其实也不难，

（1）被删节点只有一个孩子，把孩子替换成该节点 （2）被删节点有两个孩子，取左子树的最大点或者右子树的最小点来替代

转载地址：http://wgqen.baihongyu.com/