内容纲要

1.二叉搜索树的概念

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

  1. 若左子树不空,则左子树上所有节点的值均小于它的根节点的值。
  2. 若右子树不空,则右子树上所有节点的值均大于它的根节点的值。
  3. 左、右子树也分别为二叉排序树。

二叉搜索树的中序序列必定有序。这一性质十分重要。如图是一个二叉搜索树:(百度百科
file
注意观察,每个节点的左孩子小于自己,右孩子大于自己。
二叉搜索树与平衡二叉树概念上无直接联系,但是平衡二叉搜索树性能最好。

2.二叉搜索树的基本操作

  • 查值
    二叉搜索树的查值操作与二分类似,先查根节点,若根节点值大于要查值,则对左子树指向上述操作,否则对右子树执行,直到查到。时间复杂度O(logn)级别。见伪代码:

    查找(查找值,树)
    {
    如果查找值等于根节点的值
        返回查到的节点;
    如果查找值小于根节点的值
        查找(查找值,左子树);
    如果查找值大于根节点的值
        查找(查找值,右子树);
    返回空;
    }
  • 插入值
    首先将要插入的值与根节点比较,若比根节点小,则插入左子树,重复这个操作,若比根节点大,则插入右子树,重复这个操作,这样讲比较抽象,具体见伪代码:

    插入(插入值,树)
    {
    如果插入值小于树的根节点的值
        插入(插入值,左子树);
    如果插入值大于等于树的根节点的值
        插入(插入值,右子树);
    如果树不存在
        申请新节点;
    }
  • 删除值
    这个相对复杂,但是只要把握好“二叉搜索树的中序序列必定有序”这个性质,其实也简单的批爆。
    首先,如果要删的节点是叶子节点,那么久直接删。
    如果要删的节点有左子树,将左子树下最靠右的节点值赋予想要删除的节点。
    如果要删的节点有右子树,将右子树下最靠左的节点值赋予想要删除的节点。
    具体见伪代码:

    删除(删除值,树)
    {
    删除节点 = 查找(删除值,树);
    如果删除节点是叶子节点
        删除删除节点;
    如果删除节点有左子树{
        删除节点值 = 左子树最右值;
        删除(左子树最右值,左子树);
    }
    如果删除节点有右子树{
        删除节点值 = 右子树最左值;
        删除(右子树最左值,右子树);
    }
    }

    也就是说,删除一个值时,其在中序序列中的相邻值会替代它,这样能保证其中序序列严格有序。

3.二叉搜索树的实现

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;

struct node //节点结构体
{
    int data; //数据
    node* l_child; //左孩子 
    node* r_child;//右孩子
};

class BSTree
{
public:
    BSTree(); //构造
    ~BSTree(); //析构
    void create(int n); //创建,n为数据量
    void insert(int x); //插入值
    void del(int x); //删值
    void print(); //打印序列
    node* srh(int x); //查找
private:
    node* tree;
};

BSTree::BSTree()
{
    tree = NULL;
}

void tree_del(node* tree)
{
    if(tree == NULL)
        return;
    tree_del(tree->l_child);
    tree_del(tree->r_child);
    delete tree;
}

BSTree::~BSTree()
{
    tree_del(tree);
}

node* new_node(int x) //创建新的节点
{
    // cout << "new_node" << endl;
    node* new_n = new node;
    new_n->data = x;
    new_n->l_child = NULL;
    new_n->r_child = NULL;
    return new_n;
}

node* tree_ins(node* tree,int x)
{
    if(tree == NULL)
        tree = new_node(x);
    else if(x >= tree->data)
        tree->r_child = tree_ins(tree->r_child,x);
    else
        tree->l_child = tree_ins(tree->l_child,x);
}

void BSTree::insert(int x)
{
    tree = tree_ins(tree,x);
}

void BSTree::create(int n)
{
    for(int i = 0;i < n;++i)
    {
        int tmp;
        cout << "Input the " << i + 1 << "th number: ";
        cin >> tmp;
        insert(tmp);
    }
}

node* tree_srh(node* tree,int x)
{
    if(tree == NULL)
    {
        // cout << "tree == NULL" << endl;
        return NULL;
    }
    if(x == tree->data)
        return tree;
    if(x > tree->data)
    {
        // cout << "x > tree->data" << endl;
        return tree_srh(tree->r_child,x);
    }
    if(x < tree->data)
    {
        // cout << "x < tree->data" << endl;
        return tree_srh(tree->l_child,x);
    }
    return NULL;
}

node* BSTree::srh(int x)
{
    return tree_srh(tree,x);
}

node* tree_del(node* tree,int x)
{
    node* p;
    //以下是定位操作
    if(tree == NULL)
    {
        cout << "tar == NULL" << endl;
        return NULL;
    }
    if(tree->data > x)
        tree->l_child = tree_del(tree->l_child,x);
    else if(tree->data < x)
        tree->r_child = tree_del(tree->r_child,x);
    //定位到之后,开始删除
    else
    {
        if(tree->l_child == NULL && tree->r_child == NULL)
        {
            // cout << tree->data << endl;
            delete tree;
            tree = NULL;
        }
        else if(tree->l_child != NULL)
        {
            // cout << "tree->l_child != NULL " << tree->data << endl;
            for(p = tree->l_child;p->r_child;p = p->r_child); //找出左子树最右值
            tree->data = p->data;
            tree->l_child = tree_del(tree->l_child,tree->data);
        }
        else if(tree->r_child != NULL)
        {
            // cout << "tree->r_child != NULL " << tree->data << endl;
            for(p = tree->r_child;p->l_child;p = p->l_child); //找出右子树最左值
            tree->data = p->data;
            tree->r_child = tree_del(tree->r_child,tree->data);
        }
    }
    return tree;
}

void BSTree::del(int x)
{
    tree = tree_del(tree,x);
}

void tree_prt(node* tree)
{
    if(tree)
    {
        tree_prt(tree->l_child);
        // cout << "tree_prt" << endl;
        cout << tree->data << " ";
        tree_prt(tree->r_child);
        // cout << "tree_prt" << endl;
    }
}

void BSTree::print()
{
    // cout << "print" << endl;
    tree_prt(tree);
    // cout << "~print" << endl;
    cout << endl;
}

//int main()
//{
//    int n;
//    cout << "Input the number of numbers: ";
//    cin >> n;
//    BSTree tree;
//    tree.create(n);
//    tree.print();
//    cout << "Input the number you want to delete: ";
//    int tmp; cin >> tmp;
//    tree.del(tmp);
//    tree.print();
//
//    return 0;
//}

(删除操作我debug了半小时,最后发现是在主函数中把它注释掉了,蔡的抠脚)


总提纲:《数据结构》期末提纲小结

发表评论

电子邮件地址不会被公开。 必填项已用*标注