二叉树程序.txt

本程序实现了二叉排序树的建立以及查找,插入和删除的功能.

#include<iostream.h>
#include<stdio.h>
#include<conio.h>

//******************************************
//define the structure of an element of a tree
//******************************************
struct tree {                          
	char info;                           
	struct tree *left,*right;            
};

//******************************************
//explanation the functions 
//******************************************
struct tree *create_btree(struct tree *root,struct tree *r,char info);
struct tree *search_btree(struct tree *root,char key);
struct tree *delete_node(struct tree *root,char key);
void  print_btree(struct tree *r,int l);
void PreOrder(struct tree *T);          //先序递归遍历二叉树
void InOrder(struct tree *T);           //中序递归遍历二叉树
void PostOrder(struct tree *T);  

//******************************************
// the main function 
//******************************************
void main()
{   
	int s[10], c,  e;                     
	struct tree *root=0, *p;       
	printf("Input a letter for Creating the Binary_Tree ( Directly press <Enter> to stop ):\n"); 
	do { 
		printf("\nInput a letter: "); 
		
		e=_getch();
		_putch(e);
		if(e==13) break;
		if (!root)
			root=create_btree(root,root,e);
		else
			create_btree(root,root,e);
		
		//		gets(s);
		//		if(s[0]==0) break;
		//		if (!root)
		//			root=create_btree(root,root,*s);
		//		else
		//			create_btree(root,root,*s);
		
	}  while (s) ;
	printf("\n先序遍历结果：");
	PreOrder(root);          //先序递归遍历二叉树
	printf("\n中序遍历结果：");
	InOrder(root);  
	printf("\n后序遍历结果：");       //中序递归遍历二叉树
	PostOrder(root);  
	printf("\n");
	while ( c!='!')  //查找
	{
		print_btree(root,0);
		printf("Enter a character to find( '!' to stop ):");
		scanf("%s",&c);
		printf("\n");
		p=search_btree(root,c);
	    printf("\n");
	}
	c='1';
	while ( c!='!')   //删除节点
	{
		print_btree(root,0);
		printf("Enter a character to delete( '!' to stop ):");
		scanf("%s",&c);
		printf("\n");
		root=delete_node(root,c);   //删除结点后返回树的根
	    printf("\n");
	}

}   /* Btree.C 结束  */ 

   

 
struct tree *create_btree(struct tree *root,struct tree *r,char info)
{  
	if (r ==0 )
	{   
		r=new (struct tree);
		if ( r == 0)
		{ 
			printf("Out of memory\n");   return 0 ; 
		}
		r->left= 0;  r->right=0;   r->info=info;
		if (root)
		{ 
			if(info<root->info)    root -> left=r;
			else                    
				root->right=r;
		}
		else
		{  
			r->right=0;   r->left = 0; 
		}
		return  r;
	}    
	if (info < r->info)
		create_btree(r,r->left,info);
	if(info>=r->info)
		create_btree(r,r->right,info);
	return root;
}    /*   create_btree(root,r,info)      */

//******************************************
//tree *search_btree(struct tree *root,char key)
//******************************************
struct tree *search_btree(struct tree *p,char key)
{   struct tree *root;
	root=p;
	if (!root)
	{  printf("Empty btree\n");   return root;  }                             
	while(root->info!=key)           
		{   if(key<root->info)          
				root=root->left;
			else
				root=root->right;
			if(root==0)
			{  printf("Search Failure\n");
               return 0;
			}
		}  /* while(root->info!=key)   */
	if (root !=0)
	printf("Successful search\n key=%c\n",root->info);
	return root ;
}  /*     *search_btree(root,key)     */


//************************************
// print_btree 
//************************************
void print_btree(struct tree *r,int l)

{    int i;
	if (r == 0) return ;
	print_btree(r->left,l+1);
	for(i=0;i<l;i++)	printf("  ");
	printf("%c\n",r->info);
	print_btree(r->right,l+1);
}   


void PreOrder(struct tree *T)
{
 if(T)
  {

   printf("%c",T->info);  //访问结点
   PreOrder(T->left);   //遍历左子树
   PreOrder(T->right);   //遍历右子树
  }
}
void InOrder(struct tree *T)
{if(T)
  {
   InOrder(T->left);   //遍历左子树 
   printf("%c",T->info); //访问结点
   InOrder(T->right);   //遍历右子树
  }
}
void PostOrder(struct tree *T)
{
 if(T)
  {
   PostOrder(T->left); //遍历左子树
   PostOrder(T->right); //访问结点
   printf("%c",T->info); //遍历右子树
  }
}
//************************************
// struct tree *delete_node(struct tree *root,char key)  
//************************************
struct tree *delete_node(struct tree *root,char key)  
{
	struct tree *p,*t,*parent;
	/*查找结点key并记录父结点指针   */
	parent=root;	
	p=root;
	if (!p)     //判断树是否为空
	{  
		printf("Empty btree\n");  
		return root;  
	}                             
	while(p->info!=key && p!=0)     //查找要删除的结点， 
	{   
		parent=p;	                  //同时保留其父结点的指针
		if(key<p->info)          
			p=p->left;
		else
			p=p->right;
		if(p==0)
		{  
			printf("Search Failure\n");
			return root;
		}
	} 
	printf("Search Successful\n");
	if(parent!=p)                      //要删除的结点不是根
	{
		if(p==parent->left)            //要删除的结点是父结点的左子
		{
			if(p->left!=0)              //要删除的结点的左子不空
			{
				
				parent->left=p->left;  //左孙升级为左子
				t=p->left;
				while(t->right!=0)    //找原左孙的右子树叶子
				{
					t=t->right;
				}
				t->right=p->right;
			}
			else                    //要删除的结点的左子空
			{
				parent->left=p->right;    
			}
		}
		
		if(p==parent->right)    //要删除的结点是父结点的右子       
		{
			if(p->left!=0)       //要删除的结点的左子不空
			{
				
				parent->right=p->left;
				t=p->left;
				while(t->right!=0)
				{
					t=t->right;
				}
				t->right=p->right;
			}
			else              //要删除的结点的左子空
			{
				parent->right=p->right;
			}
		}
		delete(p);
		return root;
	}
	
	else                    //要删除的结点是根
	{
		//root=p;
		if(p->left!=0)      //根有左子树
		{
			root=p->left;
			t=p->left;
			while(t->right!=0)
			{
				t=t->right;
			}
			t->right=p->right;
		}
		else         //根没有左子树
		{
			root=p->right;
		}
		delete(p);
		return root;
	}
	
}