对二叉树的深入研究（4）二叉排序树

在数据结构中，线性表分为无序线性表和有序线性表.

无序线性表中的数据是无序的，因此在插入和删除时无需遵循任何规则. 可以在数据末尾插入它，也可以在数据末尾删除它. 但是，在搜索时需要遍历整个数据表，这导致无序线性表的搜索效率低.

有序线性表的数据相反. 在搜索数据时，由于数据是有序的，因此可以通过二分法，内插法和斐波那契搜索来实现. 但是，在进行插入和删除操作时，需要保持表中数据的顺序，这会花费大量时间.

然后，我们希望找到一种具有更高插入和删除效率以及更高搜索效率的数据结构. 因此，二进制排序树应运而生.

二进制排序树，也称为二进制搜索树，也称为二进制搜索树. 二进制排序树可以是空树，也可以是具有以下属性的二进制树:

（1）如果左子树不为空，则左子树上所有节点的值都小于或等于其根节点的值;

（2）如果右子树不为空，则右子树上所有节点的值都大于或等于其根节点的值;

（3）左和右子树分别也是二进制排序树；

现有序列: 61 87 59 47 35 73 51 98 37 93

构建过程如下:

1）索引i = 0，A [i] = 61，节点61作为根节点，如图2.1所示:

图2.1

2）索引i = 1，A [1] = 87，87> 61，并且节点61的右子元素为空，因此81是节点61的右子元素，如图2.2所示:

图2.2

3）索引i = 2，A [i] = 59，59

61，节点61的左子节点为空，因此59是节点61的左子节点，如图2.3所示:

图2.3

4）索引i = 3二叉排序树 for，A [3] = 47，47

图2.4

5）索引i = 4，A [4] = 35，35

图2.5

使用相同的规则遍历整个数组，以得到排序的二叉树，如图2.6所示.

图2.6

由二叉树的递归性质定义，并且也可以使用以下递归算法搜索二叉排序树.

如果树为空，则搜索将不匹配而结束.

如果搜索到的值等于根节点的值，则搜索成功. 否则，继续在子树中搜索. 如果搜索到的值小于根节点的值，则选择左子树；如果搜索的值大于根节点的值，则选择右子树.

在理想情况下，每次比较后，该树将被切成一半，几乎是搜索的一半.

遍历打印可以使用有序遍历，并且打印结果是从小到大的有序数组.

查找代码:

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 
/* 二叉树的二叉链表结点结构定义 */
typedef  struct BiTNode /* 结点结构 */
{
    int data;   /* 结点数据 */
    struct BiTNode *lchild, *rchild;    /* 左右孩子指针 */
} BiTNode, *BiTree;
/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(BiTree t, int key, BiTree f, BiTree *p) 
{  
    if (!t) /*  查找不成功 */
    { 
        *p = f;  
        return FALSE; 
    }
    else if (key == t->data) /*  查找成功 */
    { 
        *p = t;  
        return TRUE; 
    } 
    else if (key < t->data) 
        return SearchBST(t->lchild, key, t, p);  /*  在左子树中继续查找 */
    else  
        return SearchBST(t->rchild, key, t, p);  /*  在右子树中继续查找 */
}

对于图2.6中所示的二进制排序树，如果搜索节点键为47，则搜索可以成功. 如果搜索节点键为75，则树中不存在带有键75的节点，因此搜索失败，然后搜索指针p指向搜索路径的最后一个节点，即节点73.

二进制排序的插入基于对二进制排序的搜索. 插入节点是通过搜索找到适当的节点插入位置，然后直接将其放入. 实际上，第2.2节中逐步构造二进制排序树的过程就是节点插入过程. 可以得出结论二叉排序树 for，二进制排序树插入规则如下:

如果搜索键已存在于树中，则p指向数据节点.

如果搜索关键字不在树中，则p指向搜索路径上的最后一个节点.

例如: 如果在图2.6所示的二进制排序树中插入数据为60的节点.

首先找到数据为60的节点. 在二进制排序树中没有数据为60的节点，因此搜索失败. 此时，搜索指针p指向搜索路径的最后一个节点，即点59. 由于60> 59并且59节点的右子树为空，因此60节点被视为该节点的右子节点. 59个节点，并且插入完成. 插入的二进制排序树如图2.8所示.

图2.8

插入代码:

struct BiTree {
    int data;
    BiTree *lchild;
    BiTree *rchild;
};
 
//在二叉排序树中插入查找关键字key
BiTree* InsertBST(BiTree *t,int key)
{
    if (t == NULL)
    {
        t = new BiTree();
        t->lchild = t->rchild = NULL;
        t->data = key;
        return t;
    }
 
    if (key < t->data) 
        t->lchild = InsertBST(t->lchild, key);
    else
        t->rchild = InsertBST(t->rchild, key);
 
    return t;
}
 
//n个数据在数组d中，tree为二叉排序树根
BiTree* CreateBiTree(BiTree *tree, int d[], int n)
{
    for (int i = 0; i < n; i++)
        tree = InsertBST(tree, d[i]);
}

删除二叉树不再像插入二叉树那样容易，因为认为删除节点会影响树的其他部分的结构.

删除时需要考虑以下情况:

1）将该节点删除为叶节点；

2）删除的节点只是左子树；

3）删除的节点只是正确的子树

4）删除的节点同时具有左子树和右子树.

考虑到前三种情况，处理方法相对简单.

例如: 如果要删除图2.8中的节点93，只需直接删除该节点. 删除后的二进制排序树如图2.9所示:

图2.9

如果要删除的节点是仅具有右侧子树的节点35，则只需删除节点35并将节点35替换为右侧子树37节点. 删除的二进制排序树如图2.10所示:

图2.10

仅删除左侧子树的节点与此情况类似.

情况4相对复杂. 对于要删除的节点同时具有左子树和右子树的情况，最好的方法是找到其余序列中最接近的节点以替换已删除的节点. 这种替换不会影响树的整体结构. 那么如何获得最近的节点呢？

按顺序遍历可用于获取已删除节点的前任和后继. 选择前任节点或后继节点，而不要删除该节点.

例如: 要删除的节点为47，图2.8中二进制排序树的有序遍历顺序为35 37 47 51 59 60 61 73 87 9398. 则节点47的前任节点为37节点，而37节点可以直接替换47节点. 替换后的二进制排序树如图2.11所示:

图2.11

删除代码:

/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
Status DeleteBST(BiTree *T,int key)
{ 
    if(!*T) /* 不存在关键字等于key的数据元素 */ 
        return FALSE;
    else
    {
        if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ 
            return Delete(T);
        else if (key<(*T)->data)
            return DeleteBST(&(*T)->lchild,key);
        else
            return DeleteBST(&(*T)->rchild,key);
    }
}
/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
Status Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */
    {
        q=*p; *p=(*p)->lchild; free(q);
    }
    else if((*p)->lchild==NULL) /* 只需重接它的右子树 */
    {
        q=*p; *p=(*p)->rchild; free(q);
    }
    else /* 左右子树均不空 */
    {
        q=*p; s=(*p)->lchild;
        while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */
        {
            q=s;
            s=s->rchild;
        }
        (*p)->data=s->data; /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
        if(q!=*p)
            q->rchild=s->lchild; /*  重接q的右子树 */ 
        else
            q->lchild=s->lchild; /*  重接q的左子树 */
        free(s);
    }
    return TRUE;
}

二进制排序树是一种具有更高搜索和插入效率的数据结构. 同时，二叉树也是二叉树学习的重点和难点. 我希望通过本文的学习，我可以掌握搜索，插入和删除二进制排序树的基本操作. 我也希望读者能给予指导.

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-286323-1.html