二叉排序树

一、介绍

若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

二、功能介绍

2.1、插入和构造

插入方法：

首先找到K所放置的位置，定位到已存在的某个节点。规则按照第一节介绍

然后申请空间，接在树后面

注意：这里需要引用，原因本文最后进行讨论。

构造方法：

每次读取一个数

用插入的方法生成树

代码如下：

//插入函数
template <class T>
void BiSortTree<T>::Insert(BiNode<T>* &p, int k)	//p为根结点
{
	if (p == NULL)//根结点
	{
		p = new BiNode<T>;
		p->data = k;
		p->lchild = p->rchild = NULL;
	}
	else
	{
		if (k < p->data)		//比根结点小的插在左子树
			Insert(p->lchild, k);
		else if (k>p->data)		//比根结点大的插在左子树
			Insert(p->rchild, k);
	}
}

template <class T>
void BiSortTree<T>::Insert(int k)
{
	Insert(root,k);
}

//构造函数(多次调用插入函数)
template <class T>
BiSortTree<T>::BiSortTree(int a[], int n)
{
	root = NULL;
	for (int i = 0; i < n; i++)
		Insert(root,a[i]);
}

2.2、删除函数

传入节点为空，删除失败，返回
若不空，继续定位，查找值比当前节点小，查找其左子树，否则右子树

若定位成功，分三种情况删除

叶子节点 — 直接删除
单支节点 — 用孩子节点的值链接到当前节点，删除原节点

双支节点 — 考虑下二叉排序树的特点，即能想到，我要找的替代数字，应该是该节点左子树的最大孩子，也就是寻找左子树的最右孩子

//删除函数
template <class T>
void BiSortTree<T>::Delete(BiNode<T>* &p, int k)
{
	BiNode<T>* temp;
	if (p != NULL)
	{
		if (k < p->data)
			Delete(p->lchild, k);	//查找值k比当前值小，所以在其左子树找
		else if (k>p->data)
			Delete(p->rchild, k);	//查找值k比当前值大，所以在其右子树找
		else
		{
			if (p->lchild != NULL && p->rchild != NULL)  //双支节点
			{
				//寻找左子树的最右孩子
				temp = p->lchild;
				while (temp->rchild != NULL)
					temp = temp->rchild;
				p->data = temp->data;
				Delete(p->lchild, temp->data);
			}
			else
			{
				temp = p;
				if (p->lchild == NULL)
					p = p->rchild;
				else if (p->rchild == NULL)
					p = p->lchild;
				delete temp;
			}
		}
	}
}
template <class T>
void BiSortTree<T>::Delete(int k)
{
	Delete(root, k);
}

###2.3、查找函数
查找过程类似插入过程：

二叉树为空，查找失败，
查找值小于当前节点的值，递归查找左子树

查找值大于当前节点的值，递归查找右子树

//查找函数
template <class T>
BiNode<int>* BiSortTree<T>::Search(BiNode<T>* p, int k)	//查找值为k的结点
{
	if (p == NULL)	//递归出口
		return NULL;
	else if (p->data == k)
		return p;
	else if (k < p->data)
		return Search(p->lchild, k);
	else
		return Search(p->rchild, k);
}

template <class T>
void BiSortTree<T>::Search(int k)
{
	if (Search(root, k)==NULL)
		cout << "未查找到" << endl;
	else
		cout << "查到为：" << Search(root, k)->data << endl;
}