温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何实现二叉查找树

发布时间:2021-10-21 11:12:40 来源:亿速云 阅读:158 作者:小新 栏目:编程语言

小编给大家分享一下如何实现二叉查找树,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

        二叉查找树又叫二叉排序树,其特点有:

  1. 对于每一棵子树,若左子树不为NULL,则左子树所有节点都小于它的根结点值。

  2. 对于每一棵子树,若右子树不为NULL,则左子树所有节点都大于它的根结点值。

  3. 没有键值相等的结点。

完成二叉查找树的基本操作有:

  1. 插入结点。

  2. 查找结点。

  3. 查找最小关键字:根据二叉查找树的特点,应该是最左边的结点

  4. 查找最大关键字:根据二叉查找树的特点,应该是最右边的结点

  5. 删除结点。

以上操作中,难点在与插入和删除。分别说下其主要思想:

插入:根据插入数据与结点的比较,找寻它的插入位置,若比结点值大,则往结点的右子树继续寻找,直到其右孩子为空,将新结点作为其右孩子;若比结点值小,则往结点的左子树继续寻找,直到其左孩子为空,将新结点作为其左孩子。

删除:设要查找的结点为d

  1. 若d有左子树,则用d的左孩子取代它,找到其左子树的最右边的结点r,把f的右孩子作为r的右子树。

  2. 若d无左子树,则直接用它的右孩子取代它。

但执行删除操作时要注意要删除的结点是否是几个特殊的结点:空结点、根结点、叶子节点。

代码示例:

//插入结点
//查找元素
//查找最小关键字
//查找最大关键字
//删除节点
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node* lchild;
    struct Node* rchild;
    struct Node* parent;
}Node;
//往二叉查找树中插入结点  
//插入的话,可能要改变根结点的地址,所以传的是二级指针  
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 ;
        }
    }
}
//输出节点元素
void print_tree(Node* root)
{
    if(root==NULL)
        return ;
    printf("%d\t",root->data);
    print_tree(root->lchild);
    print_tree(root->rchild);
}
//查找元素,找到返回关键字的结点指针,没找到返回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);
    }
}
//查找最小关键字,空树时返回NULL  
Node* search_min(Node* root)
{
    if(root==NULL)
    {
        return NULL;
    }
    if(root->lchild==NULL)
    {
        return root;
    }
    search_min(root->lchild);
}
//查找最大关键字
Node* search_max(Node* root)
{
    if(root==NULL)
    {
        return NULL;
    }
    if(root->rchild==NULL)
    {
        return root;
    }
    search_max(root->rchild);
}
//根据关键字删除某个结点,删除成功返回1,否则返回0  如果把根结点删掉,那么要改变根结点的地址,所以传二级指针
/*思想: 1。若p有左子树,p的左孩子取代它;找到其左子树的最右边的叶子结点r,把p的右子树作为r的右子树。
 2。若p没有左子树,直接用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 ;
    }
    //如没有左子树
    if(dnode->lchild==NULL)
    {
        //若这个节点是根节点
        if(dnode==*root)
        {
            *root=(*root)->rchild;
            (*root)->parent=NULL;
            free(dnode);
            return ;
        }
        //若这个节点是父节点的左孩子
        if(dnode->parent->lchild==dnode)
        {
            dnode->parent->lchild=dnode->rchild;
            dnode->rchild->parent=dnode->parent;
            free(dnode);
            return ;
        }
        //若这个节点是父节点的右孩子
        if(dnode->parent->rchild==dnode)
        {
            dnode->parent->rchild=dnode->rchild;
            dnode->rchild->parent=dnode->parent;
            free(dnode);
            return ;
        }
    }
    if(dnode->lchild!=NULL)
    {
    //找到其左子树的最右边的叶子结点r,把p的右子树作为r的右子树。
        Node* r=dnode->lchild;
        while(r->rchild!=NULL)
        {
            r=r->rchild;
        }
        r->rchild=dnode->rchild;
        dnode->rchild->parent=r->rchild;
        //用dnode的左节点来取代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;
}

以上是“如何实现二叉查找树”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI