C/C++排序篇-二叉排序树

Miracle • 2023-05-23 • C++, 数据结构与算法 • 578 阅读

前言

二叉排序树又称二叉查找树，二叉树排序树的所有左孩子的关键字都小于其父结点的关键字，所有右孩子的关键字都大于其父结点的关键字。

实现

查找过程：

二叉排序树非空时，将给定的关键字值与根结点的关键字值进行比较，若相等则查找成功，否则判断关键字小于或大于根结点，下一步到对应的左右子树进行查找。直到查找成功，如遍历到叶子结点，仍未查找到则该关键字不存在树中。

template<typename ElementType>
BTreeNode<ElementType>* BSTree<ElementType>::SearchBST(ElementType _value,BTreeNode<ElementType> **father)
{
    BTreeNode<ElementType> *p=node;
    *father=nullptr;
    while (p&&p->elemValue!=_value)
    {
        *father=p;
        if (p->elemValue>_value)
        {
            //左子树
            p=p->lchild;
        }
        else if (p->elemValue<_value)
        {
            //右子树
            p=p->rchild;
        }
    }
    return p;
}

插入

根据输入序列构造二叉排序树，若排序树为空，则当前新增的元素作为树的根结点。若当前新增的元素大于根结点则插入到右子树中。若小于根结点的关键字则插入到左子树中。

template<typename ElementType>
void BSTree<ElementType>::Add(ElementType elem)
{
    BTreeNode<ElementType> *newNode=new BTreeNode<ElementType>();
    newNode->elemValue=elem;
    lastAdd_Node=newNode;
    if (node==nullptr)
    {
        node=newNode;
        length=1;
        return;
    }
    BTreeNode<ElementType> *tar_node=node;
    BTreeNode<ElementType> *p;
    BTreeNode<ElementType> **father=(BTreeNode<ElementType>**)malloc(sizeof(BTreeNode<ElementType>));
    queue_Sequence<BTreeNode<ElementType>*> queue;
    p=SearchBST(elem,father);
    if (p)
    {
        return;//已经存在不再插入 ？是不是可以在BTreeNode中定义count字段。这样可以正确记录重复的数据在二叉排序中的位置。
    }
    if (*father!=nullptr)
    {
        if ((*father)->elemValue>elem)
        {
            //左子树
            (*father)->lchild=newNode;
        }
        else if ((*father)->elemValue<elem)
        {
            //右子树
            (*father)->rchild=newNode;
        }
    }
    length+=1;
}

删除结点：在二叉排序树中删除一个结点，不能直接删除，需要删除后仍使排序树保持特性。

删除分三种情况

要删除的是叶子节点。
要删除的是叶子节点就直接删除。
要删除的是节点有左子树或右子树。
则让其左子树或右子树直接接上其父节点。
要删除的节点同时具有左子树和右子树。
若要删除的左右子树均不空，则删除结点时应该将其左子树、右子树连接到适当的位置。可以采用*p中序直接前驱结点*_prior代替*p结点。因为这个中序直接前驱是左子树中最大的数。
同样中序直接后续也可以代替*p的位置使调整后的结构平衡。
还有一种调整思路：我们知道*p的左子树一定都小于*p，那么左子树一定都小于*p的右子树，那何尝不可以让*p右子树接入左子树里最大的那个节点（这里也就是前面说的*p的中序前驱），然后左子树的头去代替*p的位置。
这些方法思想其实差不多，这里代码示例中采用直观一点的‘*p中序直接前驱结点*_prior代替*p结点’。

template<typename ElementType>
void BSTree<ElementType>::Remove(ElementType elem)
{
    //分为三种情况。
    //1.要删除的是叶子节点。
    //2.要删除的是节点有左子树或右子树。
    //3.要删除的节点同时具有左子树和右子树。
    BTreeNode<ElementType> *p;
    BTreeNode<ElementType> *q;//要删除的节点
    BTreeNode<ElementType> **father=(BTreeNode<ElementType>**)malloc(sizeof(BTreeNode<ElementType>));
    p=SearchBST(elem,father);
    if (!p)
    {
        return;
    }
    //查找到了
    if (p!=nullptr)
    {
        bool haveLChild=p->lchild!=nullptr;
        bool haveRChild=p->rchild!=nullptr;
        if ((!haveLChild)&&(!haveRChild))
        {
            //1.要删除的是叶子节点。直接删除
            if ((*father)->lchild==p)
            {
                (*father)->lchild=nullptr;
            }
            else if ((*father)->rchild==p)
            {
                (*father)->rchild=nullptr;
            }

        }
        else if ((haveLChild!=haveRChild))
        {
            q=p;
            //2.要删除的节点有左子树或右子树。
            if (haveLChild)
            {
                //左子树
                if ((*father)->lchild == p)
                {
                    (*father)->lchild = p->lchild;
                }
                else if ((*father)->rchild == p)
                {
                    (*father)->rchild = p->lchild;
                }
            }
            else
            {
                //右子树
                if ((*father)->lchild == p)
                {
                    (*father)->lchild = p->rchild;
                }
                else if ((*father)->rchild == p)
                {
                    (*father)->rchild = p->rchild;
                }
            }
        }
        else if (haveLChild&&haveRChild)
        {
            BTreeNode<ElementType> *_prior=p->lchild;
            BTreeNode<ElementType> *_priorFather;
            //找到左子树中最大的结点。即中序遍历*p时的直接前驱。用*p中序直接前驱结点*_prior代替*p结点
            while (_prior->rchild)
            {
                _priorFather=_prior;
                _prior=_prior->rchild;
            }
            if (p->lchild!=_prior)
            {
                _priorFather->rchild=_prior->lchild;//将prior的左子树接prior父节点的右子树上，即接到prior位置上。
            }
            else
            {
                //如果左子树没有右子树，那么就把左子树的左子树接到*p的左节点上。
                p->lchild=_prior->lchild;
            }
            //*p右子树接入*p的_prior直接前驱
            p->elemValue=_prior->elemValue;
            q=_prior;
        }
    }
    if (q)
    {
        delete(q);
        q=nullptr;
    }
}

经过多次的对二叉排序树进行调整，二叉排序树形态发生了变化，查找效率会有所降低。所以我们想要让二叉排序树尽量保持平衡，于是提出了平衡二叉树的概念。这个我们下次再讲！

C/C++平衡二叉树 - 麦瑞克博客 (playcreator.cn)