二叉搜索树的相关操作

/二叉搜索树是一棵二叉树，可以为空，如果不为空，有如下的性质
//（1）非空左子树的所有键值小于其根结点的键值
//（2）非空右子树的所有键值大于其根结点的键值
//（3）左右子树都是二叉搜索树

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
struct TNode {
	ElemType data;
	struct TNode *left;
	struct TNode *right;
}; 
typedef TNode *BT;

BT CreateBinTree() {
	BT T;
	ElemType ch;
	cin >> ch;
	if (ch == 0)
		T = NULL;//到叶节点之后，其左右儿子的值赋值为0
	else {
		T = (BT)malloc(sizeof(TNode));
		T->data = ch;
		T->left = CreateBinTree();
		T->right = CreateBinTree();
	}
	return T;
}

//二叉搜索树查找元素（递归）
BT Findx_inBST(BT BST, ElemType x) {
	if (!BST) return NULL;
	if (BST->data < x)
		Findx_inBST(BST->right, x);
	else if (BST->data > x)
		Findx_inBST(BST->left, x);
	else
		return BST;
}

//二叉搜索树查找元素（非递归）
BT Findx_inBST2(BT BST, ElemType x) {
	if (!BST) return NULL;
	while (BST) {
		if (BST->data < x)
			BST = BST->right;
		else if (BST->data > x)
			BST = BST->left;
		else
			break;
	}
	return BST;
}

//递归方式查找二叉搜索树的最大值
//二叉搜索树最大值的查找
//树为空直接返回；不为空，就到右子树去找，直到右子树为空，返回其父节点
BT Findmax_inBST(BT BST) {
	if (!BST) return NULL;
	else if (!BST->right) return BST;
	else return Findmax_inBST(BST->right);
}

//非递归方式查找
BT Findmax_inBST2(BT BST) {
	if (!BST) return NULL;
	while (BST->right) BST = BST->right;
	return BST;
}

//递归方式查找二叉搜索树的最小值
BT Findmin_inBST(BT BST) {
	if (!BST) return NULL;
	else if (!BST->left) return BST;
	else return Findmax_inBST(BST->left);
}

//非递归方式查找
BT Findmin_inBST2(BT BST) {
	if (!BST) return NULL;
	while (BST->left) BST = BST->left;
	return BST;
}

/二叉搜索树的插入，与find类似
BT InsertXtoBST(BT BST, ElemType x) {
	if (!BST) {
		BST = (BT)malloc(sizeof(TNode));
		BST->data = x;
		BST->left = BST->right = NULL;

	}
	if (BST->data > x)
		BST->left = InsertXtoBST(BST->left, x);
	else if (BST->data < x)
		BST->right = InsertXtoBST(BST->right, x);
	return BST;
}

//二叉搜索树的删除
//（1）删除的是叶节点
//（2）删除的节点只有一个孩子
//（3）删除的节点有两个孩子。此时，可以取左子树的最大值，或右子树的最小值。
BT Deletex_inBST(BT BST, ElemType x) {
	if (!BST) {
		printf("树为空，无法删除");
		return BST;
	}
	BT temp;
	if (BST->data > x) BST->left = Deletex_inBST(BST->left, x);
	else if (BST->data < x) BST->right = Deletex_inBST(BST->right, x);
	else {
		if (BST->left&&BST->right) {
			temp = Findmax_inBST2(BST->right);
			BST->data = temp->data;
			BST->right = Deletex_inBST(BST->right, x);
		}
		else {
			temp = BST;
			if (BST->left == NULL) BST = BST->right;
			else BST = BST->left;
			free(temp);
		}
	}
	return BST;
}

// 中序遍历(递归)
void InOrderTraversal(BT BT) {
	if (BT) {
		InOrderTraversal(BT->left);
		printf("%d ", BT->data);
		InOrderTraversal(BT->right);
	}
}

// 先序遍历(递归)
void PreOrderTraversal(BT BT) {
	if (BT) {
		printf("%d ", BT->data);
		PreOrderTraversal(BT->left);
		PreOrderTraversal(BT->right);
	}
}

int main(int argc, char *argv[]) {
	// 创建一棵二叉树	
	BT T = CreateBinTree();
	printf("二叉搜索树创建成功, 现在输出先序遍历的结果:");
	PreOrderTraversal(T);
	printf("\n");
	printf("二叉搜索树创建成功, 现在输出中序遍历的结果:");
	InOrderTraversal(T);
	printf("\n\n");

	BT resTNode;
	printf("【1】使用递归方式查找数字 7 是否在二叉搜索树中  : ");
	if (Findx_inBST(T, 7)) {
		printf("YES \n");
		resTNode = Findx_inBST(T, 7);
		printf("	 用FindX_inBST的结果显示一下数字 7 : %d\n\n", resTNode->data);
	}
	else {
		printf("NO \n\n");
	}

	printf("【2】使用非递归方式查找数字 5 是否在二叉搜索树中 : ");
	if (Findx_inBST2(T, 5)) {
		printf("YES \n\n");
		resTNode = Findx_inBST2(T, 5);
		printf("	 用FindX_inBST_的结果显示一下数字 5 : %d\n\n", resTNode->data);
	}
	else {
		printf("NO\n\n");
	}

	resTNode = Findmax_inBST(T);
	printf("【3】使用递归方式找到该二叉搜索树的最大值为   : %d\n", resTNode->data);
	resTNode = Findmax_inBST2(T);
	printf("【4】使用非递归方式找到该二叉搜索树的最大值为 : %d\n\n", resTNode->data);

	resTNode = Findmin_inBST(T);
	printf("【5】使用递归方式找到该二叉搜索树的最小值为   : %d\n", resTNode->data);
	resTNode = Findmin_inBST2(T);
	printf("【6】使用非递归方式找到该二叉搜索树的最小值为 : %d\n\n", resTNode->data);

	printf("【7】将数字 35 插入该二叉搜索树中 : \n");
	resTNode = InsertXtoBST(T, 35);
	printf("     成功插入数字 35, 现在输出先序遍历的结果:");
	PreOrderTraversal(resTNode);
	printf("\n");
	printf("     成功插入数字 35, 现在输出中序遍历的结果:");
	InOrderTraversal(resTNode);
	printf("\n\n");

	printf("【8】将数字 6 插入空树中 : ");
	BT T1 = CreateBinTree();
	resTNode = InsertXtoBST(T1, 6);
	printf("     成功插入数字 6, 现在输出先序遍历的结果:");
	PreOrderTraversal(resTNode);
	printf("\n");
	printf("     成功插入数字 6, 现在输出中序遍历的结果:");
	InOrderTraversal(resTNode);
	printf("\n\n");

	printf("【9】将数字 33 从该二叉搜索树中删除 : \n");
	resTNode = Deletex_inBST(T, 33);
	printf("     成功删除数字 33, 现在输出先序遍历的结果:");
	PreOrderTraversal(resTNode);
	printf("\n");
	printf("     成功删除数字 33, 现在输出中序遍历的结果:");
	InOrderTraversal(resTNode);
	printf("\n\n");

	system("pause");
	return 0;
}