华东师范大学
上海，中国
请与我们联系
注册
MENU

算法简介



二叉查找树（Binary Search Tree）


对树的介绍：

现在让我们来想像一颗树，把树根看作一个结点（我们叫它根节点），把树中的每个分支都看作一个结点（称为分支结点），把树中的每一个叶子都看作一个节点（称作叶子结点或叶结点）；然后，我们用圆圈来表示结点，再用线段连接树中相关的结点；最后，我们把树上下颠倒过来。这样，我们就用圆圈和线段抽象出了一棵小树的结构。当我们用图形来表示一棵树时，会把结点的值填在圆圈里。现在，我们要介绍一棵树之间结点之间的关系。如果结点ki和结点kj被一段线段连接，并且ki在kj的上端，我们就称ki是kj的父结点（也叫做双亲结点）；同时kj是ki的子结点（也叫做孩子结点）。

二叉树的介绍：

二叉树是一种特殊的树，对于二叉树中的任何结点，最多有两个子结点。为了更方便地表示二叉树中的结点，我们常常把第一个和第二个子结点分别称为左子结点和右子结点。 那么，我们学习树这种数据结构有什么用呢？其实，树是一种应用非常广泛的数据结构。下面，我们就来介绍二叉树的一个经典应用：二叉搜索树。

首先，二叉搜索树必须满足下面的条件：

1. 如果树T的根结点的左子树非空，那么左子树中的所有结点中的值都小于T的根结点中的值。

2. 如果树T的根结点的右子树非空，那么右子树中所有节点的值都大于T的根结点中的值。

3. 树T的根结点的左，右子树也都是查找树。 如果按中序遍历查找树T的结点，那么我们就得到一个排好序的结点序列。



二叉树查找

假设我们需要在查找树T中查找值为a的结点，我们需要做下面的事情：

1. 如果树T为空，那么查找失败，算法结束，否则进行第2步；

2. 如果t->data（根结点的值）等于a，那么查找成功，否则进行第3步；

3. 如果a小于t->data，那么t->lchild→t（即把根结点左孩子的值赋给根结点），转第1步（这样我们在根结点的左子树上继续进行递归搜索）；否则，t->rchild→t（这样我们在根结点的右子树上继续进行递归搜索），转第1步。


二叉树插入


我们试图将值为a的结点插入到查找树T中：

1.首先我们要先做查找，如果值为a的结点已经在查找树T中，我们则不做插入；

2.如果该结点不在树T中，则把它插在树T的适当位置上。我们依旧用一个例子来说明插入的方式。


二叉树删除


1.若被删结点有左子树，那么被删结点的位置由它的左子树的根结点来充当，它的右子树被链接在左子树的最右下方；

2.否则，被删结点的位置由它的右子树的根结点来充当。

 

typedef struct node
{
    int data;
    int bel;//结点的平衡度
    int len;//该结点到根结点的路径长度
    struct node *lchild;
    struct node *rchild;
}NODE;//二叉树的存储结构
 
 
void search(char a,NODE **p_p,NODE **p_q)//在查找树中查找键值为a的结点
{
    *p_p=NULL;
    *p_q=t;
    while(*p_q!=NULL)//*p_q为空，算法结束
    {
        if((*p_q)->data==a)
        {
            return;
        }//查找成功
        *p_p=*p_q;
        if(a<(*p_q)->data)//a小于当前结点值
        {
            *p_q=(*p_q)->lchild;
        }
        else
        {
            *p_q=(*p_q)->rchild;//a大于当前结点值
        }
    }
}
 
 
int insert(NODE **p_t,char a)//插入键值为a的结点
{
    NODE *r;
    search(a,&p,&q);//查找键值为a的结点
    if(q!=NULL)
        return 1;
    r=(NODE*)malloc(sizeof(NODE));
    r->data=a;
    r->lchild=NULL;
    r->rchild=NULL;
    r->len=0;
    if(p==NULL)//查找树为空
    {
       *p_t=r;
    }
    else if(p->data>a)//查找路径中最后一个结点的值大于a
        p->lchild=r;//将新结点插入到左子树
    else
        p->rchild=r;//将新结点插入到右子树
    return 0;//插入成功，返回0
}
 
 
Int delete (NODE ** p_t,char a)//删除结点
{
    search (*p_t,a,& p;&q); //执行后q如果不空，指向找到的结点
    if (q==NULL) return (1); //结点“a“不在树中
    if （p==NULL） //p为NULL，找到的结点为根，被删结点为根结点
    if （q->lchild==NULL) *p_t=q->rchild;
    else 
    { 
        r=q->lchild;
        while (r->rchid!=NULL) r=r->rchild; //找“最右”
        r->rchild=q->rchild;
        *p_t =q->lchild;
    }
    //将被删除的结点q不是根，作为子树的根来处理，同时完成父结点p的指针变化
    else if （q->lchild ==NULL )
    if （q==p->lchild） p-lchild=q->rchild;
    else p->rchild = q->rchild;
    else
    { 
        r=q-lchild;
        while (r->rchid!=NULL) r=r->rchild;
        r->rchild=q->rchild;
        if （q==p->lchild） p-lchild=q->lchild;
        else p->rchild = q->lchild;
    }
    free (q);
    Return 0;
}





可视化