学步园

二叉搜索树，详情见算法导论，直接代码。

/*
二叉查找树，实现了以下操作：插入结点、构造二叉树、删除结点、
查找、查找最大值、查找最小值、查找指定结点的前驱和后继。
所有操作时间复杂度 均为o(h),其中h是树的高度 

改变二叉树 ，用二级指针 
*/  
#include<iostream>
#include<stdio.h>  
#include<stdlib.h>
using namespace std;  

struct node  
{  
    int key;          //关键字  
    struct node *left;   //左孩子指针  
    struct node *right;  //右孩子指针  
    struct node *p; //指向父节点指针  
};  
  
//插入结点  
//插入的话，可能要改变根结点的地址，所以传的是二级指针
void insert(node** root,int key)  
{  
    node *p=(node*)malloc(sizeof(node)); 
	 
    p->key=key;  
    p->left=p->right=p->p=NULL; 
	
    if(*root==NULL)//空树,直接作为根结点 
	{  
        *root=p;  
        return;  
    }  
    //插入左孩子  
    if((*root)->left==NULL && key<(*root)->key)
	{  
        p->p=(*root);  
        (*root)->left=p;  
        return;  
    }  
    //插入右孩子  
    if((*root)->right==NULL && key>(*root)->key)
	{  
        p->p=(*root);  
        (*root)->right=p;  
        return;  
    }  
    
    if(key< (*root)->key) //插入到左子树 
    	insert(&(*root)->left,key);  
    else if(key> (*root)->key) //插入到右子树 
    	insert(&(*root)->right,key); 
    else  
        return;  
}  
  
//查找元素,找到返回关键字的结点指针，没找到返回NULL  
node* search(node* root,int key)  
{  
    if(root==NULL||key==root->key)  
        return root;  
        
    if(key >root->key) //查找右子树  
        return search(root->right,key);  
    else if(key < root->key) //查找左子树  
        return search(root->left,key);    
}  
  
//查找最小关键字,空树时返回NULL，否则一直向左子树查找  
node* searchMin(node* root)  
{  
    while(root->left!=NULL)
		root=root->left;
	return root; 
}  
 
//查找最大关键字,空树时返回NULL，否则一直向右子树查找  
node* searchMax(node* root)  
{  
    while(root->right!=NULL)
		root=root->right;
	return root; 
}  
  
//查找某个结点的前驱  
node* searchPredecessor(node *p)  
{  
    //空树  
    if(p==NULL)  
        return p;
		  
    //有左子树、左子树中最大的那个  
    if(p->left!=NULL)  
        return searchMax(p->left);  
    
	//无左子树,查找某个结点的右子树遍历完了  
    else
	{  
        if(p->p == NULL)  
            return NULL; 
			 
        //向上寻找前驱  
        while(p)
		{  
            if(p->p->right==p)//当p是右子树时，根就是前驱  
                break;  
            p=p->p;  
        }  
        return p->p;  
    }  
}  
  
//查找某个结点的后继  
node* searchSuccessor(node* p)  
{  
    if(p->right!=NULL)//有右子树、右子树中最小的那个 
		 return searchMin(p->right); 
        
    //无右子树,查找某个结点的左子树遍历完了  
    else
	{  
        if(p->p==NULL)  
            return NULL; 
			 
        //向上寻找后继  
        while(p)
		{  
            if(p->p->left==p)//当p是左子树时，根就是后继 
                break;  
            p=p->p;  
        }  
        return p->p;  
    }  
}  
  
//这里跟算法导论有点区别，未考虑删根节点 
void transplant(node** u,node** v)
{		
	if(*u==(*u)->p->left)
		(*u)->p->left=*v;
	else
		(*u)->p->right=*v;
	if(v!=NULL)
		(*v)->p=(*u)->p;
}

//如果把根结点删掉，那么要改变根结点的地址，所以传二级指针 
int deleteNode(node** root,int key)  
{  
     
    node* p=search(*root,key); //查找到要删除的结点 
    node *y=NULL;
    
	if(p->left==NULL)
		{
		transplant(&p,&(p->right));	 
		}
		
	else if(p->right==NULL)
		transplant(&p,&(p->left));
	else//左右不为空 
	{
		y=searchMin(p->right);
		
		if(y->p!=p)//是右子树,y右子树替换y，y替换p 
		{
			transplant(&y,&(y->right));
			y->right=p->right;
			y->right->p=y;
		} 
		transplant(&p,&y);//y是右孩子 
		y->left=p->left;
		y->left->p=y;
	} 
}

//创建二叉查找树  
void create(node** root,int *keyArray,int length)  
{  
    int i;  
    //逐个结点插入二叉树中  
    for(i=0;i<length;i++)  
        insert(root,keyArray[i]);  
}  
  
int main(void)  
{  
    int i;  
    node* root=NULL;  
    int a[11]={15,6,18,3,7,17,20,2,4,13,9};
	/*
			    15
		    6       18
		 3    7   17  20
		2 4    13
			  9	
	*/  
    create(&root,a,11);
	 
	printf("%d\n",searchPredecessor(root)->key); //15的前驱13  
    printf("%d\n",searchSuccessor(root)->key);//15后继17 
    printf("%d\n",searchMin(root)->key);//2  
    printf("%d\n",searchMax(root)->key);//20  
    printf("%d\n",search(root,13)->key);//13
	printf("%d\n",search(root,13)->left->key);//查找13的左子树9 
	
    deleteNode(&root,6);
    printf("删去6之后：\n");
    /*
			    15
		    7      18
		 3   13   17  20
	   2 4  9
	*/  
	root=root->left;//节点7 
    printf("%d\n",searchPredecessor(root)->key); //7的前驱4 
    printf("%d\n",searchSuccessor(root)->key);//7后继9  
    printf("%d\n",searchMin(root)->key);  //2  
    printf("%d\n",searchMax(root)->key);  //13
    printf("%d\n",search(root,3)->key);
    printf("%d\n",search(root,3)->left->key); //查找3的左子树2  
    return 0;  
}