二叉排序树

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;
}

三、引用

3.1、插入

文档中的两个函数，需要有引用才能正确。我们先看插入函数。
(1)

(2)

(3)

(4)

(5)

(6)

3.2、删除

再看一个影响到的函数，删除函数，这个似乎更加复杂。
(1)

(2)

(3)

(4)

(5)