二叉排序树算法

  1 #include "stdio.h"
  2 #include "string.h"
  3 #include "malloc.h"
  4 
  5 struct Student{
  6     char Stu_Number[20];//学号
  7     char Stu_Name[10];//姓名
  8     char Stu_Bedroom[10];//房间号
  9 };
 10 
 11 struct Student student[100];
 12 int Num ;//用于统计总个数
 13 
 14 //输入数据
 15 void Create(){
 16     struct Student temp;
 17     int Continue;
 18     Num = 0;//数据个数初始为0
 19     while(1 ){
 20         printf("输入一个学生信息:
");
 21         printf("学号:");
 22         scanf("%s",&temp.Stu_Number);
 23         printf("姓名:");
 24         scanf("%s",&temp.Stu_Name);
 25         printf("房间号:");
 26         scanf("%s",&temp.Stu_Bedroom);
 27         student[Num++] = temp;
 28         printf("
");
 29         printf("继续|(1:Y,0:N):");
 30         scanf("%d",&Continue);
 31         while(Continue!=1&&Continue!=0)
 32         {
 33             printf("请输入0|1:");
 34             scanf("%d",&Continue);
 35         }
 36         if(Continue==0)
 37         {
 38             printf("数据输入结束!
");
 39             break;
 40         }
 41     }
 42 }
 43 
 44 
 45  struct Bnode{
 46      struct Student student;
 47      Bnode *lchild;
 48      Bnode *rchild;
 49 };
 50 
 51 /*
 52 *将指针S所指的结点插入到二叉排序树T中  关键字(房号+学号)
 53 */
 54 void RoomNum_Number_insert( Bnode * &Tree, Bnode *S)
 55 {
 56     if(Tree==NULL)//若插入到空树时，插入结点为根结点
 57     {
 58         Tree = S;
 59     }else if(strcmp(S->student.Stu_Bedroom,Tree->student.Stu_Bedroom)<0){    
 60         RoomNum_Number_insert(Tree->lchild,S);//插入到Tree的左子树中
 61     }else if(strcmp(S->student.Stu_Bedroom,Tree->student.Stu_Bedroom)>0){
 62         RoomNum_Number_insert(Tree->rchild,S);//插入到Tree的右子树中
 63     }else if(strcmp(S->student.Stu_Bedroom,Tree->student.Stu_Bedroom)==0)//房号相同的情况下 再比较学号
 64     {
 65         if(strcmp(S->student.Stu_Number,Tree->student.Stu_Number)<0)
 66         {
 67             RoomNum_Number_insert(Tree->lchild,S);//插入到Tree的左子树中
 68         }else RoomNum_Number_insert(Tree->rchild,S);//插入到Tree的右子树中
 69     }
 70 }
 71 
 72 
 73 /*
 74 *二叉排序树的构造  关键字(房号+学号)
 75 */
 76 void RoomNum_Number_Create_bst(Bnode *&Tree)
 77 {
 78     int i=0;
 79     Tree = NULL;
 80     Student x;
 81     while(i<Num)
 82     {
 83         x = student[i];
 84         Bnode *u;
 85         u = ( Bnode *)malloc(sizeof(Bnode));//分配存储区域
 86         u->student = x;
 87         u->lchild = NULL;
 88         u->rchild = NULL;
 89         RoomNum_Number_insert(Tree,u);
 90         i++;
 91     }
 92     printf("二叉排序树构造完毕!
");
 93 }
 94 
 95 
 96 /*
 97 *查找某个房间号的所有人 关键字(房号+学号)
 98 */
 99 void Room_Num_inorder(Bnode *Tree,char temp[])
100 {
101     if(Tree!=NULL)
102     {
103         Room_Num_inorder(Tree->lchild,temp);
104         if (strcmp(Tree->student.Stu_Bedroom,temp)==0)
105         {
106             printf("房号:%s 学号:%s 姓名:%s
",Tree->student.Stu_Bedroom,Tree->student.Stu_Number,Tree->student.Stu_Name);
107         }
108         Room_Num_inorder(Tree->rchild,temp);
109     }
110 }
111 
112 
113 /*
114 *将指针S所指的结点插入到二叉排序树T中  关键字(姓名+学号)
115 */
116 void Name_Number_insert(Bnode * &Tree,Bnode *S)
117 {
118     if(Tree==NULL)//插入到空树时，插入结点为根结点
119     {
120         Tree = S;
121     }else if(strcmp(S->student.Stu_Name,Tree->student.Stu_Name)<0){    
122         Name_Number_insert(Tree->lchild,S);//插入到Tree的左子树中
123     }else if(strcmp(S->student.Stu_Name,Tree->student.Stu_Name)>0){
124         Name_Number_insert(Tree->rchild,S);//插入到Tree的右子树中
125     }else if(strcmp(S->student.Stu_Name,Tree->student.Stu_Name)==0)//房号相同的情况下 再比较学号
126     {
127         if(strcmp(S->student.Stu_Number,Tree->student.Stu_Number)<0)
128         {
129             Name_Number_insert(Tree->lchild,S);//插入到Tree的左子树中
130         }else Name_Number_insert(Tree->rchild,S);//插入到Tree的右子树中
131     }
132 }
133 
134 
135 /*
136 *二叉排序树的构造  关键字(姓名+学号)
137 */
138 void Name_Number_Create_bst(Bnode *&Tree)
139 {
140     int i=0;
141     Tree = NULL;
142     Student temp;
143     while(i<Num)
144     {
145         temp = student[i];
146         Bnode *u;
147         u = (Bnode *)malloc(sizeof(Bnode));//分配存储区域
148         u->student = temp;
149         u->lchild = NULL;
150         u->rchild = NULL;
151         Name_Number_insert(Tree,u);
152         i++;
153     }
154     printf("二叉排序树构造完毕!
");
155 }
156 
157 
158 /*
159 *查找同名的所有人 关键字(姓名+学号)
160 */
161 void Name_Num_inorder(Bnode *Tree,char temp[])
162 {
163     if(Tree!=NULL)
164     {
165         Name_Num_inorder(Tree->lchild,temp);
166         if (strcmp(Tree->student.Stu_Name,temp)==0)
167         {
168             printf("姓名:%s 学号:%s 房号:%s
",Tree->student.Stu_Name,Tree->student.Stu_Number,Tree->student.Stu_Bedroom);
169         }
170         Name_Num_inorder(Tree->rchild,temp);
171     }
172 }
173 
174 
175 /*
176 *中序输出二叉排序树
177 */
178 void inorder(Bnode *Tree)
179 {
180     if(Tree!=NULL)
181     {
182         inorder(Tree->lchild);
183         printf("房号:%s 学号:%s 姓名:%s
",Tree->student.Stu_Bedroom,Tree->student.Stu_Number,Tree->student.Stu_Name);
184         inorder(Tree->rchild);
185     }
186 }
187 
188 
189 int main()
190 {
191 
192     Bnode *Tree_Room_Number;
193     Tree_Room_Number = (Bnode *)malloc(sizeof(Bnode));//分配存储区域
194     Bnode *Tree_Name_Number;
195     Tree_Name_Number = (Bnode *)malloc(sizeof(Bnode));//分配存储区域
196 
197     int Continue;
198     char name[20],room[20];
199     while(1)
200     {
201         printf(" ------------------菜单---------------------
");
202         printf("|-----1:数据输入----------------------------|
");
203         printf("|-----2:二叉排序树(房号+学号)---------------|
");
204         printf("|-----3:查找同房号所有人--------------------|
");
205         printf("|-----4:二叉排序树(姓名+学号)---------------|
");
206         printf("|-----5:姓名查找同名的所有人----------------|
");
207         printf("|-----6:二叉排序树中序输出------------------|
");
208         printf(" -------------------------------------------
");
209         
210         printf("请选择菜单:");
211         scanf("%d",&Continue);
212         while(Continue!=1&&Continue!=2&&Continue!=3&&Continue!=4&&Continue!=5&&Continue!=6)
213         {
214             printf("请输入1|2|3|4|5|6:");
215             scanf("%d",&Continue);
216         }
217         switch(Continue)
218         {
219         case 1:
220             Create();
221             break;
222         case 2:
223             RoomNum_Number_Create_bst(Tree_Room_Number);//创建二叉排序树  关键字(房号+学号)
224             break;
225         case 3:
226             printf("输入房间号:");
227             scanf("%s",&room);
228             Room_Num_inorder(Tree_Room_Number,room);
229             break;
230         case 4:
231             Name_Number_Create_bst(Tree_Name_Number);//创建二叉排序树  关键字(姓名+学号)
232             break;
233         case 5:
234             printf("输入姓名:");
235             scanf("%s",&name);
236             Name_Num_inorder(Tree_Name_Number,name);
237             break;
238         case 6:
239             printf(" ------------查看(中序输出)-----------
");
240             printf("|-----1:二叉排序树(房号+学号)--------|
");
241             printf("|-----0:二叉排序树(姓名+学号)--------|
");
242             printf(" ------------------------------------
");
243             printf("请选择:");
244             scanf("%d",&Continue);
245             while(Continue!=1&&Continue!=0)
246             {
247                 printf("输入有误，请输入0|1:");
248                 scanf("%d",&Continue);
249             }
250             if(Continue==1) inorder(Tree_Room_Number);
251             else inorder(Tree_Name_Number);
252             break;
253         }
254         printf("
1:主菜单,0:退出  :");
255         scanf("%d",&Continue);
256         while(Continue!=1&&Continue!=0)
257         {
258             printf("输入有误，请输入0|1:");
259             scanf("%d",&Continue);
260         }
261         if(Continue==0)break;
262     }
263     return 0;
264 }

宿舍管理查询软件（限2 人完成）
任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：
1) 输入数据，要求输入学号，姓名，房号。
2) 建立一棵二叉排序树。关键字（房号+学号)
3）输入房号找到此房间的所有人，打印房号、学号、姓名
4）建立一棵二叉排序树。关键字（姓名+学号)
5）输入姓名找到同名的所有人，打印姓名、学号、房号

  1 #include <iostream>
  2 #include <string>
  3 using namespace std;
  4 
  5 enum error{rangeerror,overflow,underflow,success};
  6 
  7 struct Infor{
  8     string Number;//学号
  9     string Name;//姓名
 10     int Room_Num;//房间号
 11 };
 12 
 13 struct node{
 14     Infor data;
 15     node *next;
 16 };
 17 
 18 class list{
 19 public:
 20     list();
 21     int length() const;//求长度的函数
 22     int get_int(const int i ,Infor & x)const;//按序号取元素运算函数
 23     void  create();//创建链表
 24 private:
 25     int count;
 26     node * head;
 27 };
 28 
 29 /*
 30 *初始化对应的构造函数
 31 */
 32 list::list(){
 33     head =new node;
 34     head->next=NULL;
 35     count=0;
 36 }
 37 
 38 /*
 39 *求长度
 40 */
 41 int list::length() const{
 42     return count;
 43 }
 44 
 45 
 46 /*
 47 *创建链表,输入数据
 48 */
 49 void list::create(){
 50     Infor Data;
 51     bool flags = true;//是否继续输入数据标识
 52     int select;
 53     node * rear=head;
 54     while(flags ){
 55         cout<<"请输入一组数据:"<<endl;
 56         cout<<"学号:";
 57         cin>>Data.Number;
 58         cout<<"姓名:";
 59         cin>>Data.Name;
 60         cout<<"房间号:";
 61         cin>>Data.Room_Num;
 62         cout<<endl;
 63         count++;
 64         node *s=new node;
 65         s->data=Data;
 66         rear->next=s;
 67         rear=s;
 68         rear->next=NULL;
 69 
 70         cout<<"继续输入数据?|(1:继续,0不继续):";
 71         cin>>select;
 72         while(select!=1&&select!=0)
 73         {
 74             cout<<"输入有误，请输入0|1:";
 75             cin>>select;
 76         }
 77         if(select==0)
 78         {
 79             flags = false;
 80             cout<<"数据输入完毕!"<<endl;
 81         }
 82     }
 83 }
 84 
 85 /*
 86 *按序号取元素
 87 */
 88 int list::get_int(const int i,Infor &x)const{
 89     node *p=new node;
 90     p=head->next;
 91     int j=1;
 92     while(p!=NULL&&j!=i){//当前节点不是目标节点，并且不空时就继续搜索
 93         p=p->next;
 94         j++;
 95     }
 96     if(p==NULL)return rangeerror;
 97     else {
 98         x=p->data;
 99         return success;
100     }
101 }
102 
103 struct Bnode{
104     Infor data;
105     Bnode *lchild;
106     Bnode *rchild;
107 };
108 
109 
110 //---------------------关键字(房号+学号)-------------------
111 /*
112 *将指针S所指的结点插入到二叉排序树T中  关键字(房号+学号)
113 */
114 void RoomNum_Number_insert(Bnode * &Tree,Bnode *S)
115 {
116     if(Tree==NULL)//插入到空树时，插入结点为根结点
117     {
118         Tree = S;
119     }else if(S->data.Room_Num<Tree->data.Room_Num){    
120         RoomNum_Number_insert(Tree->lchild,S);//插入到Tree的左子树中
121     }else if(S->data.Room_Num>Tree->data.Room_Num){
122         RoomNum_Number_insert(Tree->rchild,S);//插入到Tree的右子树中
123     }else if(S->data.Room_Num==Tree->data.Room_Num)//房号相同的情况下 再比较学号
124     {
125         if(S->data.Number<Tree->data.Number)
126         {
127             RoomNum_Number_insert(Tree->lchild,S);//插入到Tree的左子树中
128         }else RoomNum_Number_insert(Tree->rchild,S);//插入到Tree的右子树中
129     }
130 }
131 
132 /*
133 *二叉排序树的构造  关键字(房号+学号)
134 */
135 void RoomNum_Number_Create_bst(list A,Bnode *&Tree)
136 {
137     int i=0;
138     Tree = NULL;
139     Infor x;
140     while(i<A.length())
141     {
142         A.get_int(i+1,x);
143         Bnode *u = new Bnode;
144         u->data = x;
145         u->lchild = NULL;
146         u->rchild = NULL;
147         RoomNum_Number_insert(Tree,u);
148         i++;
149     }
150     cout<<"二叉排序树构造完毕!"<<endl;
151 }
152 
153 /*
154 *查找某个房间号的所有人 关键字(房号+学号)
155 */
156 void Room_Num_inorder(Bnode *Tree,int x)
157 {
158     if(Tree!=NULL)
159     {
160         Room_Num_inorder(Tree->lchild,x);
161         if (Tree->data.Room_Num == x)
162         {
163             cout<<"房号:"<<Tree->data.Room_Num <<" 学号:"<<Tree->data.Number<<" 姓名:"<<Tree->data.Name<<endl;
164         }
165         Room_Num_inorder(Tree->rchild,x);
166     }
167 }
168 
169 //---------------------关键字(房号+学号)-------------------
170 
171 
172 
173 //---------------------关键字(姓名+学号)-------------------
174 /*
175 *将指针S所指的结点插入到二叉排序树T中  关键字(姓名+学号)
176 */
177 void Name_Number_insert(Bnode * &Tree,Bnode *S)
178 {
179     if(Tree==NULL)//插入到空树时，插入结点为根结点
180     {
181         Tree = S;
182     }else if(S->data.Name<Tree->data.Name){    
183         Name_Number_insert(Tree->lchild,S);//插入到Tree的左子树中
184     }else if(S->data.Name>Tree->data.Name){
185         Name_Number_insert(Tree->rchild,S);//插入到Tree的右子树中
186     }else if(S->data.Name==Tree->data.Name)//房号相同的情况下 再比较学号
187     {
188         if(S->data.Number<Tree->data.Number)
189         {
190             Name_Number_insert(Tree->lchild,S);//插入到Tree的左子树中
191         }else Name_Number_insert(Tree->rchild,S);//插入到Tree的右子树中
192     }
193 }
194 
195 /*
196 *二叉排序树的构造  关键字(姓名+学号)
197 */
198 void Name_Number_Create_bst(list A,Bnode *&Tree)
199 {
200     int i=0;
201     Tree = NULL;
202     Infor x;
203     while(i<A.length())
204     {
205         A.get_int(i+1,x);
206         Bnode *u = new Bnode;
207         u->data = x;
208         u->lchild = NULL;
209         u->rchild = NULL;
210         Name_Number_insert(Tree,u);
211         i++;
212     }
213     cout<<"二叉排序树构造完毕!"<<endl;
214 }
215 
216 /*
217 *查找同名的所有人 关键字(姓名+学号)
218 */
219 void Name_Num_inorder(Bnode *Tree,string x)
220 {
221     if(Tree!=NULL)
222     {
223         Name_Num_inorder(Tree->lchild,x);
224         if (Tree->data.Name == x)
225         {
226             cout<<"姓名:"<<Tree->data.Name<<" 学号:"<<Tree->data.Number<<" 房号:"<<Tree->data.Room_Num<<endl;
227         }
228         Name_Num_inorder(Tree->rchild,x);
229     }
230 }
231 
232 //---------------------关键字(姓名+学号)-------------------
233 
234 
235 /*
236 *中序输出
237 */
238 void inorder(Bnode *Tree)
239 {
240     if(Tree!=NULL)
241     {
242         inorder(Tree->lchild);
243         cout<<"房号:"<<Tree->data.Room_Num <<" 学号:"<<Tree->data.Number<<" 姓名:"<<Tree->data.Name<<endl;
244         inorder(Tree->rchild);
245     }
246 }
247 
248 
249 int main()
250 {
251 
252     Bnode *Room_Number_Tree =new Bnode;
253     Bnode *Name_Number_Tree =new Bnode;
254     list A;
255     int room,select;
256     string name;
257     bool flags = true;
258     while(flags)
259     {
260         cout<<" ------------------菜单---------------------
";
261         cout<<"|-----1:输入数据----------------------------|
";
262         cout<<"|-----2:建立二叉排序树(房号+学号)-----------|
";
263         cout<<"|-----3:输入房号查找同房号所有人------------|
";
264         cout<<"|-----4:建立二叉排序树(姓名+学号)-----------|
";
265         cout<<"|-----5:输入姓名查找同名的所有人------------|
";
266         cout<<"|-----6:二叉排序树中序输出------------------|
";
267         cout<<" -------------------------------------------
";
268         cout<<"提示:"<<endl;
269         cout<<"      1.数据只需输入一遍即可
";
270         cout<<"      2.二叉排序树建立一遍即可
";
271         cout<<"      3.顺序:输入数据，建立二叉排序树，再查找
";
272         cout<<" -------------------------------------------
";
273         cout<<"请选择菜单:";
274         cin>>select;
275         while(select!=1&&select!=2&&select!=3&&select!=4&&select!=5&&select!=6)
276         {
277             cout<<"输入有误，请输入1|2|3|4|5|6:";
278             cin>>select;
279         }
280         switch(select)
281         {
282         case 1:
283             A.create();
284             break;
285         case 2:
286             RoomNum_Number_Create_bst(A,Room_Number_Tree);//创建二叉排序树  关键字(房号+学号)
287             break;
288         case 3:
289             cout<<"输入房间号:";
290             cin>>room;
291             Room_Num_inorder(Room_Number_Tree,room);
292             break;
293         case 4:
294             Name_Number_Create_bst(A,Name_Number_Tree);//创建二叉排序树  关键字(姓名+学号)
295             break;
296         case 5:
297             cout<<"输入姓名:";
298             cin>>name;
299             Name_Num_inorder(Name_Number_Tree,name);
300             break;
301         case 6:
302             cout<<" ------------查看(中序输出)-----------
";
303             cout<<"|-----1:二叉排序树(房号+学号)--------|
";
304             cout<<"|-----0:二叉排序树(姓名+学号)--------|
";
305             cout<<" ------------------------------------
";
306             cout<<"请选择:";
307             cin>>select;
308             while(select!=1&&select!=0)
309             {
310                 cout<<"输入有误，请输入0|1:";
311                 cin>>select;
312             }
313             if(select==1) inorder(Room_Number_Tree);
314             else inorder(Name_Number_Tree);
315             break;
316         }
317         cout<<"
1:返回菜单,0:退出  :";
318         cin>>select;
319         while(select!=1&&select!=0)
320         {
321             cout<<"输入有误，请输入0|1:";
322             cin>>select;
323         }
324         if(select==0)flags = false;
325     }
326     return 0;
327 }