算法小讲堂之二叉排序树|二叉搜索树|BST

一、定义

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

• 若左子树非空，则左子树上所有结点的值均小于根结点的值。
• 若右子树非空， 则右子树上所有结点的值均大于根结点的值
• 左、右子树也分别是一棵二叉排序树。

对于二叉树的每一个结点，我们可以有两种不同的定义方式，当然后面的操作也是分为两种：

• 其一（主要用于考研书籍）

typedef struct Node{
	ElemType data;
	struct Node *lchild, *rchild;
}Node;

• 其二（用于竞赛代码）

struct Node{
    int val,ls,rs,cnt;//分别表示的是结点的值、左儿子、右儿子、结点出现的次数
}tree[500010];

二、 查找操作

如果我们想查找某个值的元素是否存在在树中，我们可以从根节点的元素进行比较，然后我们将查找元素和根节点进行比较，如果根节点和查找元相等的话那么就找到了，如果查找元素比根节点大的话我们就往右子树走，否则往左子树走，直到找到了就返回找到的结点

• case1

Node *BST_Search(Node *root,ElemType key) {
    while(root != NULL && root->data != key) {
        if(root->data rchild;
        else root = root->lchild;
    }
    return root;
}

• case2

int find(int x,int v)//x是当前查询位置的下标，v是查询的值
{
	while(x != 0 && tree[x].val != v) {
		if(tree[x].val data = key;
    p->lchild = p->rchild = NULL;
}

int BST_insert(Node *root,ElemType key) {
    if(!root) {//如果是根节点元素为空的话
        root = Create_Node(key);
        return 1;
    }
    if(root->data == key)
        return 0;//已经存在，插入失败
    else if(root->data rchild == NULL) {
            Node *p = Create_Node(key);
            root->rchild = p;
            return 1;//成功插入
        } else {
            return BST_insert(root->rchild,key);
        }
    }
    else {//插入到左子树
    	if(root->lchild == NULL) {
            Node *p = Create_Node(key);
            root->lchild = p;
            return 1;//成功插入
        } else {
            return BST_insert(root->lchild,key);
        }
    }
}

• case2

void add(int x,int v)//x是当前查询位置的下标，v是插入的值
{
    if(tree[x].val==v){
        //如果恰好有重复的数，就把cnt++，退出即可，因为我们要满足第四条性质
        tree[x].cnt++;
        return ;
    }
    if(tree[x].val>v){//如果v