如何實(shí)現(xiàn)二叉查找樹(shù)

小編給大家分享一下如何實(shí)現(xiàn)二叉查找樹(shù)，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

        二叉查找樹(shù)又叫二叉排序樹(shù)，其特點(diǎn)有：

1. 對(duì)于每一棵子樹(shù)，若左子樹(shù)不為NULL，則左子樹(shù)所有節(jié)點(diǎn)都小于它的根結(jié)點(diǎn)值。
   

2. 對(duì)于每一棵子樹(shù)，若右子樹(shù)不為NULL，則左子樹(shù)所有節(jié)點(diǎn)都大于它的根結(jié)點(diǎn)值。

3. 沒(méi)有鍵值相等的結(jié)點(diǎn)。

完成二叉查找樹(shù)的基本操作有：

1. 插入結(jié)點(diǎn)。
   

2. 查找結(jié)點(diǎn)。

3. 查找最小關(guān)鍵字：根據(jù)二叉查找樹(shù)的特點(diǎn)，應(yīng)該是最左邊的結(jié)點(diǎn)

4. 查找最大關(guān)鍵字：根據(jù)二叉查找樹(shù)的特點(diǎn)，應(yīng)該是最右邊的結(jié)點(diǎn)

5. 刪除結(jié)點(diǎn)。

以上操作中，難點(diǎn)在與插入和刪除。分別說(shuō)下其主要思想：

插入：根據(jù)插入數(shù)據(jù)與結(jié)點(diǎn)的比較，找尋它的插入位置，若比結(jié)點(diǎn)值大，則往結(jié)點(diǎn)的右子樹(shù)繼續(xù)尋找，直到其右孩子為空，將新結(jié)點(diǎn)作為其右孩子；若比結(jié)點(diǎn)值小，則往結(jié)點(diǎn)的左子樹(shù)繼續(xù)尋找，直到其左孩子為空，將新結(jié)點(diǎn)作為其左孩子。

刪除：設(shè)要查找的結(jié)點(diǎn)為d

1. 若d有左子樹(shù)，則用d的左孩子取代它，找到其左子樹(shù)的最右邊的結(jié)點(diǎn)r，把f的右孩子作為r的右子樹(shù)。
   

2. 若d無(wú)左子樹(shù)，則直接用它的右孩子取代它。

但執(zhí)行刪除操作時(shí)要注意要?jiǎng)h除的結(jié)點(diǎn)是否是幾個(gè)特殊的結(jié)點(diǎn)：空結(jié)點(diǎn)、根結(jié)點(diǎn)、葉子節(jié)點(diǎn)。

代碼示例：

//插入結(jié)點(diǎn)
//查找元素
//查找最小關(guān)鍵字
//查找最大關(guān)鍵字
//刪除節(jié)點(diǎn)
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node* lchild;
    struct Node* rchild;
    struct Node* parent;
}Node;
//往二叉查找樹(shù)中插入結(jié)點(diǎn)  
//插入的話(huà)，可能要改變根結(jié)點(diǎn)的地址，所以傳的是二級(jí)指針  
void insert_node(Node** root,int _data)
{
    Node* newnode=(Node*)malloc(1*sizeof(Node));
    newnode->data=_data;
    newnode->lchild=NULL;
    newnode->rchild=NULL;
    newnode->parent=NULL;
    if(*root==NULL)
    {
        *root=newnode;
        return ;
    }
    if((*root)->lchild==NULL && _data < (*root)->data)
    {
        (*root)->lchild=newnode;
        newnode->parent=*root;
        return ;
    }
    if((*root)->rchild==NULL && _data > (*root)->data)
    {
        (*root)->rchild=newnode;
        newnode->parent=*root;
        return ;
    }
    if( _data < (*root)->data )
    {
        insert_node(&(*root)->lchild,_data);
    }
    else
    {
        if( _data > (*root)->data)
        {
            insert_node(&(*root)->rchild,_data);
        }
        else
        {
            return ;
        }
    }
}
//輸出節(jié)點(diǎn)元素
void print_tree(Node* root)
{
    if(root==NULL)
        return ;
    printf("%d\t",root->data);
    print_tree(root->lchild);
    print_tree(root->rchild);
}
//查找元素,找到返回關(guān)鍵字的結(jié)點(diǎn)指針，沒(méi)找到返回NULL  
Node* find_node(Node* root,int _data)
{
    if(root==NULL || ( _data == root->data))
    {
        return root;
    }
    if( _data < root->data )
    {
        return find_node(root->lchild,_data);
    }
    if(_data > root->data)
    {
        return find_node(root->rchild,_data);
    }
}
//查找最小關(guān)鍵字,空樹(shù)時(shí)返回NULL  
Node* search_min(Node* root)
{
    if(root==NULL)
    {
        return NULL;
    }
    if(root->lchild==NULL)
    {
        return root;
    }
    search_min(root->lchild);
}
//查找最大關(guān)鍵字
Node* search_max(Node* root)
{
    if(root==NULL)
    {
        return NULL;
    }
    if(root->rchild==NULL)
    {
        return root;
    }
    search_max(root->rchild);
}
//根據(jù)關(guān)鍵字刪除某個(gè)結(jié)點(diǎn),刪除成功返回1,否則返回0  如果把根結(jié)點(diǎn)刪掉，那么要改變根結(jié)點(diǎn)的地址，所以傳二級(jí)指針
/*思想： 1。若p有左子樹(shù)，p的左孩子取代它；找到其左子樹(shù)的最右邊的葉子結(jié)點(diǎn)r，把p的右子樹(shù)作為r的右子樹(shù)。
 2。若p沒(méi)有左子樹(shù)，直接用p的右孩子取代它。
*/
void delete_node(Node** root,int _data)
{
    if(root==NULL)
        return ;
    Node* dnode=find_node(*root,_data);
    if(dnode==NULL)
    {
        return ;
    }
    if(dnode->lchild==NULL && dnode->rchild==NULL && dnode!=*root)
    {
        if(dnode->parent->lchild==dnode)
        {
            dnode->parent->lchild=NULL;
        }
        if(dnode->parent->rchild==dnode)
        {
            dnode->parent->rchild=NULL;
        }
        free(dnode);
        dnode=NULL;
        return ;
    }
    //如沒(méi)有左子樹(shù)
    if(dnode->lchild==NULL)
    {
        //若這個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)
        if(dnode==*root)
        {
            *root=(*root)->rchild;
            (*root)->parent=NULL;
            free(dnode);
            return ;
        }
        //若這個(gè)節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子
        if(dnode->parent->lchild==dnode)
        {
            dnode->parent->lchild=dnode->rchild;
            dnode->rchild->parent=dnode->parent;
            free(dnode);
            return ;
        }
        //若這個(gè)節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子
        if(dnode->parent->rchild==dnode)
        {
            dnode->parent->rchild=dnode->rchild;
            dnode->rchild->parent=dnode->parent;
            free(dnode);
            return ;
        }
    }
    if(dnode->lchild!=NULL)
    {
    //找到其左子樹(shù)的最右邊的葉子結(jié)點(diǎn)r，把p的右子樹(shù)作為r的右子樹(shù)。
        Node* r=dnode->lchild;
        while(r->rchild!=NULL)
        {
            r=r->rchild;
        }
        r->rchild=dnode->rchild;
        dnode->rchild->parent=r->rchild;
        //用dnode的左節(jié)點(diǎn)來(lái)取代ta
        if(dnode==*root)
        {
            *root=dnode->lchild;
            (*root)->parent=NULL;    
        }
        else
        {
            if(dnode->parent->lchild==dnode)
            {
                dnode->parent->lchild=dnode->lchild;
                dnode->lchild->parent=dnode->parent;
            }
            if(dnode->parent->rchild==dnode)
            {
                dnode->parent->rchild=dnode->lchild;
                dnode->lchild->parent=dnode->parent;
            }
        }
        free(dnode);
        dnode=NULL;
    }
}
int main(int argc, char const *argv[])
{
    Node* root=NULL;
    insert_node(&root,15);
    insert_node(&root,6);
    insert_node(&root,18);
    insert_node(&root,3);
    insert_node(&root,7);
    insert_node(&root,17);
    insert_node(&root,20);
    
    print_tree(root);
    printf("\n");
    Node* f=find_node(root,6);
    if(f!=NULL)
    {
        printf("%d\n",f->parent->data);
    }
    delete_node(&root,3);
    print_tree(root);
    printf("\n");
    return 0;
}

以上是“如何實(shí)現(xiàn)二叉查找樹(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！