[TOC]

性质

二叉搜索树本质上还是一棵二叉树，其满足以下性质（习惯性定义为）：

非空左子树的所有键值小于其根结点的键值
非空右子树的所有键值大于其根结点的键值
左右子树都是二叉搜索树

基本函数

//从二叉搜索树BST中查找x，返回结点地址
Poi Find(ElementType x, BinTree BST);

//从二叉搜索树BST中查找最小元素的结点地址
Poi FindMin(BinTree BST);

//从二叉搜索树BST中查找最大元素结点地址
Poi FindMax(BinTree BST);

//向二叉搜索树BST插入值为x的结点
BinTree Insert(ElementType x, BinTree BST);

//向二叉搜索树BST删除值为x的结点
BinTree Delete(ElementType x, BinTree BST);

Find

BiNode* BiSearchTree::Find(int x, BiNode* BST){
	if (!BST) return nullptr;

	if (x < BST->data) {
		Find(x, BST->left);
	}
	else if (x > BST->data) {
		Find(x, BST->right);
	}
	else {
		return BST;
	}
}

FindMin

最小元素一定在树的最左分支的结点

BiNode* BiSearchTree::FindMin(BiNode* BST){
	if (BST) {
		if (BST->left)return FindMin(BST->left);
	}
	return BST;
}

FindMax

最大元素一定在树的最右分支的结点

BiNode* BiSearchTree::FindMax(BiNode* BST){
	if (BST) {
		if (BST->right)return FindMin(BST->right);
	}
	return BST;
}

Insert

BiNode* BiSearchTree::Insert(int x, BiNode* BST){
	if (BST) {
		if (x < BST->data) {
			//向左子树
			BST->left = Insert(x, BST->left);
		}
		else if (x > BST->data) {
			//向右子树
			BST->right = Insert(x, BST->right);
		}
		else {
			//根即为当前数
			BST->cnt++;
		}
	}else{
        //构造新节点用于存储
		BST = new BiNode;
		BST->data = x;
		BST->left = BST->right = nullptr;
	}

	return BST;
}

Delete

需要考虑三种情况

要删除的是叶结点：直接删除，再修改其父结点指针NULL
要删除的结点只有一个"孩子"：将其父结点的指针指向要删除的"孩子"结点
要删除的结点有左右两棵子树：用另一结点替代被删除的结点（右子树的最小元素 或 左子树的最大元素）----- 这样做的好处是：右子树的最小值和左子树的最大值一定不会有两个"孩子"的结点

BiNode* BiSearchTree::Delete(int x, BiNode* BST){
	BiNode* tmp = nullptr;
	if (!BST) {
		cout << "未找到相应元素" << endl;
	}else if (x < BST->data) {
		BST->left = Delete(x, BST->left);
	}
	else if (x > BST->data) {
		BST->right = Delete(x, BST->right);
	}
	else{
		if (BST->left && BST->right) {
			tmp = FindMax(BST->left);

			BST->data = tmp->data;
			BST->left = Delete(BST->data, BST->left);
            
            /*这里也可以选择选取右子树最小值
            tmp = FindMin(BST->right);

			BST->data = tmp->data;
			BST->right = Delete(BST->data, BST->right);
            */

		}
		else {
			tmp = BST;
			if (!BST->left) {
				BST = BST->left;
			}
			else if (!BST->right) {
				BST = BST->right;
			}

			delete tmp;
		}
	}

	return BST;
}