采用二叉树存储结构，利用预置数组建立二叉树；实现对通讯录的查找，基于查找实现对同学录的修改和新增成员；求所要操作节点的父节点，从而顺利地编写对同学录的删除操作。

/*采用二叉树存储结构，
利用预置数组建立二叉树；
实现对通讯录的查找，
基于查找实现对同学录的修改
和新增成员；
求所要操作节点的父节点，
从而顺利地编写对同学录的删除操作。
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M 100
#define len sizeof(Student)
/*定义一个学生类型的结构体 sizeof(Student)
所用的空间的大小赋值给变量len*/

typedef struct stu{
int number; //号码
char name[M]; //姓名
char sex[M]; //性别
char phone[M]; //电话
struct stu*left,*right; //左子树 右子树
}Student;

Student *Stu;

//初始化
void init(){
Stu==NULL;
}
//添加元素
Student *Add(int num,char n[],char s[],char p[],Student*root){
if(root==NULL){ // 判断根节点是否有人，没有人则执行插入操作
root=(Student*)malloc(len);
root->number=num;
strcpy(root->name,n);
strcpy(root->sex,s);
strcpy(root->phone,p);
root->left=NULL;
root->right=NULL;
}
else{ //如果根结点有人
if(num<root->number){ //如果插入的学号比根结点的学号小，则放在左孩子结点
root->left=Add(num,n,s,p,root->left);
} //插入的学号比根节点的学号要大，则放在右孩子结点
else if(num>root->number){
root->right=Add(num,n,s,p,root->right);
}
else if(num=root->number){
printf("插入结点失败，插入失败的结点是%s\n:",num,root->name);
}
}
return root; //插入失败时候，返回根结点
}
/*--------------------------------------1:显示原来的预置数组里同学的信息-------*/
//显示前序遍历的结果
void PerOrderTraverse(Student *Ptrl){
if(Ptrl!=NULL){
printf("\t%3d\t",Ptrl->number);
printf("\t%3s\t",Ptrl->name);
printf("\t%3s\t",Ptrl->sex);
printf("\t%3s\t",Ptrl->phone);
printf("\n");
PerOrderTraverse(Ptrl->left);
PerOrderTraverse(Ptrl->right);

}
}
//中序遍历
void InOrderTraverse(Student *Ptrl){
if(Ptrl!=NULL){
PerOrderTraverse(Ptrl->left);
printf("\t%3d\t",Ptrl->number);
printf("\t%3s\t",Ptrl->name);
printf("\t%3s\t",Ptrl->sex);
printf("\t%3s\t",Ptrl->phone);
printf("\n");
PerOrderTraverse(Ptrl->right);
}
}
//后序遍历
void PostOrderTraverse(Student*Ptrl){
if(Ptrl!=NULL){
PerOrderTraverse(Ptrl->left);
PerOrderTraverse(Ptrl->right);
printf("\t%3d\t",Ptrl->number);
printf("\t%3s\t",Ptrl->name);
printf("\t%3s\t",Ptrl->sex);
printf("\t%3s\t",Ptrl->phone);
}
}
/*--------------------------------------2:查找同学的信息--------------------*/
void SearchInformationByNum(Student *T,int num){ //按照学号进行查找
if (T != NULL)
{
SearchInformationByNum(T->left,num);
if(T->number==num)
{
printf("\t%d\t", T->number);
printf("%s\t", T->name);
printf("%s\t", T->sex);
printf("%s\n", T->phone);
}
SearchInformationByNum(T->right,num);
}
}

void SearchInformationByName(Student* T,char n[]) //按照名字查找 遍历查找
{
if (T != NULL)
{
SearchInformationByName(T->left,n);
/*strcmp函数比较两个字符串，
str1<str2 返回的值是0
str=str2 返回的值是负数
str1>str2 返回的值是正数
*/
if(strcmp(T->name,n) == 0)
{
printf("\t%d\t", T->number);
printf("%s\t", T->name);
printf("%s\t", T->sex);
printf("%s\n", T->phone);
}
SearchInformationByName(T->right,n);
}
}

void SearchInformationBySex(Student*T,char s[]){ //按照性别进行查找
if (T != NULL)
{
SearchInformationBySex(T->left,s);
if(strcmp(T->sex,s) == 0){
printf("\t%d\t", T->number);
printf("%s\t", T->name);
printf("%s\t", T->sex);
printf("%s\n", T->phone);
}
SearchInformationBySex(T->right,s);
}
}

void SearchInformationByPhone(Student*T,char p[]){ //按照电话号码进行查找
if(T!=NULL){
SearchInformationByPhone(T->left,p);
if(strcmp(T->phone,p)==0){
printf("\t%d\t",T->number);
printf("\t%s\t",T->name);
printf("\t%s\t",T->sex);
printf("\t%s\n",T->phone);
}
SearchInformationByPhone(T->right,p);
}
}

Student *FindMin(Student *s){
if(!s){ //空的二叉树，返回NULL
return NULL;
}
else{
if(!s->left)
return s; //找到最左叶的结点并返回
else{
return FindMin(s->left); //沿着左分支继续查找
}
}
}

/*---------------------------3:修改同学的信息------------------------------------------*/
void ModifyInformationByNum(Student *T,int num){
int k;
if (T != NULL){
ModifyInformationByNum(T->left,num);
if(T->number==num){
printf("\t%d\t", T->number);
printf("%s\t", T->name);
printf("%s\t", T->sex);
printf("%s\n", T->phone);
while(1){
printf("\n\n");
printf(" 1: 姓名\n");
printf(" 2: 性别\n");
printf(" 3: 电话\n");
printf("显示修改后的信息并且退出本次的循环\n");
scanf("%d",&k);
switch(k){
case 1:{
char name[M];
printf("请输入名字:");
scanf("%s",&name);
strcpy(T->name,name);
}break;
case 2:{
char sex[M];
printf("请输入性别:");
scanf("%s",&sex);
strcpy(T->sex,sex);
}break;
case 3:{
char phone[M];
printf("请输入新号码:");
scanf("%s",phone);
strcpy(T->phone,phone);
}break;
case 0:{
printf("\t学号\t姓名\t性别\t电话\n");
printf("\t%d\t",T->number);
printf("%s\t",T->name);
printf("%s\t",T->sex);
printf("%s\n",T->phone);
printf("\n");
goto temp;
}
default:break;
}
}
}
temp: ModifyInformationByNum(T->right,num);
}
}

void ModifyInformationByName(Student *T,char n[]){
int k;
if (T != NULL){
ModifyInformationByName(T->left,n);
if(strcmp(T->name,n) == 0){
printf("\t%d\t", T->number);
printf("%s\t", T->name);
printf("%s\t", T->sex);
printf("%s\n", T->phone);
while(1){
printf("\n\n");
printf(" 1: 姓名\n");
printf(" 2: 性别\n");
printf(" 3: 电话\n");
printf("显示修改后的信息并且退出本次的循环\n");
scanf("%d",&k);
switch(k){
case 1:{
char n[M];
printf("请输入名字:");
scanf("%s",&n);
strcpy(T->name,n);
}break;
case 2:{
char sex[M];
printf("请输入性别:");
scanf("%s",&sex);
strcpy(T->sex,sex);
}break;
case 3:{
char phone[M];
printf("请输入新号码:");
scanf("%s",phone);
strcpy(T->phone,phone);
}break;
case 0:{
printf("\t学号\t姓名\t性别\t电话\n");
printf("\t%d\t",T->number);
printf("%s\t",T->name);
printf("%s\t",T->sex);
printf("%s\n",T->phone);
printf("\n");
goto temp;
}
default:break;
}
}
}
temp: ModifyInformationByName(T->right,n);
}
}

void ModifyInformationBySex(Student *T,char sex[]){
int k;
if (T != NULL){
ModifyInformationBySex(T->left,sex);
if(strcmp(T->sex,sex) == 0){
printf("\t%d\t", T->number);
printf("%s\t", T->name);
printf("%s\t", T->sex);
printf("%s\n", T->phone);
while(1){
printf("\n\n");
printf(" 1: 姓名\n");
printf(" 2: 性别\n");
printf(" 3: 电话\n");
printf("显示修改后的信息并且退出本次的循环\n");
scanf("%d",&k);
switch(k){
case 1:{
char name[M];
printf("请输入名字:");
scanf("%s",&name);
strcpy(T->name,name);
}break;
case 2:{
char sex[M];
printf("请输入性别:");
scanf("%s",&sex);
strcpy(T->sex,sex);
}break;
case 3:{
char phone[M];
printf("请输入新号码:");
scanf("%s",phone);
strcpy(T->phone,phone);
}break;
case 0:{
printf("\t学号\t姓名\t性别\t电话\n");
printf("\t%d\t",T->number);
printf("%s\t",T->name);
printf("%s\t",T->sex);
printf("%s\n",T->phone);
printf("\n");
goto temp;
}
default:break;
}
}
}
temp: ModifyInformationBySex(T->right,sex);
}
}

void ModifyInformationByPhone(Student *T,char p[]){
int k;
if (T != NULL){
ModifyInformationByPhone(T->left,p);
if(strcmp(T->phone,p) == 0){
printf("\t%d\t", T->number);
printf("%s\t", T->name);
printf("%s\t", T->sex);
printf("%s\n", T->phone);
while(1){
printf("\n(\t1:姓名,\t2:性别 \t3:联系电话 \t 0:显示修改后的信息并退出本次修改\n");
scanf("%d",&k);
switch(k){
case 1:{
char name[M];
printf("请输入名字:");
scanf("%s",&name);
strcpy(T->name,name);
}break;
case 2:{
char sex[M];
printf("请输入性别:");
scanf("%s",&sex);
strcpy(T->sex,sex);
}break;
case 3:{
char phone[M];
printf("请输入新号码:");
scanf("%s",phone);
strcpy(T->phone,phone);
}break;
case 0:{
printf("\t学号\t姓名\t性别\t电话\n");
printf("\t%d\t",T->number);
printf("%s\t",T->name);
printf("%s\t",T->sex);
printf("%s\n",T->phone);
printf("\n");
goto temp;
}
default:break;
}
}
}
temp: ModifyInformationByPhone(T->right,p);
}
}
/*------------------------------删除操作----------------------------------------------*/
void DeleteInformationByName(Student *T,Student *PRT, char n[]){ //采用递归的方式进行遍历删除
if(T!=NULL){ //当遍历的根结点不为空指针时
DeleteInformationByName(T->left,T,n);
if(strcmp(T->name,n)==0){
if(T->left&&T->right){ //同时拥有左子树和右子树
Student *student = FindMin(T->left);
T->number= student->number;
strcpy(T->name,student->name);
strcpy(T->sex,student->sex);
strcpy(T->phone,student->phone);
DeleteInformationByName(T->right,T,student->name);
}
else{
if(PRT == NULL){
if(T->left !=NULL){
T = T->left;
}
else{
T = T->right;
}
}
else{
if(T == PRT->left){
if(T->left != NULL){ //有右孩子结点无子结点
PRT->left = T->left;
}
else{
PRT->left = T->right;
}
}
else{
if(T->left!= NULL){
PRT->right = T->left;
}
else{
PRT->right = T->right;
}
}
}
}
}
DeleteInformationByName(T->right,T,n);
}
}

void DeleteInformationByPhone(Student *T,Student *PRT, char p[]){ //采用递归的方式进行遍历删除
if(T!=NULL){ //当遍历的根结点不为空指针时
DeleteInformationByPhone(T->left,T,p);
if(strcmp(T->phone,p)==0){
if(T->left&&T->right){ //同时拥有左子树和右子树
Student *student = FindMin(T->left);
T->number= student->number;
strcpy(T->name,student->name);
strcpy(T->sex,student->sex);
strcpy(T->phone,student->phone);
DeleteInformationByPhone(T->right,T,student->phone);
}
else{
if(PRT == NULL){
if(T->left !=NULL){
T = T->left;
}
else{
T = T->right;
}
}
else{
if(T == PRT->left){
if(T->left != NULL){
PRT->left = T->left;
}
else{
PRT->left = T->right;
}
}
else{
if(T->left!= NULL){
PRT->right = T->left;
}
else{
PRT->right = T->right;
}
}
}
}
}
DeleteInformationByPhone(T->right,T,p);
}
}

/*----------------------------------视图层---------------------------------*/
Student *menu(Student *Stu){
printf("\t 同学录管理系统\n");
printf(" ---------------------------------------------------------\n");
printf("\t 1:显示原来的预置数组里同学的信息 \n\n");
printf("\t 2:查找同学的信息 \n\n");
printf("\t 3:修改同学录信息 \n\n");
printf("\t 4:添加新同学信息 \n\n");
printf("\t 5:删除同学录信息 \n\n");
printf("\t 6:退出该系统\n\n");
printf(" ----------------------------------------------------------\n");
printf("\t选择您要进行的操作前的序号(1~6):");
}
Student *showInformation(Student *Stu){
printf("\n\n");
printf("\t 显示原来的预置数组里同学的信息 \n");
printf(" ----------------------------------------------------------\n");
printf("\t (1)先序遍历预置数组里同学的信息\n");printf("\n");
printf("\t (2)中序遍历预置数组里同学的信息\n");printf("\n");
printf("\t (3)后序遍历预置数组里同学的信息\n");printf("\n");
printf("\t (0)返回主菜单\n");
printf(" ----------------------------------------------------------\n");

}
Student *SearchInformation(Student *Stu){
printf("\n\n");
printf("\t 查找同学的信息 \n");
printf(" ----------------------------------------------------------\n");
printf("\t (1)按照学号查找同学的信息\n");printf("\n");
printf("\t (2)按照姓名查找同学的信息\n");printf("\n");
printf("\t (3)按照性别查找同学的信息\n");printf("\n");
printf("\t (4)按照电话查找同学的信息\n");printf("\n");
printf("\t (0)返回主菜单\n");
printf(" ----------------------------------------------------------\n");

}
Student *ModifyInformation(Student *Stu){
printf("\n\n");
printf("\t 修改同学的信息 \n");
printf(" ----------------------------------------------------------\n");
printf("\t (1)根据学号做为索引修改同学的信息\n");printf("\n");
printf("\t (2)根据姓名作为索引修改同学的信息\n");printf("\n");
printf("\t (3)根据电话做为索引修改同学的信息\n");printf("\n");
printf("\t (0)返回主菜单\n");
printf(" ----------------------------------------------------------\n");

}
Student *DeleteInformation(Student *Stu){
printf("\n\n");
printf("\t 删除同学的信息 \n");
printf(" ----------------------------------------------------------\n");
printf("\t (1)根据姓名做为索引删除同学的信息\n");printf("\n");
printf("\t (2)根据电话删做为索引除同学的信息\n");printf("\n");
printf("\t (0)返回主菜单\n");
printf(" ----------------------------------------------------------\n");
}

//打印函数
void print(Student*Stu){
printf("\t学号\t\t姓名\t\t性别\t\t电话\n");
}

//测试函数
int main(){
int a;
void init();
if(Stu==NULL){
// printf("初始化工作完成\n\n");
}
//预置数组的信息
Stu=Add(1,"Bob","male","15538569845",Stu);
Stu=Add(2,"lisi","female","13846825852",Stu);
Stu=Add(3,"yang","male","18837235685",Stu);
l:
while(1)
{
int n;
menu(Stu); //主菜单
scanf("%d",&n);
switch(n)
{
case 1:{ //显示操作
system("cls");
showInformation(Stu);
while(1)
{
printf("\t请输入你的选择(0~3):");
scanf(" %d",&a);
switch(a){
case 1:print(Stu);PerOrderTraverse(Stu);break; //先序遍历二叉树
case 2:print(Stu);InOrderTraverse(Stu);break; //中序遍历二叉树
case 3:print(Stu);PostOrderTraverse(Stu);break; //后序遍历二叉树
case 0:goto l;break;
default :break;
}
}
}break;

case 2:{
system("cls");
SearchInformation(Stu); //2：查找菜单函数
while(1)
{
printf("请输入你的选择(0-4):");
scanf(" %d",&a);
switch(a){

case 1:{
int num;
printf("请输入要查找的同学学号:");
scanf("%d",&num);
print(Stu);
SearchInformationByNum(Stu,num); //按照学号进行查找
printf("\n");
}break;
case 2:{
char name[M];
printf("请输入要查找的同学名字:"); //按照同学的姓名进行查找
scanf("%s",&name);
print(Stu);
SearchInformationByName(Stu,name);
printf("\n");
}break;
case 3:{
char sex[M];
Student *ptr=(Student*)malloc(len);
printf("请输入要查找的同学的性别:"); //按照性别进行查找
scanf("%s",&sex);
print(Stu);
SearchInformationBySex(Stu,sex);
printf("\n");
}break;
case 4:{
char phone[M];
printf("请输入要查找的同学的电话:");
scanf("%s",&phone);
print(Stu);
SearchInformationByPhone(Stu,phone);
printf("\n");
}break;
case 0:goto l;break;
default :break;
}
}
}break;

//修改操作
case 3:{
system("cls");
ModifyInformation(Stu); //修改操作
while(1)
{
printf("\t请输入你的选择(0~4):");
scanf("%d",&a);
switch(a){
case 1:{
int num;
printf("\t请输入要修改的同学的学号:"); //按照同学的姓名进行查找
scanf("%d",&num);
print(Stu);
ModifyInformationByNum(Stu,num);
printf("\n");
}break;

case 2:{
char name[M];
printf("\t请输入要修改的同学的名字:"); //按照同学的姓名进行修改
scanf("%s",&name);
//Student *ptr = (Student *)malloc(len);
print(Stu);
ModifyInformationByName(Stu,name);
printf("\n");
}break;
case 3:{
char sex[M];
printf("\t请输入要修改的同学的性别:"); //按照同学的姓名进行修改
scanf("%s",&sex);
//Student *ptr = (Student *)malloc(len);
print(Stu);
ModifyInformationByName(Stu,sex);
printf("\n");
}break;
case 4:{
char phone[M];
//Student *ptr=(Student*)malloc(len);
printf("\t请输入要修改的同学的电话号码:"); //按照性别进行修改
scanf("%s",&phone);
print(Stu);
ModifyInformationByPhone(Stu,phone);
printf("\n");
}break;
case 0:goto l;break;
default :break;
}
}
}break;

//4:添加新的结点信息
case 4:{
system("cls");
int addnumber;
char addname[M];
char addsex[M];
char addphone[M];
printf("\t ---------------添加操作!---------\n\n");
printf("请依次录入同学的\n\t学号\t姓名\t性别\t电话\n");
scanf("%d",&addnumber);
scanf("%s",&addname);
scanf("%s",&addsex);
scanf("%s",&addphone);
Stu=Add(addnumber,addname,addsex,addphone,Stu);
}break;

//删除操作
case 5:{
system("cls");
DeleteInformation(Stu); //删除操作
while(1)
{
printf("请输入你的选择(0~2):");
scanf("%d",&a);
switch(a){
case 1:{
char name[M];
Student *ptr=(Student*)malloc(len);
printf("请输入要删除的同学的姓名:"); //按照姓名进行删除
scanf("%s",&name);
DeleteInformationByName(Stu,NULL,name);
printf("\n");
}break;
case 2:{
char phone[M];
Student *ptr=(Student*)malloc(len);
printf("请输入要删除的同学的电话:"); //按照姓名进行删除
scanf("%s",&phone);
DeleteInformationByPhone(Stu,NULL,phone);
printf("\n");
}break;
case 0:goto l;break;
default :break;
}
}
}break;
}
}
}

利用二叉树设计同学录管理系统