本文共 4796 字，大约阅读时间需要 15 分钟。

二叉排序树相对于线性表的存储结构可以提高搜索的效率，是基于折半查找的思想而设计的一种数据结构，最好的情况下，二叉排序树操作的时间复杂度仅为O(logN)。

二叉排序树的特点：树中任意节点X应满足如下条件，X的左子树中每个节点的关键码均应该小于节点X的关键码，而X右子树中每个节点的关键码均应该大于节点X的关键码。

因为如此的设计原则，二叉搜索树中所存储的关键码是不允许重复的。如果需要考虑数据重复的情况，可以单独建立一个线性表，储存重复的数据和该数据出现的次数。但这种方法也比较局限。下面代码不考虑二叉排序树的重复问题。

#define _CRT_SECURE_NO_WARNINGS#include 
   
    #include 
    
     typedef struct Node{
   	int data;	struct Node* left;	struct Node* right;}Node_t, *pNode_t;void Insert_Node(pNode_t* ppbstnode, int value);      //二叉排序树的插入void Delete_Node(pNode_t* ppbstnode, int value);      //二叉排序树的删除pNode_t Find_Node_value(pNode_t pbstnode, int value); //寻找二叉排序树的valuepNode_t Find_Max_Node_value(pNode_t pbstnode);        //返回二叉排序树最大Key值的节点pNode_t Find_Min_Node_value(pNode_t pbstnode);        //返回二叉排序树最小Key值的节点void Delete_Min_Node(pNode_t* ppbstnode);             //删除二叉排序树最小Key值的节点void PreOrder(pNode_t pbstnode);                      //二叉排序树的前序遍历void MidOrder(pNode_t pbstnode);					  //二叉排序树的中序遍历void LatOrder(pNode_t pbstnode);					  //二叉排序树的后续遍历int BSTtree_Height(pNode_t pbstnode);                 //求二叉排序树的高度int main(){
   	int num;	pNode_t proot = NULL;	while (scanf("%d", &num) != EOF)	{
   		Insert_Node(&proot, num);	}	PreOrder(proot);	putchar('\n');	Delete_Node(&proot, 5);	PreOrder(proot);	//printf("%d \n", BSTtree_Height(proot));	return 0;}void Insert_Node(pNode_t* ppbstnode, int value){
   	pNode_t pnew = (pNode_t)calloc(1, sizeof(Node_t));	pnew->data = value;	if (NULL == *ppbstnode)	{
   		*ppbstnode = pnew;	}	else if (value < (*ppbstnode)->data)	{
   		if ((*ppbstnode)->left == NULL)		{
   			(*ppbstnode)->left = pnew;		}		else {
   			Insert_Node(&((*ppbstnode)->left), value);		}	}	else if (value > (*ppbstnode)->data)	{
   		if ((*ppbstnode)->right == NULL)		{
   			(*ppbstnode)->right = pnew;		}		else {
   			Insert_Node(&((*ppbstnode)->right), value);		}	}	else	{
   		printf("ERROR, Duplicate Element.\n");		return;	}	return;}//备注：一种错误的写法，在函数内部对函数内部变量pnode的改变并不能影响*ppbstnode指向的值//void Insert_Node(pNode_t* ppbstnode, int value)//{
   //	pNode_t pnode = *ppbstnode;//	pNode_t pnew = (pNode_t)calloc(1, sizeof(Node_t));//	pnew->data = value;//	if (NULL == pnode)//	{
   //		pnode = pnew;//	}//	else if (value < pnode->data)//	{
   //		if (pnode->left == NULL)//		{
   //			pnode->left = pnew;//		}//		else {
   //			Insert_Node(&(pnode->left), value);//		}//	}//	else if (value > pnode->data)//	{
   //		if (pnode->right == NULL)//		{
   //			pnode->right = pnew;//		}//		else {
   //			Insert_Node(&(pnode->right), value);//		}//	}//	else//	{
   //		printf("ERROR, Duplicate Element.\n");//		return;//	}//	return;//}void Delete_Node(pNode_t* ppbstnode, int value){
   	if (NULL == *ppbstnode)	{
   		printf("This bstnode is not exist.\n");		return;	}	else if (value < (*ppbstnode)->data)	{
   		Delete_Node(&(*ppbstnode)->left, value);	}	else if (value > (*ppbstnode)->data)	{
   		Delete_Node(&(*ppbstnode)->right, value);	}	else if ((*ppbstnode)->left != NULL && (*ppbstnode)->right != NULL)	{
   		(*ppbstnode)->data = Find_Min_Node_value((*ppbstnode)->right)->data;	}	else	{
   		pNode_t tmp = (*ppbstnode);		(*ppbstnode) = ((*ppbstnode)->left != NULL) ? (*ppbstnode)->left : (*ppbstnode)->right;		free(tmp);	}}pNode_t Find_Node_value(pNode_t pbstnode, int value){
   	while (pbstnode)	{
   		if (value == pbstnode->data)		{
   			return pbstnode;		}		else if (value < pbstnode->data)		{
   			pbstnode = pbstnode->left;		}		else if (value > pbstnode->data)		{
   			pbstnode = pbstnode->right;		}		else		{
   			printf("Not Find this value.\n");			return NULL;		}	}}pNode_t Find_Max_Node_value(pNode_t pbstnode){
   	while (pbstnode->right)	{
   		pbstnode = pbstnode->right;	}	return pbstnode;}pNode_t Find_Min_Node_value(pNode_t pbstnode){
   	while (pbstnode->left)	{
   		pbstnode = pbstnode->left;	}	return pbstnode;}void Delete_Min_Node(pNode_t* ppbstnode){
   	if ((*ppbstnode) == NULL)	{
   		printf("Empty Tree.\n");		return;	}	else if ((*ppbstnode)->left != NULL)	{
   		Delete_Min_Node(&(*ppbstnode)->left);	}	else if ((*ppbstnode)->left == NULL)	{
   		pNode_t tmp = (*ppbstnode);		(*ppbstnode) = (*ppbstnode)->right;		free(tmp);	}}void PreOrder(pNode_t pbstnode){
   	if (pbstnode)	{
   		printf("%d ", pbstnode->data);		PreOrder(pbstnode->left);		PreOrder(pbstnode->right);	}}void MidOrder(pNode_t pbstnode){
   	if (pbstnode)	{
   		MidOrder(pbstnode->left);		printf("%d ", pbstnode->data);		MidOrder(pbstnode->right);	}}void LatOrder(pNode_t pbstnode){
   	if (pbstnode)	{
   		LatOrder(pbstnode->left);		LatOrder(pbstnode->right);		printf("%d ", pbstnode->data);	}}int BSTtree_Height(pNode_t pbstnode){
   	int LD = 0;	int RD = 0;	if (pbstnode == NULL)	{
   		return 0;	}	else	{
   		LD = BSTtree_Height(pbstnode->left);		RD = BSTtree_Height(pbstnode->right);		return (LD > RD ? LD : RD) + 1;	}}
    
   

转载地址：http://pxxmb.baihongyu.com/