程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言實現二叉查找樹（BST）的基本操作

C語言實現二叉查找樹（BST）的基本操作

編輯：關於C語言

C語言實現二叉查找樹（BST）的基本操作

我們在上一篇博客中講解了二叉樹，這一次我們來實現二叉樹的進階——二叉查找樹（Binary Search Tree），又稱二插排序樹(Binary Sort Tree)。所以簡稱為BST。二插查找樹的定義如下：

1.若左子樹不為空，則左子樹上所有節點的值均小於它的根節點的值；

2.若右子樹不為空，則右子樹上所有節點的值均大於它的根節點的值；

3.左右子樹也分別為二叉排序樹；

二叉排序樹的一個重要特點就是中序遍歷是一個遞增序列。

（1）節點的構造

typedef int elemType;
typedef struct BTNode{

    int data;
    struct BTNode *lChild;
    struct BTNode *rChild;
}BiTNode,*BiTree;

（2）創建二叉樹

創建二插排序樹的過程就是一個不斷插入節點的過程，並且最重要的就是查找插入的合適位置。

//創建二叉查找樹
/**
 *  輸入-1時創建結束,其實是一個不斷插入的過程
 */
int CreateBinarySearchTree(BiTree *T){

    printf("請輸入創建二叉查找樹的數字序列：\n");

    int num;
    scanf("%d",&num);

    while (num != -1) {
        Insert(T,num);
        scanf("%d",&num);
    }

    printf("%s函數執行，二叉查找樹創建成功\n",__FUNCTION__);
    return 1;
}

（3）插入節點

//插入節點
void Insert(BiTree *T,int x){

    //這裡創建一個要插入的節點
    BiTNode *pInsert = (BiTNode *)malloc(sizeof(BiTNode));
    pInsert->data = x;
    pInsert->lChild = NULL;
    pInsert->rChild = NULL;

    if ((*T) == NULL) {
        *T = pInsert;
    }

    if ((*T)->lChild == NULL && x < (*T)->data) {
        (*T)->lChild = pInsert;
    }

    if ((*T)->rChild == NULL && x > (*T)->data) {
        (*T)->rChild = pInsert;
    }

    //遞歸實現
    if (x < (*T)->data) {
        Insert(&(*T)->lChild, x);
    }

    if (x > (*T)->data) {
        Insert(&(*T)->rChild, x);
    }

    return;
}

（4）樹的中序遍歷和先序遍歷

樹的先序遍歷+中序遍歷可以唯一的確定一棵樹。並且二叉排序樹的中序遍歷必定是一個遞增的序列。用這樣的方法可以來驗證我們對一顆二叉排序樹進行操作後是否正確。

//中序遍歷二叉查找樹
//打印的應該是一個遞增的序列
void MiddleOrder(BiTree T){
    if (T == NULL) {
        return;
    }else{

        MiddleOrder(T->lChild);
        printf("%d ",T->data);
        MiddleOrder(T->rChild);
    }
}

//先序遍歷二叉查找樹
//因為先序遍歷+中序遍歷 可以唯一確定一棵樹，等下可以驗證樹是否正確
void PreOrder(BiTree T){

    if (T == NULL) {
        return;
    }else{

        printf("%d ",T->data);
        PreOrder(T->lChild);
        PreOrder(T->rChild);
    }
}

（5）查找元素

//查找某一個值
//返回1表示找到該值，返回0表示沒有找到
BiTNode *SearchValue(BiTree T,int x){
    if (T == NULL) {
        return 0;
    }else{
        if (x < T->data) {
            //查左子樹
            SearchValue(T->lChild, x);
        }else if (x > T->data){
            //查右子樹
            SearchValue(T->rChild, x);
        }else{
            //找到該值
            printf("該值的內存地址為：%p\n",T);
            return T;
        }
    }

    return NULL;
}

（6）刪除元素

//刪除某一個元素
BiTree *DeleteValue(BiTree *T,int x){


    //先要查找該節點，同時也要保存該節點的父節點
    BiTNode *searchNode;
    BiTNode *parentNode;

    //初始都指向根節點
    searchNode = *T;
    parentNode = *T;

    while (searchNode->data != x) {

        if (searchNode->lChild == NULL && searchNode->rChild == NULL) {
            //已經是葉子節點了，但是還沒有找到該值，表示樹種根本就沒有要刪除的節點
            printf("%s函數執行，不存在該值，刪除失敗\n",__FUNCTION__);
            return T;
        }

        if (x < searchNode->data) {

            parentNode = searchNode;
            searchNode = searchNode->lChild;
        }else if (x > searchNode->data){

            parentNode = searchNode;
            searchNode = searchNode->rChild;
        }else{
            break;
        }
    }

    if (searchNode->lChild == NULL && searchNode->rChild == NULL) {
        //是葉子節點
        if ((*T)->lChild == NULL && (*T)->rChild == NULL) {
            //是根節點
            free(*T);
            *T = NULL;
        }else{
            //不是根節點,是普通的葉子節點
            //需要判斷要刪除的節點是父節點的左孩子還是右孩子
            if (searchNode->data < parentNode->data) {
                //是左孩子
                parentNode->lChild = NULL;
            }else{
                //是右孩子
                parentNode->rChild = NULL;
            }
            free(searchNode);
            searchNode = NULL;
        }

        return T;
    }

    if (searchNode->lChild != NULL && searchNode->rChild == NULL) {
        //有左子樹，沒有右子樹
        //直接把父節點的指針指向右子樹即可，然後釋放自己;
        //首先需要判斷當前節點是父節點的左孩子還是右孩子
        if (searchNode->data < parentNode->data) {
            //是左孩子
            parentNode->lChild = searchNode->lChild;
        }else{
            //是右孩子
            parentNode->rChild = searchNode->lChild;
        }

        free(searchNode);
        searchNode = NULL;

        return T;
    }

    if (searchNode->lChild == NULL && searchNode->rChild != NULL) {
        //沒有左子樹，有右子樹
        if (searchNode->data < parentNode->data) {
            //是左孩子
            parentNode->lChild = searchNode->rChild;
        }else{
            //是右孩子
            parentNode->rChild = searchNode->rChild;
        }

        free(searchNode);
        searchNode = NULL;

        return T;
    }

    if (searchNode->lChild != NULL && searchNode->rChild != NULL) {
        //要刪除的節點既有左孩子，又有右孩子
        /**
         *  算法：刪除節點p的左子樹和右子樹均不為空。找到p的後繼y，因為y一定沒有左子樹，所以可以刪除y，並讓y的父節點成為y的右子樹的父節點，並用y的值代替p的值；
         
         如何找到要刪除節點的後繼節點,包括該後繼節點的父節點！！
         */

        BiTNode *nextNode;//尋找要刪除節點的後繼節點
        BiTNode *nextParentNode;//尋找要刪除節點的後繼節點的父節點
        nextParentNode = searchNode;
        nextNode = searchNode->rChild;
        while (nextNode->lChild != NULL) {
            nextParentNode = nextNode;
            nextNode = nextNode->lChild;
        }

        //這裡要判斷nextNode節點和nextParentNode節點的值大小，因為需要判斷要刪除節點是父親的左孩子還是右孩子
        if (nextNode->data < nextParentNode->data) {
            //是左孩子
            nextParentNode->lChild = nextNode->rChild;
        }else{
            //是右孩子
            nextParentNode->rChild = nextNode->rChild;
        }

        //代替值
        searchNode->data = nextNode->data;

        //刪除後繼節點
        free(nextNode);
        nextNode = NULL;

        return T;
    }

    return T;
}

（7）測試代碼

int main(int argc, const char * argv[]) {

    BiTree tree;

    //這個是引用傳遞
    CreateBinarySearchTree(&tree);
    
    MiddleOrder(tree);
    printf("\n");

    printf("請輸入要查找的元素：");
    int searchValue;
    scanf("%d",&searchValue);
    SearchValue(tree,searchValue);


    printf("請輸入要刪除的元素：");
    int deleteValue;
    scanf("%d",&deleteValue);
    DeleteValue(&tree, deleteValue);
    printf("先序遍歷：");
    PreOrder(tree);
    printf("\n中序遍歷：");
    MiddleOrder(tree);//遍歷檢查
    printf("\n");
    
    return 0;
}