[数据结构与算法]二叉搜索树

二叉搜索树

二叉搜索树：左子树 < 根节点 < 右子树。且不能出现相同的val。

树的初始化

用数组模拟二叉树

const int maxn = 500050;

struct hzw	//某dalao qaq
{
	int lc,rc,val;	//分别代表左儿子、右儿子和当前节点的val
}a[maxn];

int cur,root;	//cur为节点的编号,root为根节点的编号

二叉查找树的初始化

const int INF = 0x3f3f3f3f<<1; //设置一个极大值

int New(int val)	//新建一个节点 
{
    a[++cur].val = val;	//将第cur个节点内储存的值赋为val
    return cur;	//返回节点的编号
}

void Build() //初始化一个二叉搜索树，其含有一个正无穷和负无穷val的节点
{
    New(-INF), New(INF);	//建立极大值和极小值节点
    root = 1, a[1].rc = 2;	//根节点即为编号为1的节点。
}

为了避免越界，减少边界情况的特殊判断，编程实现时一般在 树中额外插入一个val为正无穷和负无穷的节点。 仅由这两个节点构成的B二叉搜索树就是一棵初始的空BST。如果要遍历二叉搜索树时，只需要跳过输出val为INF和-INF的点即可。

二叉查找树的插入

void Insert(int &p, int val) //其中的p为根节点
{
    if (p == 0) //如果当前节点还没有被建立过，建立一个节点
	{
        p = New(val); //p为实参，此时父亲节点的lc和rc会被同时更新
        return;
    }
    if (val == a[p].val) return;	//不能出现相同的val
    if (val < a[p].val) Insert(a[p].lc, val);	
    else Insert(a[p].rc, val);
}

我们通过插入操作来生成一棵二叉查找树。函数中的参数p为根节点的编号，每次插入时都从根节点开始。

二叉搜索树的查找

在BST中检索是否存在值为val的节点。 设变量p等于根节点root，执行以下过程：

1.若p的值等于val，则已经找到

2.若p的值大于val

    (1) 若p的左儿子为空，则说明不存在val

    (2）若p的左儿子不空，在p的左子树中递归进行检索

3.若p的值小于val

    (1) 若p的右子节点为空，则说明不存在val

    (2) 若p的右子节点不空，在p的右子树中递归进行检索

int Find(int p, int val) //p为根节点
{
	if(p == 0) return 0; //检索失败
 	if(val == a[p].val) return p; //检索成功
 	if(val < a[p].val) return Find(a[p].lc, val); //递归检索左子树
 	else return Find(a[p].rc, val);//递归检索右子树
}

二叉搜索树的删除

二叉树的删除操作，首先需要二叉树查找后继。

二叉搜索树的后继

二叉树的后继是指，在二叉树中找到大于某一点val的最小节点。

初始化ans为正无穷节点的编号(编号为2)。然后，从根节点开始在BST中检索val。在检索的过程中，每经过一个节点，都检查该节点的值，判断能否更新所求的后继val。
检索完成后，有三种可能的结果：

1.没有找到val，此时val的后继就在已经经过的节点中，val即为所求。
2.找到了值为val的节点p，但p没有右子树与上一种情况相同，val即为所求
3.找到了值为val的节点p，且p有右子树从p的右子节点出发，一直向左走，就找到了val的后继

int GetNext(int val) 
{
	//ans为所求节点编号，首先初始化为无穷大节点的编号 
    int ans = 2;
    int p = root;
    while(p) //从根节点一直往下搜索，直到空节点为止
	{
        if (val == a[p].val) //找到值为val的点
		{
            if(a[p].rc > 0) //如果该节点有右子树
			{
                p = a[p].rc;	//该节点的右子树即为初步所求点
                while(a[p].lc > 0) p = a[p].lc;	//当该点有左子树，不断往左搜找到后继点
                ans = p;
            }
            break;	//找到点了就退出
        }
        if(a[p].val > val && a[p].val < a[ans].val) ans = p;	//满足条件就更新ans的值
        p = val < a[p].val ? a[p].lc : a[p].rc;	//判断往左搜还是往右搜
    }
    return a[ans].val;
}

删除