二叉排序树C语言实现

#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define maxlen 100 

typedef int Status;	


typedef  struct Node	
{
	int data;	
	struct BiTNode* lchild, * rchild;	
} Node, * Tree;

int search_tree(Tree T, int key, Tree father, Tree* get)
{
	if (!T)
	{
		*get = father;
		return 0;
	}
	else if(T->data == key)
	{
		*get = T;
		return 1;
	}
	else if(T->data >key)
	{
		search_tree(T->lchild, key, T, get);
	}
	else
	{
		search_tree(T->rchild, key, T, get);
	}
}

int insert(Tree* T, int value)
{
	Tree p, s;
	if (!search_tree(*T, value, NULL, &p))
	{
		s = (Tree)malloc(sizeof(Node));
		s->lchild = NULL;
		s->rchild = NULL;
		s->data = value;
		if (!p)
		{
			*T = s;
		}
		else if(value>p->data)
		{
			p->rchild = s;
		}
		else
		{
			p->lchild = s;
		}
		return 1;
	}
	else
	{
		return 0;
	}
}



int delete_node(Tree *T, int key)
{
	if (!*T)
	{
		return 0;
	}
	else
	{
		if ((*T)->data == key)
		{
			delet(T);
		}
		else if((*T)->data > key)
		{
			delete_node(&(*T)->lchild, key);
		}
		else
		{
			delete_node(&(*T)->rchild, key);
		}
		return 1;
	}
}

int insert1(Tree* T, int value)
{
	Tree p, s;
	if (*T == NULL)  //根节点
	{
		*T= (Tree)malloc(sizeof(Node));
		(*T)->data = value;
		(*T)->lchild = NULL;
		(*T)->rchild = NULL;
	}
	else if(value < (*T)->data)
	{

		if ((*T)->lchild == NULL)   //如果没有左孩子，直接将值赋给左孩子
		{
			p = (Tree)malloc(sizeof(Node));  //这已经给他的左右孩子分配了内存地址，所以要将他的左右孩子只想NULL
			p->lchild = NULL;
			p->rchild = NULL;
			p->data = value;
			(*T)->lchild = p;
			return 1;
		}


		else
		{
			insert1(&((*T)->lchild), value);
		}

	}

	else if(value > (*T)->data)
	{
		if ((*T)->rchild == NULL)   //如果没有左孩子，直接将值赋给左孩子
		{
			s = (Tree)malloc(sizeof(Node));
			   //这已经给他的左右孩子分配了内存地址，所以要将他的左右孩子只想NULL
			s->lchild = NULL;
			s->rchild = NULL;

			s->data = value;
			(*T)->rchild = s;
			return 1;
		}


		else
		{
			insert1(&((*T)->rchild), value);
		}
	}
	else
	{
		return 0;
	}
	return 1;

}

int delet(Tree* T)
{
	Tree q, s;
	if ((*T)->lchild == NULL && (*T)->rchild == NULL)
	{
		*T = NULL;
		free(*T);
	}
	else if((*T)->lchild == NULL)
	{
		q = *T;
		*T = (*T)->rchild;
		free(q);
	}
	else if ((*T)->rchild == NULL)
	{
		q = *T;
		*T = (*T)->lchild;
		free(q);
	}
	else
	{
		q = *T;
		s = q->lchild;
		while (s->rchild)
		{
			q = s; //指向最终s的父母节点
			s = s->rchild;
		}
		(*T)->data = s->data;
		if(q!=*T)  //若T节点左子节点没有子右节点
			q->rchild = s->lchild;
		else
		{
			q->lchild = s->lchild;
		}
		free(s);

	}
	return 1;
}

int in_see(Tree T)
{
	if (!T)
	{
		return 0;
	}
	in_see(T->lchild);
	printf("%d ", T->data);
	in_see(T->rchild);
	return 1;
}

int main(void)
{
	int i;
	int a[10] = { 62,88,58,47,35,73,51,99,37,93 };
	Tree T = NULL;

	for (i = 0;i < 10;i++)
	{
		insert(&T, a[i]);
	}
	in_see(T);
	printf("n");
	delete_node(&T, 93);
	in_see(T);
	printf("n");
	delete_node(&T, 47);
	in_see(T);
	printf("n");
	return 0;
}