@rg070836rg 2016-03-27T05:31:40.000000Z 字数 1833 阅读 1676

二叉排序树

data_structure

一、介绍

若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

二、功能介绍

2.1、插入和构造

插入方法：

首先找到K所放置的位置，定位到已存在的某个节点。规则按照第一节介绍

然后申请空间，接在树后面

注意：这里需要引用，原因本文最后进行讨论。

构造方法：

每次读取一个数

用插入的方法生成树

代码如下：

//插入函数
template <class T>
void BiSortTree<T>::Insert(BiNode<T>* &p, int k)    //p为根结点
{
    if (p == NULL)//根结点
    {
        p = new BiNode<T>;
        p->data = k;
        p->lchild = p->rchild = NULL;
    }
    else
    {
        if (k < p->data)        //比根结点小的插在左子树
            Insert(p->lchild, k);
        else if (k>p->data)     //比根结点大的插在左子树
            Insert(p->rchild, k);
    }
}
template <class T>
void BiSortTree<T>::Insert(int k)
{
    Insert(root,k);
}
//构造函数(多次调用插入函数)
template <class T>
BiSortTree<T>::BiSortTree(int a[], int n)
{
    root = NULL;
    for (int i = 0; i < n; i++)
        Insert(root,a[i]);
}

2.2、删除函数

传入节点为空，删除失败，返回

若不空，继续定位，查找值比当前节点小，查找其左子树，否则右子树

若定位成功，分三种情况删除

叶子节点 --- 直接删除

单支节点 --- 用孩子节点的值链接到当前节点，删除原节点

双支节点 --- 考虑下二叉排序树的特点，即能想到，我要找的替代数字，应该是该节点左子树的最大孩子，也就是寻找左子树的最右孩子

//删除函数
template <class T>
void BiSortTree<T>::Delete(BiNode<T>* &p, int k)
{
    BiNode<T>* temp;
    if (p != NULL)
    {
        if (k < p->data)
            Delete(p->lchild, k);   //查找值k比当前值小，所以在其左子树找
        else if (k>p->data)
            Delete(p->rchild, k);   //查找值k比当前值大，所以在其右子树找
        else
        {
            if (p->lchild != NULL && p->rchild != NULL)  //双支节点
            {
                //寻找左子树的最右孩子
                temp = p->lchild;
                while (temp->rchild != NULL)
                    temp = temp->rchild;
                p->data = temp->data;
                Delete(p->lchild, temp->data);
            }
            else
            {
                temp = p;
                if (p->lchild == NULL)
                    p = p->rchild;
                else if (p->rchild == NULL)
                    p = p->lchild;
                delete temp;
            }
        }
    }
}
template <class T>
void BiSortTree<T>::Delete(int k)
{
    Delete(root, k);
}

2.3、查找函数

查找过程类似插入过程：

二叉树为空，查找失败，

查找值小于当前节点的值，递归查找左子树

查找值大于当前节点的值，递归查找右子树

//查找函数
template <class T>
BiNode<int>* BiSortTree<T>::Search(BiNode<T>* p, int k) //查找值为k的结点
{
    if (p == NULL)  //递归出口
        return NULL;
    else if (p->data == k)
        return p;
    else if (k < p->data)
        return Search(p->lchild, k);
    else
        return Search(p->rchild, k);
}
template <class T>
void BiSortTree<T>::Search(int k)
{
    if (Search(root, k)==NULL)
        cout << "未查找到" << endl;
    else
        cout << "查到为：" << Search(root, k)->data << endl;
}