王道数据结构自学-二叉排序树（二叉查找树）

二叉排序树就是将比结点大的值放在右结点，比结点小的值放在左结点。

// 构建树的结构
typedef int KeyType;
typedef struct BSTNode
{
	KeyType key;
	BSTNode* lchild;//树的左孩子结点
	BSTNode* rchild;//树的右孩子结点
}BSTNode, * BiTree;

1 插入

首先判断被插入的结点是否存在，不存在的话先给这个结点申请空间初始化（将左右孩子置空，数值等于要插入的值）
如果存在，看一下元素是否一样，一样就不插入了
如果存在且值不一样，值小于结点的值就放入左子树，反之放入右子树

int BST_Insert(BiTree& T, KeyType k) {
	if (NULL == T) {
		//为新结点申请空间，第一个结点作为树根
		T = (BiTree)malloc(sizeof(BSTNode));
		T->key = k;
		T->lchild = T->rchild = NULL;
		return 1;//代表插入成功
	}
	else if (k == T->key) {
		return 0;//元素相同就不插入
	}
	else if(k < T->key)
	{
		return BST_Insert(T->lchild, k);
	}
	else
	{
		return BST_Insert(T->rchild, k);
	}
}

2 创建

创建就是循环插入的过程

void Creat_BST(BiTree& T, KeyType str[], int n) {
	T = NULL;
	int i = 0;
	while (i < n) {
		BST_Insert(T, str[i]);//把某一个结点放入二叉树
		i++;
	}
}

3 查找

查找就是根据要查找的值比结点大还是比结点小的关系进行查找的过程。比结点大就要去右孩子查找，比结点小就要求左孩子查找，直至遍历完。

BSTNode* BST_Search(BiTree T, KeyType key, BiTree& p) {
	p = NULL;//存储要找的结点的父亲
	while (T != NULL && key != T->key) {
		p = T;
		if (key < T->key) {
			T = T->lchild;//比当前结点小，就左边找
		}
		else
		{
			T = T->rchild;//比当前结点大，就右边找
		}
	}
	return T;
}

4 删除

理解原理即可，考察代码几率不大

被删除结点的左子树存在，右子树为空，左子树直接顶替结点
被删除结点的左子树为空，右子树存在，右子树直接顶替结点
被删除结点的左右子树都存在，采取用左子树最大值或者右子树最小值顶替结点的方法，选一个即可

void DeleteNode(BiTree& root, KeyType x) {
	if (root == NULL) {
		return;
	}
	if (root->key > x) {
		DeleteNode(root->lchild, x);
	}
	else if (root->key < x) {
		DeleteNode(root->rchild, x);
	}
	else//找到了要删除的结点
	{
		if (root->lchild == NULL) {//左子树为空，右子树直接顶上去
			BiTree tempNode = root;//用临时的存着的目的是一会要给他free
			root = root->rchild;
			free(tempNode);
		}
		else if (root->rchild == NULL) {//右子树为空，左子树直接顶上去
			BiTree tempNode = root;
			root = root->lchild;
			free(tempNode);
		}
		else//左右子树都不为空
		{//一般的删除策略是：左子树的最大数据 或 右子树的最小数据 代替删除的结点
			//这里采用使用左子树最大数据代替删除结点的方法
			BiTree tempNode = root->lchild;
			if (tempNode->rchild == NULL) {
				tempNode = tempNode->rchild;
			}
			root->key = tempNode->key;
			DeleteNode(root->lchild, tempNode->key);
		}
	}
}