二叉搜索树的一些相关算法介绍

二叉搜索树知识整理
服务器君一共花费了532.966 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

二叉搜索树中,左子树值大于根节点,右子树值大于根节点,每一层子树都遵守以上规则。二叉搜索能够大大加快搜索速度,常规的搜索只能一个个比较,算法复杂度为n,二叉搜索树由于其结果特点能够将搜索负载度减小为log(n)。

首先定义二叉树的节点数据结构:

struct Tree
{
	struct Tree *p;
	struct Tree *l;
	struct Tree *r;
	char name[31];
	int num;
};

首先考虑节点的插入:

从根节点开始,如果待插入节点的值大于根节点则向右子树查找,否则向左子树查找,直到到达叶节点。如果叶节点值大于待插入节点,将待插入节点设为叶节点的左子树,否则为右子树。注意,考虑空树的情况。

void add_num(char name[],struct Tree * tree,struct Tree *parent)
{
    struct Tree * new_node;
    if(flag==true) return;
    if(tree==0) {
        flag=true;
        new_node=new struct Tree();
        init(new_node);
        strcpy(new_node->name,name);
        new_node->num++;;
        if(parent==0) root=new_node;
        else 
        {
            if(strcmp(new_node->name,parent->name)>0)
            {
                parent->r=new_node;
            }
            else 
                parent->l=new_node;
            new_node->p=parent;
        }
        return;
    } 
    else 
    {
        if(strcmp(tree->name,name)==0) {tree->num++;flag=true;return;}
        else if(strcmp(tree->name,name)>0)
        {
            add_num(name,tree->l,tree);
        }
        else 
        {
            add_num(name,tree->r,tree);
        }
    }
}

删除节点:

删除节点操作比较复杂,需要进行分类讨论。当带删除节点不存左右儿子时,可以直接删掉;如果不同时存在左右儿子,假设存在左儿子,则删除节点后将其儿子作为其父亲的左儿子;

如果同时存在左右儿子,则需要找到其后继结点(大于他的最小节点),将其值拷贝到待删除节点位置,并且删除其后继结点(其后继结点不可能同时存在左右儿子!)

寻找后继结点的方法:如果其右子树不为空,则寻找右子树中的最小值,即查找右子树中最左边的节点值便可;如果其右子树为空,则其后继结点可能为当前节点的某一级的祖先,因此,一直向上循环查找,直到当前节点为父节点的左儿子为止,注意当前节点也是不断向上更新的。

寻找后继结点的代码:

struct Tree* successor(struct Tree *tree)
{
    struct Tree *temp,*temp1;
    if(tree->r!=0) return find_min(tree->r);
    temp1=tree;
    temp=tree->p;
    while(temp!=0&&temp->r==temp1)
    {
        temp1=temp;
        temp=temp->p;
    }
    if(temp==0) return tree; //如果不存在后继则返回自身
    else return temp;        //否则返回后继结点
}

删除节点的代码:(这里删除的是最小节点)

struct Tree* delete_min()
{
    struct Tree * tree=find_min(root); //找到value最小的那个节点
    struct Tree * temp1,*temp2;
    if(tree->l==0||tree->r==0)         //如果左子树或者右子树不存在
        temp1=tree;
    else temp1=successor(tree);       //如果存在左右儿子,则找到后继结点
    if(temp1->l!=0) temp2=temp1->l;
    else temp2=temp1->r;
    if(temp2!=0) temp2->p=temp1->p;
    if(temp1->p==0) root=temp2;       //
    else if(temp1==temp1->p->l) temp1->p->l=temp2;
    else temp1->p->r=temp2;
    if(temp1!=tree) tree->num=temp1->num;
    return temp1;
}

寻找最小值: 其实很简单,就是找整棵树的最左边的节点!

struct Tree* find_min(struct Tree *tree)
{
    if(tree->l!=0) return find_min(tree->l);
    else return tree;
}

最后,输出树也是很简单的递归,比如按照中序输出:

void search(struct Tree *tree)
{
    if(tree!=0)
    {
        printf("%s\n",tree->name);
        if(tree->l!=0)  search(tree->l);
        else if(tree->r!=0) search(tree->r);
    
    }
}

以上是链表形式的二叉搜索树的一些基本操作,以作备忘。

本文地址:http://www.nowamagic.net/librarys/veda/detail/206,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/206

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《软件随想录:程序员部落酋长Joel谈软件》 Joel Spolsky (作者), 阮一峰 (译者)

《软件随想录:程序员部落酋长Joel谈软件》是一部关于软件技术、人才、创业和企业管理的随想文集,作者以诙谐幽默的笔触将自己在软件行业的亲身感悟娓娓道来,观点新颖独特,内容简洁实用。全书分为 36讲,每一讲都是一个独立的专题。《软件随想录:程序员部落酋长Joel谈软件》从不同侧面满足了软件开发人员、设计人员、管理人员及从事软件相关工作的人员的学习与工作需要。

更多计算机宝库...