[网络协议]数据结构(8)_二叉搜索树

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 10

typedef struct TreeNode* BT;


typedef struct TreeNode* BinTree;
struct TreeNode
{
	int data;
	BinTree Left;
	BinTree Right;
};

//二叉搜索树 递归实现 查找指定元素所在结点地址
TreeNode* find(int elem, BinTree BT)
{
	if (BT == NULL)
		return NULL;
	if (elem > BT->data)
		return find(elem, BT->Right);
	else if (elem < BT->data)
		return find(elem, BT->Left);
	else
		return BT;
}
//非递实现
TreeNode* find2(int elem, BinTree BT)
{
	while (BT!=NULL)
	{
		if (elem > BT->data)
			BT = BT->Right;
		else if (elem < BT->data)
			BT = BT->Left;
		else
			return BT;
	}
	return NULL;
}

//如插入35，与30比较，要插入其右子树，。。。最后要把35插入到33的右子树，而其右子树为空，
//所以这里最后要建一个新结点，并且递归的返回值应为当前子树的根节点
BinTree insertNode(int elem, BinTree &BT)
{
	if (BT == NULL)
	{
		BT = (BinTree)malloc(sizeof(TreeNode));
		BT->data = elem;
		BT->Left = NULL;
		BT->Right = NULL;
	}
	else
	{
		if (elem < BT->data)
			BT->Left = insertNode(elem, BT->Left);//倒数第二步左子树为空时，在最后一步malloc新结点并赋给这个空结点
		else if (elem > BT->data)
			BT->Right = insertNode(elem, BT->Right);
		//else
		//	return NULL;//与已有值相等时跳过
	}
	return BT;
}

//二叉搜索树的最大元素在最右分支的端结点上
TreeNode* findMax(BinTree BT)
{
	if (BT->Right == NULL)
		return BT;
	else
		return  findMax(BT->Right);
}

TreeNode* findMin(BinTree BT)
{
	if (BT->Left == NULL)
		return BT;
	else
		return  findMin(BT->Left);
}


BinTree deleteNode(int elem, BinTree BT)
{
	TreeNode* temp;
	if (BT == NULL)//遍历到空也没找到
		printf("not found\n");
	else if (elem < BT->data)//要删的元素在左子树
		BT->Left = deleteNode(elem, BT->Left);
	else if (elem > BT->data)//or右子树
		BT->Right = deleteNode(elem, BT->Right);
	else//找到要删除元素位置
	{
		if (BT->Left && BT->Right)//要删除的元素有两个子树--把左子树的最大元素or右子树的最小元素作为删除位置的替补
		{
			temp = findMin(BT->Right);
			BT->data = temp->data;
			BT->Right = deleteNode(BT->data, BT->Right);
			free(temp);
		}
		else//要删除元素只有一个子树--把这个子树挂在删除位置即可
		{
			temp = BT;
			if (BT->Left == NULL)
				BT = BT->Right;
			else if (BT->Right == NULL)
				BT = BT->Left;
			free(temp);
		}
	}
	return BT;
}


int main() 
{
	BinTree BT;
	BT = NULL;//别忘了初始化！！！否则插入时会引起异常

	insertNode(30, BT);
	insertNode(37, BT);
	insertNode(28, BT);
	insertNode(39, BT);

	if (find(28, BT) == NULL)
		printf("null\n");
	else
		printf("%d\n", find(28, BT)->data);

	BT = deleteNode(28, BT);

	if (find(28, BT) == NULL)
		printf("null\n");
	else
		printf("%d\n", find(28, BT)->data);


	return 0;
}