二叉検索ツリー(C言語実装)

/*
 *          ，      、       
 *
 */

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

typedef struct node
{
	int count;  //           
	int data;   //  
    struct node * left;
	struct node * right;
}Node,*PNode;


int array[100];  //          
int k=0;         //  array  

//          
PNode init()
{
	PNode p=(PNode)malloc(sizeof(Node));
	p->count=0;
	p->left=p->right=NULL;
	return p;
}

//    
void insert(PNode root ,int data)
{
	if(root!=NULL&&root->count==0){//           count 0
		 root->data=data;
		 root->count++;
		 return;
	}
	if(data<root->data&&root->left==NULL){
        PNode p=(PNode)malloc(sizeof(Node));
    	p->data=data;
     	p->count=1;
    	p->left=p->right=NULL;
		root->left=p;
		return;
	}
	if(data>root->data&&root->right==NULL){
        PNode p=(PNode)malloc(sizeof(Node));
    	p->data=data;
     	p->count=1;
    	p->left=p->right=NULL;
		root->right=p;
		return;
	}
	if(data>root->data)
		insert(root->right,data);
	else if(data<root->data)
		insert(root->left,data);
	else{
		root->count++;
		return;
	}
}

//    ,      1，    0
int deleteNode(PNode* root ,int data)
{
	PNode p,q;
	//        
	if(*root==NULL)
		return 0;
	if((*root)->data==data){//        
		//           ，    
		if((*root)->left==NULL && (*root)->right==NULL){
            p=*root;
			*root=NULL;
			free(p);
			return 1;
		}
		//               ,                   
		if((*root)->left==NULL || (*root)->right==NULL){
            p=*root;
			*root=(*root)->left==NULL?(*root)->right:(*root)->left;
			p->left=p->right=NULL;
			free(p);
			return 1;
		}
		//              。                ，  
		//                 ，      。           
		if((*root)->left && (*root)->right){
            p=*root;
            *root=(*root)->left;
			q=*root;
			while(q->right)
				q=q->right;
            q->right=p->right;
			p->left=p->right=NULL;
			free(p);
			return 1;
		}
	}else if((*root)->data>data){
        deleteNode(&(*root)->left,data);
	}else
        deleteNode(&(*root)->right,data);
    return 0;
}

//    
void  search_middle(PNode root)
{

	int i=0;
    if(root==NULL)
		return; 
	search_middle(root->left);  
	for(;i<root->count;i++)
		array[k++]=root->data;
    search_middle(root->right);
}

//    
void  search_prior(PNode root)
{

	int i=0;
    if(root==NULL)
		return; 
	for(;i<root->count;i++)
		array[k++]=root->data;
	search_prior(root->left);  
    search_prior(root->right);
}

//    
void  search_last(PNode root)
{

	int i=0;
    if(root==NULL)
		return; 
	search_prior(root->left);  
    search_prior(root->right);
	for(;i<root->count;i++)
		array[k++]=root->data;
}

//     
int tree_height(PNode root)
{
	int h1,h2;
	if(root!=NULL&&root->count==0)
		return 0;
	if(root==NULL)
		return 0;
	h1=1+tree_height(root->left);
	h2=1+tree_height(root->right);
	return h1>h2?h1:h2;
}

void main()
{
	int a[20];
	int *p=a;
	PNode pnode=init();
	int i,n,deleteElement;

	//             
	printf("please input n(n<20):
");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("enter an Integer number:
");
		scanf("%d",p++);
	}

	//               
	for(i=0;i<n;i++){
		insert(pnode,*(a+i));
	}
	search_middle(pnode);
	printf("
    %d
",tree_height(pnode)); 

	//          
	for(i=0;i<k;i++)
		printf("%-5d",array[i]);
	printf("
");
	

	//    
	printf("         ：
");
	scanf("%d",&deleteElement);
    deleteNode(&pnode,deleteElement);

	k=0;
	search_middle(pnode);
	printf("
   ：    %d
",tree_height(pnode)); 

	//          
	for(i=0;i<k;i++)
		printf("%-5d",array[i]);
	printf("
");

	free(pnode);
}