一种二叉搜索树实现

今天尝试使用C语言实现一颗二叉搜索树（Binary Search Tree），发现其中最复杂的是Delete过程，说他复杂并不是其过程难以理解，而是需要用到递归，尤其是当递归函数需要返回值时，不知道中间递归（相对于尾递归而言）该如何使用，于是自己又重新梳理一下递归，总算将其搞明白了，为了防止遗忘，故写下此文。

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

struct BTNode {
	int data;
	struct BTNode *lchild;
	struct BTNode *rchild;
};

struct BTNode *insert(struct BTNode *T,int n)
{
	if(T == NULL)
	{
		T = malloc(sizeof(struct BTNode));
		if(T == NULL)
		{
			printf("Error: out of memory!!\n");
			return NULL;
		}
		else
		{
			T->data = n;
			T->lchild = T->rchild = NULL;
		}
	}
	else
	{	
		if(n < T->data)
			T->lchild = insert(T->lchild,n);
		else if(n > T->data)
			T->rchild = insert(T->rchild,n);
	}
	return T;
}

struct BTNode *find(struct BTNode *T,int n)
{
	if(T == NULL)
		return NULL;
	if(T->data == n)
		return T;
	else if(n < T->data)
		return find(T->lchild,n);
	else
		return find(T->rchild,n);
}

struct BTNode *findMin(struct BTNode *T)
{
	if(T == NULL)
	{
		printf("this is a empty tree\n");
		return NULL;
	}
	while(T->lchild != NULL)
		T = T->lchild;
	return T;
}

struct BTNode *findMax(struct BTNode *T)
{
	if(T == NULL)
	{
		printf("this is a empty tree\n");
		return NULL;
	}
	while(T->rchild != NULL)
		T = T->rchild;
	return T;
}

struct BTNode *delete(struct BTNode *T,int n)
{
	struct BTNode *temp;
	if(T == NULL)
	{
		return NULL;
	}
	if(n < T->data)
		T->lchild = delete(T->lchild,n);
	else if(n > T->data)
		T->rchild = delete(T->rchild,n);
	else {
		if(T->lchild && T->rchild)
		{
			temp = findMin(T->rchild);
			T->data = temp->data;
			T->rchild = delete(T->rchild,temp->data);
		}
		else
		{
			temp = T;
			if(T->lchild == NULL && T->rchild == NULL)
				T = NULL;
			else if(T->lchild == NULL)
				T = T->rchild;
			else
				T = T->lchild;
			free(temp);
		}
	}
	return T;
}

void print_preorder(struct BTNode *T)
{
	if(T == NULL)
		return;
	printf("\t%d\t",T->data);
	print_preorder(T->lchild);
	print_preorder(T->rchild);
	return;
}

void print_midorder(struct BTNode *T)
{
	if(T == NULL)
		return;
	print_midorder(T->lchild);
	printf("\t%d\t",T->data);
	print_midorder(T->rchild);
	return;
}

void print_postorder(struct BTNode *T)
{
	if(T == NULL)
		return;
	print_postorder(T->lchild);
	print_postorder(T->rchild);
	printf("\t%d\t",T->data);
	return;
}

int main(void)
{
	struct BTNode *T = NULL;
	T = insert(T,10);
	T = insert(T,8);
	T = insert(T,16);
	T = insert(T,11);
	T = insert(T,13);
	T = insert(T,18);

	printf("当前树的前序遍历为：");
	print_preorder(T);
	printf("\n");

	printf("当前树的中序遍历为：");
	print_midorder(T);
	printf("\n");

	printf("当前树的后序遍历为：");
	print_postorder(T);
	printf("\n");

	struct BTNode *position;
	position = find(T,15);
	if(position == NULL)
		printf("15 not found in current tree\n");
	else
		printf("%d is in current tree\n",position->data);
	
	position = findMin(T);
	printf("%d is Min value in current tree\n",position->data);

	position = findMax(T);
	printf("%d is Max value in current tree\n",position->data);

	printf("---------------start to delete 10------------------\n");
	position = delete(T,10);

	printf("---------------after delete 10---------------------\n");
	printf("当前树的前序遍历为：");
	print_preorder(T);
	printf("\n");

	printf("当前树的中序遍历为：");
	print_midorder(T);
	printf("\n");

	printf("当前树的后序遍历为：");
	print_postorder(T);
	printf("\n");
	
	return 0;
}

运行结果如下：