二叉查找树

性质

• 左孩子<=结点<右孩子

二叉查找树

struct node
{
	int data;
	node* left;
	node* right;
};

二叉查找树的查找

//二叉查找树的查找
void search(node*root,int v)
{
	if (root == NULL)
	{
		//没找到
		return;
	}
	if (root->data == v)
	{
		//找到了
		return;
	}
	if (root->data > v)
	{
		//找左边
		search(root->left,v);
	}
	if (root->data < v)
	{
		//找右边
		search(root->right, v);
	}

}

二叉查找树的插入

//二叉查找树的插入
void insert(node* &root, int v)
{
	if (root == NULL)
	{
		//没找到
		root = new node;
		root->data = v;
		root->left = NULL;
		root->right = NULL;
		return;
	}
	if (root->data == v)
	{
		//找到了
		return;
	}
	if (root->data > v)
	{
		//插左边
		insert(root->left, v);
	}
	if (root->data < v)
	{
		//插右边
		insert(root->right, v);
	}
}

二叉查找树的的创建

//二叉查找树的的创建
node* create(int datas[],int n)
{
	node* root =NULL;
	for (int i = 0; i < n; i++)
	{
		insert(root, datas[i]);
	}
	return root;
}

删除

//删除
//找到一个结点的前驱结点(左子树的最右子树)
node* findPre(node* root)
{
	if (root == NULL)
		return NULL;
	node* p = root->left;
	if (p == NULL)
		return NULL;
	node* q = p->right;
	while (q!=NULL)
	{
		p = p->right;
		q = p->right;
	}
	return p;
}
//找到一个结点的后继结点(右子树的最左子树)
node* findPost(node* root)
{
	if (root == NULL)
		return NULL;
	node* p = root->right;
	if (p == NULL)
		return NULL;
	node* q = root->left;
	while (q != NULL)
	{
		p = p->left;
		q = p->left;
	}
	return p;
}
//删除一个结点
void deleteNode(node*& root,int v)
{
	if (root == NULL)
		return;
	if (root->data == v)//找到欲删除节点
	{
		if (root->left == NULL && root->right == NULL)
			root = NULL;
		else if (root->left != NULL)//找到前驱
		{
			node* pre = findPre(root);
			root->data = pre->data;
			deleteNode(root->left, pre->data);
			//使用前驱节点的左孩子代替前驱节点（因为没有右孩子),前驱节点的父节点指向前驱节点的左孩子
		}
		else if (root->right != NULL)
		{
			node* post = findPost(root);
			root->data = post->data;
			deleteNode(root->right, post->data);
		}
	}
	else if (root->data > v)
	{
		deleteNode(root->left, v);
	}
	else {
		deleteNode(root->right, v);
	}
}

• 注：删除优化小技巧：使用前驱节点的左孩子代替前驱节点（因为没有右孩子),前驱节点的父节点指向前驱节点的左孩子