二叉排序树（c/c++）_设计一个读入一串整数,然后构造二叉排序树,进行查找。

二叉排序树又称为二叉查找树，对树中任意一个结点来说，如果它的左子树不为空，那么左子树中的数一定小于该结点中的数，同理，非空右子树中的数一定大于该结点中的数。（也可以设置为左大右小）

查找

在二叉排序树中查找一个数的算法如下:

bTree* searchT(bTree* T, int key)
{
	if (T == NULL)
		return NULL;
	if (T->data == key)
		return T;
	else if (T->data < key)
		return searchT((T->rc, key);
	else
		return searchT(T->lc, key);
}
1
2
3
4
5
6
7
8
9
10
11

插入

如何构造一棵二叉排序树，可以通过插入一个个结点来实现，下面是在二叉树中插入结点的算法：

bool insertBtree(bTree* T, int ele)
{
	if (T == NULL)//空结点
	{
		T = new bTree;
		T->data = ele;
		T->lc = T->rc = NULL;
		return true;
	}
	bTree* f;
	bTree* temp = new bTree;
	while (T!=NULL&&T->data!=ele)
	{
		f = T;
		if (f->data < ele)
			f = f->rc;
		else(T->data > ele)
			f = f->lc;
	}
	if (f)
		return false;//树中已存在该数据
	temp->data = ele;
	temp->lc = temp->rc = NULL;
	if (ele > f->data)
		f->rc = temp;
	else
		f->lc = temp;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

删除

删除二叉树结点a
1，若a为叶子结点，直接删除
2，若a只有一个子树，用其子树代替其位置
3，若a有两个子树，有一个比较好用的方法：因为二叉树中任何一个结点及其子树的排序结果都为左-根-右，它符合中序遍历的顺序，故如果要删除a，可以用中序遍历中a的直接前驱代替a或者用a的直接后继代替a。