[C++知识库]【C语言】二叉排序树、二叉查找树学习心得

一、基本概念

	二叉排序树 二叉排序树（Binary sort tree，BST），又称为二叉查找树，或者是一棵空树；或者是具有下列性质的二叉树：

    (1)若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；

    (2)若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值；

    (3)它的左、右子树也分别为二叉排序树。

二、基本操作

1. 查找
在指针T所指的二叉排序树中递归查找关键字为key的元素，
若查找成功，则返回ture，并查找到的数据对应的节点指针保存在p中，
否则返回false，并将查找路径上访问的最后一个节点指针保存在p中。
这里的参数parent指向每次递归遍历的子树的根节点的父节点，即始终是参数T的父节点，
它的初始值为NULL，其目的是跟踪查找路径上访问的当前节点的父节点（即上一个访问节点）
“该函数用来被后面的插入函数调用。”

//递归查找                                                       //不改变树T元素的时候，要用二直接传参 BinTree T
int SearchBST(BinTree T,int key,BinTree parent,BinTree *p)      //p是二级指针传参，函数调用要使用取址 &p   函数体中使用要用 *p
{
    if(T == NULL){              //树为空，查找失败
        *p = parent;
        return FLASE;
    }
    else if (T->data == key)    //查找成功，记录该节点（指针p指向该元素节点）
    {
        *p = T;
        return TRUE;
    }
    else if (T->data > key)                     //key < T->data 在左子树中继续寻找
    {
        return SearchBST(T->lchild,key,T,&(*p));    //&(*p)
    }
    else    // (T->data < key)                  //key > T->data 在右子树中继续寻找
    {
        return SearchBST(T->rchild,key,T,&(*p));
    }

}

2. 插入节点

//插入节点
int InsertBST(BinTree *T,int key)                       //要改变树T元素的时候，要用二级指针传参 BinTree *T = struct BiTNode **T
{
    BinTree ptr;                                        //树T路径上访问的最后一个节点
    if (SearchBST(*T,key,NULL,&ptr) == FLASE)           //查找失败，执行插入 &ptr
    {
        BinTree pNew = (BinTree)malloc(sizeof(BiTNode));    //创建一个新节点pNew
        pNew->data = key;
        pNew->lchild = NULL;
        pNew->rchild = NULL;

        if(ptr == NULL)                             //树T为空
        {                       
            *T = pNew;                              //插入的pNew为根节点
        }
        else if(key < ptr->data)
        {
            ptr->lchild = pNew;                     //向左子树下插入pNew
        }
        else if(key > ptr->data)
        {
            ptr->rchild = pNew;                     //向右子树下插入pNew
        }
        return TRUE;
    }
    else
    {
        return FLASE;
    }
}

3. 删除节点
1）叶子节点 ----- 找到直接删
2）仅有左子树或右子树的节点（独子节点）---- 找到直接删，然后它的子树继承它的位置
3）左右子树都有的节点 ----- 在它的左子树中找最大的节点，或者右子树中最小的节点，继承它的位置

//删除节点
int DeleteBST(BinTree *T,int key)
{
    if (*T == NULL)                 //树为空
    {
        return FLASE;
    }
    else if ((*T)->data == key)     //删除
    {
        return delete(&(*T));
    }
    else if (key < (*T)->data)      //往左子树继续找（递归）
    {
        return DeleteBST(&(*T)->lchild,key);
    }
    else if (key > (*T)->data)      //往右子树继续找（递归）
    {
        return DeleteBST(&(*T)->rchild,key);
    }
}

int delete(BinTree *pT)
{
    BinTree qT,sT;

    if((*pT)->lchild == NULL &&  (*pT)->rchild == NULL)         //叶子节点
    {
        free((*pT));
    }
    else if ((*pT)->rchild == NULL && (*pT)->lchild != NULL)    //只有左子树
    {
        qT = *pT;
        *pT = (*pT)->lchild;
        free(qT);
    } 
    else if ((*pT)->lchild == NULL && (*pT)->rchild != NULL)     //只有右子树
    {
        qT = *pT;
        *pT = (*pT)->rchild;
        free(qT);
    }
    else                                                        //有左右子树
    {
        qT = *pT;
        sT = (*pT)->lchild;             //转到pT的左子树中
        while (sT->rchild  != NULL)     //在左子树中找最大的（一直往右找）
        {
            qT = sT;                    //qT为sT的父节点
            sT = sT->rchild;            //循环结束，sT为最大的值（最右的值）
        }
        (*pT)->data = sT->data;         //赋值给pT

        if (qT != *pT)                  //重接sT的左子树
        {       
            qT->rchild = sT->lchild;    //qT != pT,接在qT右子树
        }
        else                            //qT == pT,qT(pT)的右子树还在，所以只能接在qT左子树
        {
            qT->lchild = sT->lchild;
        }

    }

}

4. 创建二叉排序树

//创建二叉排序树
 BinTree CreatBST(BinTree T,int array[],int num)
{
    for (int i = 0; i < num; i++)
    {
        InsertBST(&T,array[i]);
    }
    return T;    
}

三、完整源码

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FLASE 0

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BinTree;          //struct  BiTNode = BiTBode             struct  BiTNode * = BinTree

//递归查找1
BinTree searchBST(BinTree T,int key)
{
    if (T == NULL || T->data == key)
    {
        return T;
    }
    else if (key < T->data)
    {
        return searchBST(T->lchild,key);
    }
    else    //(key > T->data)
    {
        return searchBST(T->rchild,key);
    }
}

/*
在指针T所指的二叉排序树中递归查找关键字为key的元素，
若查找成功，则返回ture，并查找到的数据对应的节点指针保存在p中，
否则返回false，并将查找路径上访问的最后一个节点指针保存在p中。
这里的参数parent指向每次递归遍历的子树的根节点的父节点，即始终是参数T的父节点，
它的初始值为NULL，其目的是跟踪查找路径上访问的当前节点的父节点（即上一个访问节点）
"该函数用来被后面的插入函数调用。"
*/
//递归查找2                                                      //不改变树T元素的时候，要用二直接传参 BinTree T
int SearchBST(BinTree T,int key,BinTree parent,BinTree *p)      //p是二级指针传参，函数调用要使用取址 &p   函数体中使用要用 *p
{
    if(T == NULL){              //树为空，查找失败
        *p = parent;
        return FLASE;
    }
    else if (T->data == key)    //查找成功，记录该节点（指针p指向该元素节点）
    {
        *p = T;
        return TRUE;
    }
    else if (T->data > key)                     //key < T->data 在左子树中继续寻找
    {
        return SearchBST(T->lchild,key,T,&(*p));    //&(*p)
    }
    else    // (T->data < key)                  //key > T->data 在右子树中继续寻找
    {
        return SearchBST(T->rchild,key,T,&(*p));
    }

}

//插入节点
int InsertBST(BinTree *T,int key)                       //要改变树T元素的时候，要用二级指针传参 BinTree *T = struct BiTNode **T
{
    BinTree ptr;                                        //树T路径上访问的最后一个节点
    if (SearchBST(*T,key,NULL,&ptr) == FLASE)           //查找失败，执行插入 &ptr
    {
        BinTree pNew = (BinTree)malloc(sizeof(BiTNode));    //创建一个新节点pNew
        pNew->data = key;
        pNew->lchild = NULL;
        pNew->rchild = NULL;

        if(ptr == NULL)                             //树T为空
        {                       
            *T = pNew;                              //插入的pNew为根节点
        }
        else if(key < ptr->data)
        {
            ptr->lchild = pNew;                     //向左子树下插入pNew
        }
        else if(key > ptr->data)
        {
            ptr->rchild = pNew;                     //向右子树下插入pNew
        }
        return TRUE;
    }
    else
    {
        return FLASE;
    }
}

/*删除节点
1.叶子节点      ----- 找到直接删
2.仅有左子树或右子树的节点（独子节点）---- 找到直接删，然后它的子树继承它的位置
3.左右子树都有的节点       ----- 在它的左子树中找最大的节点，或者右子树中最小的节点，继承它的位置
*/
int delete(BinTree *pT)
{
    BinTree qT,sT;

    if((*pT)->lchild == NULL &&  (*pT)->rchild == NULL)         //叶子节点
    {
        free((*pT));
    }
    else if ((*pT)->rchild == NULL && (*pT)->lchild != NULL)    //只有左子树
    {
        qT = *pT;
        *pT = (*pT)->lchild;
        free(qT);
    } 
    else if ((*pT)->lchild == NULL && (*pT)->rchild != NULL)     //只有右子树
    {
        qT = *pT;
        *pT = (*pT)->rchild;
        free(qT);
    }
    else                                                        //有左右子树
    {
        qT = *pT;
        sT = (*pT)->lchild;             //转到pT的左子树中
        while (sT->rchild  != NULL)     //在左子树中找最大的（一直往右找）
        {
            qT = sT;                    //qT为sT的父节点
            sT = sT->rchild;            //循环结束，sT为最大的值（最右的值）
        }
        (*pT)->data = sT->data;         //赋值给pT

        if (qT != *pT)                  //重接sT的左子树
        {       
            qT->rchild = sT->lchild;    //qT != pT,接在qT右子树
        }
        else                            //qT == pT,qT(pT)的右子树还在，所以只能接在qT左子树
        {
            qT->lchild = sT->lchild;
        }

    }

}

//删除节点
int DeleteBST(BinTree *T,int key)
{
    if (*T == NULL)                 //树为空
    {
        return FLASE;
    }
    else if ((*T)->data == key)     //删除
    {
        return delete(&(*T));
    }
    else if (key < (*T)->data)      //往左子树继续找（递归）
    {
        return DeleteBST(&(*T)->lchild,key);
    }
    else if (key > (*T)->data)      //往右子树继续找（递归）
    {
        return DeleteBST(&(*T)->rchild,key);
    }
}



//创建二叉排序树
 BinTree CreatBST(BinTree T,int array[],int num)
{
    for (int i = 0; i < num; i++)
    {
        InsertBST(&T,array[i]);
    }
    return T;    
}
//中序遍历
void printTree_ZhongXu(BinTree T)
{
    if (T == NULL)
        return;

    printTree_ZhongXu(T->lchild);
    printf("%d ",T->data);
    printTree_ZhongXu(T->rchild);
}

int main()
{
    BinTree tree = NULL;
    BinTree lastNode;                   //查找路径上访问的最后一个节点

    int a[10] = {5,6,1,3,7,8,0,4,2,9};

    tree = CreatBST(tree,a,10);         //创建树

    printTree_ZhongXu(tree);            //中序遍历
    printf("\n");

    int ret = SearchBST(tree,4,NULL,&lastNode);     //查找树
    if (ret == TRUE)
    {
        printf("find yes !  lastNode = %d\n",lastNode->data);
    }else
    {
        printf("find no  !  lastNode = %d\n",lastNode->data);
    }

    DeleteBST(&tree,9);                //删除节点
    printTree_ZhongXu(tree);
    printf("\n");

    return 0;
}

以上就是学习二叉排序树过程中的心得，遇到了不少问题，注释的很详细，可以参考参考。