二叉查找树模板

/*************************************************************************
root 根节点的父亲节点设为NULL

*************************************************************************/

//二叉查找树结点描述

1 typedef int KeyType;
2 typedef struct Node
3 {
4     KeyType key;          //关键字
5     struct Node * left;   //左孩子指针
6     struct Node * right;  //右孩子指针
7     struct Node * parent; //指向父节点指针
8 } Node,*PNode;

//往二叉查找树中插入结点
//插入的话，可能要改变根结点的地址，所以传的是二级指针

 1 void inseart(PNode * root,KeyType key)
 2 {
 3     //初始化插入结点
 4     PNode p=(PNode)malloc(sizeof(Node));
 5     p->key=key;
 6     p->left=p->right=p->parent=NULL;
 7     //空树时，直接作为根结点
 8     if((*root)==NULL)
 9     {
10         *root=p;
11         return;
12     }
13     //插入到当前结点（*root）的左孩子
14     if((*root)->left == NULL && (*root)->key > key)
15     {
16         p->parent=(*root);
17         (*root)->left=p;
18         return;
19     }
20     //插入到当前结点（*root）的右孩子
21     if((*root)->right == NULL && (*root)->key < key)
22     {
23         p->parent=(*root);
24         (*root)->right=p;
25         return;
26     }
27     if((*root)->key > key)
28         inseart(&(*root)->left,key);
29     else if((*root)->key < key)
30         inseart(&(*root)->right,key);
31     else
32         return;
33 }

//查找元素,找到返回关键字的结点指针，没找到返回NULL

 1 PNode search(PNode root,KeyType key)
 2 {
 3     if(root == NULL)
 4         return NULL;
 5     if(key > root->key) //查找右子树
 6         return search(root->right,key);
 7     else if(key < root->key) //查找左子树
 8         return search(root->left,key);
 9     else
10         return root;
11 }

//查找最小关键字,空树时返回NULL

1 PNode searchMin(PNode root)
2 {
3     if(root == NULL)
4         return NULL;
5     if(root->left == NULL)
6         return root;
7     else  //一直往左孩子找，直到没有左孩子的结点
8         return searchMin(root->left);
9 }

//查找最大关键字,空树时返回NULL

1 PNode searchMax(PNode root)
2 {
3     if(root == NULL)
4         return NULL;
5     if(root->right == NULL)
6         return root;
7     else  //一直往右孩子找，直到没有右孩子的结点
8         return searchMax(root->right);
9 }

//查找某个结点的前驱 max( <x )

 1 PNode searchPredecessor(PNode p)
 2 {
 3     //空树
 4     if(p==NULL)
 5         return p;
 6     //有左子树、左子树中最大的那个
 7     if(p->left)
 8         return searchMax(p->left);
 9     else//无左子树的情况。
10     {//右子树的节点值都大于它，忽略，只能从父亲节点找。
11         if(p->parent == NULL)
12             return NULL;
13         //向上寻找前驱
14         while(p)
15         {
16             if(p->parent->right == p)
17                 break;
18             p=p->parent;
19         }
20         return p->parent;
21     }
22 }

/****查找某个结点的后继 : min{ >x } ****/

 1 PNode searchSuccessor(PNode p)
 2 {
 3     //空树
 4     if(p==NULL)
 5         return p;
 6     //有右子树、右子树中最小的那个
 7     if(p->right)
 8         return searchMin(p->right);
 9     else//此时无右子树，左子树都比它小忽略。只能从父亲节点找。
10     {
11         if(p->parent == NULL)
12             return NULL;
13         //向上寻找后继
14         while(p)
15         {
16             if(p->parent->left == p)
17                 break;
18             p=p->parent;
19         }
20         return p->parent;
21     }
22 }

/**根据关键字删除某个结点,删除成功返回1,否则返回0
如果把根结点删掉，那么要改变根结点的地址，所以传二级指针**/

{
    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;
}

//创建一棵二叉查找树

1 void create(PNode* root,KeyType *keyArray,int length)
2 {
3     int i;
4     //逐个结点插入二叉树中
5     for(i=0; i<length; i++)
6         inseart(root,keyArray[i]);
7 }

main 函数

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