二叉树排序树上实现学生信息管理

问题：树中结点结构：成绩 lchild rchild head 
链表中的结点结构：学号 姓名 next 
功能：1.按成绩查询 
      2.插入一个新学生信息 
      3.删除一个学生信息 
      4.按成绩排序(高到低) 

答案：

#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() 
{  
char s[100], 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; 
}