二叉排序树（言简意赅）

• 1. 特点
• 2. 操作

二叉排序树的特性
按中序遍历可以得到一个递增有序序列

构建过程，这个树是根据，所给点的顺序，进行比大小的。也就是说，根据所给点的顺序，进行插入，不会在树的中间插入，都是在树的尾部进行插入。当然，删除的话，可能会在中间删除

在这里说一下删除操作

1. 找到要删除的点
2. 判断当前点 是否 有 左子树（因为右子树，一定是删除点的左子树了，然后删除点的左子树，插入到右子树的根的左）

# include
# include

typedef int DataType;


typedef struct node {
	DataType data;
	struct node* lchild, * rchild;
}BSTNode, * BSTree;


void InsertBST(BSTree* bst, DataType data) {
	BSTree s;
	if (*bst == NULL) {
		s = (BSTree)malloc(sizeof(BSTNode));
		s->data = data;
		s->lchild = NULL;
		s->rchild = NULL;
		*bst = s;
	}
	else if (data < (*bst)->data)
		InsertBST(&((*bst)->lchild), data);		//将s插入左子树
	else if (data >= (*bst)->data)
		InsertBST(&((*bst)->rchild), data);		//将s插入左子树
}


void CreatBST(BSTree* bst) {
	DataType data;
	*bst = NULL;
	scanf("%d", &data);
	while (data != 0) {
		InsertBST(bst, data);
		scanf("%d", &data);
	}
}


void InOrder(BSTree bst) {
	if (bst != NULL) {
		InOrder(bst->lchild);
		printf("%d ", bst->data);
		InOrder(bst->rchild);
	}
}


BSTree SearchBST_recursion(BSTree bst, DataType data) {
	if (bst == NULL)
		return NULL;
	else if (bst->data == data) {
		printf("%d", bst->data);
		return bst;
	}
	else if (bst->data > data)
		return SearchBST_recursion(bst->lchild, data);	//在左子树继续查找
	else
		return SearchBST_recursion(bst->rchild, data);	//在右子树继续查找
}


BSTree SearchBST(BSTree bst, DataType data) {
	BSTree q;
	q = bst;
	while (q) {
		if (q->data == data) {
			printf("%d", q->data);
			return q;
		}
		if (q->data > data)
			q = q->lchild;						//查找左子树
		else
			q = q->rchild;						//查找右子树
	}
	return NULL;								//查找失败
}


void DelBST(BSTree bst, DataType data) {
	BSTNode* p, * f, * s, * q;
	p = bst;
	f = NULL;
	while (p) {									//查找值为data的待删除结点	
		if (p->data == data)
			break;
		f = p;									//f指向p结点的双亲结点
		if (p->data > data)
			p = p->lchild;						//查找左子树
		else
			p = p->rchild;						//查找右子树
	}
	if (p == NULL)
		return bst;
	if (p->lchild == NULL) {				//若待删除结点p无左子树
		if (f == NULL)							//若p为原二叉排序树的根
			bst = p->rchild;
		else if (f->lchild == p)				//若p为f的左孩子
			f->lchild = p->rchild;
		else									//若p为f的右孩子
			f->rchild = p->rchild;
		free(p);
	}
	else {									//若待删除结点p有左子树
		q = p;
		s = p->lchild;
		while (s->rchild) {						//在p的左子树中查找最右下结点
			q = s;
			s = s->rchild;
		}
		if (q == p)								//结点s无右子树
			q->lchild = s->lchild;
		else
			q->rchild = s->lchild;
		p->data = s->data;
		free(s);
	}
	return bst;
}

int main() {
	BSTree bst;
	CreatBST(&bst);
	printf("中序遍历输出：");
	InOrder(bst);
	printf("n递归查找结果：");
	SearchBST_recursion(bst, 12);
	printf("n非递归查找结果：");
	SearchBST(bst, 12);
	DelBST(bst, 24);
	printf("n删除值为24的结点后中序遍历输出：");
	InOrder(bst);
	return 0;
}