二叉検索ツリー(二叉ソートツリー)の詳細実装C版

1、順序
詳細には、ノードの挿入、ツリーの構築、ノードの削除、最大値の検索、最小値の検索、指定したノードの前駆者と後継者の検索など、ツリーを検索するさまざまな操作が実行されます.
2、二叉検索ツリーの概要
あるいは空の木ですまたは、(1)左サブツリーが空でない場合、左サブツリー上のすべてのノードの値は、そのルートノードの値よりも小さい.(2)右サブツリーが空でない場合、右サブツリー上のすべてのノードの値はそのルートノードの値より大きい.(3)左,右サブツリーもそれぞれ二叉ソートツリー
3、二叉検索ツリーの各種操作
ここにはコードが示されています.注釈は非常に詳細です.具体的な操作はコードを参照してください.

/*************************************************************************
           ，       ：    、     、    、  、
       、     、            。           
    o(h),  h     
       ，         
*************************************************************************/

#include<stdio.h>
#include<stdlib.h>

//         
typedef int KeyType;
typedef struct Node
{
	KeyType key;          //   
    struct Node * left;   //     
	struct Node * right;  //     
	struct Node * parent; //       
}Node,*PNode;

//           
//    ，           ，         
void inseart(PNode * root,KeyType key)
{
	//       
	PNode p=(PNode)malloc(sizeof(Node));
	p->key=key;
	p->left=p->right=p->parent=NULL;
	//   ，       
	if((*root)==NULL){
		*root=p;
		return;
	}
	//       （*root）    
	if((*root)->left == NULL && (*root)->key > key){
		p->parent=(*root);
        (*root)->left=p;
		return;
	}
	//       （*root）    
	if((*root)->right == NULL && (*root)->key < key){
		p->parent=(*root);
        (*root)->right=p;
		return;
	}
	if((*root)->key > key)
		inseart(&(*root)->left,key);
	else if((*root)->key < key)
		inseart(&(*root)->right,key);
	else
		return;
}

//    ,            ，     NULL
PNode search(PNode root,KeyType key)
{
	if(root == NULL)
		return NULL;
	if(key > root->key) //     
		return search(root->right,key);
	else if(key < root->key) //     
		return search(root->left,key);
	else
		return root;
}

//       ,     NULL
PNode searchMin(PNode root)
{
	if(root == NULL)
		return NULL;
	if(root->left == NULL)
		return root;
	else  //       ，          
	    return searchMin(root->left);
}

//       ,     NULL
PNode searchMax(PNode root)
{
	if(root == NULL)
		return NULL;
	if(root->right == NULL)
		return root;
	else  //       ，          
	    return searchMax(root->right);
}

//         
PNode searchPredecessor(PNode p)
{
    //  
	if(p==NULL)
		return p;
	//    、         
	if(p->left)
    	return searchMax(p->left);
	//    ,              
	else{
		if(p->parent == NULL)
			return NULL;
		//      
		while(p){
    		if(p->parent->right == p)
	    		break;
			p=p->parent;
		}
        return p->parent;
	}
}

//         
PNode searchSuccessor(PNode p)
{
    //  
	if(p==NULL)
		return p;
	//    、         
	if(p->right)
    	return searchMin(p->right);
	//    ,              
	else{
		if(p->parent == NULL)
			return NULL;
		//      
		while(p){
    		if(p->parent->left == p)
	    		break;
			p=p->parent;
		}
        return p->parent;
	}
}

//           ,      1,    0
//        ，           ，       
int deleteNode(PNode* root,KeyType key)
{
	PNode q;
	//         
	PNode p=search(*root,key);
	KeyType temp;    //        
	//       
	if(!p)
		return 0;
	//1.         ，    
	if(p->left == NULL && p->right == NULL){
		//      ，          
		if(p->parent == NULL){
			free(p);
			(*root)=NULL;
		}else{
			//             
    		if(p->parent->left == p)
	     		p->parent->left=NULL;
	    	else  //             
	     		p->parent->right=NULL;
			free(p);
		}
	}

	//2.         
	else if(p->left && !(p->right)){
		p->left->parent=p->parent;
		//        ，        
		if(p->parent == NULL)
			*root=p->left;
		//             
		else if(p->parent->left == p)
        	p->parent->left=p->left;
		else //             
			p->parent->right=p->left;
		free(p);
	}
	//3.         
	else if(p->right && !(p->left)){
		p->right->parent=p->parent;
		//        ，        
		if(p->parent == NULL)
			*root=p->right;
        //             
		else if(p->parent->left == p)
        	p->parent->left=p->right;
		else //             
			p->parent->right=p->right;
		free(p);
	}
	//4.           ，     
	//              (            )
	//      ,           
    else{
		//          
		q=searchSuccessor(p);
        temp=q->key;
		//      
        deleteNode(root,q->key);
		p->key=temp;
	}
	return 1;
}

//         
void create(PNode* root,KeyType *keyArray,int length)
{
	int i;
	//          
	for(i=0;i<length;i++)
		inseart(root,keyArray[i]);
}

int main(void)
{
	int i;
    PNode root=NULL;
	KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};
	create(&root,nodeArray,11);
	for(i=0;i<2;i++)
		deleteNode(&root,nodeArray[i]);
	printf("%d
",searchPredecessor(root)->key);
	printf("%d
",searchSuccessor(root)->key);
	printf("%d
",searchMin(root)->key);
	printf("%d
",searchMax(root)->key);
	printf("%d
",search(root,13)->key);
	return 0;
}