데이터 구조 설정 - 찾기, 정렬, 파일 - 이 진 트 리 와 파일 작업

기능 요구: (1) 키보드 에서 학생 기록 을 입력 하여 이 진 트 리 를 만 듭 니 다.(2) * 두 갈래 정렬 트 리 메모리;(3) * 파일 에서 메모 리 를 복원 하 는 두 갈래 정렬 트 리;(4) 중간 순서 로 두 갈래 정렬 트 리 를 옮 겨 다 니 기;(5) 두 갈래 정렬 트 리 의 깊이 구하 기;(6) 이 진 트 리 의 모든 노드 수 와 잎 노드 수 를 구하 기;(7) 두 갈래 정렬 트 리 에 학생 기록 삽입 하기;(8) 두 갈래 정렬 트 리 에서 학생 기록 을 삭제 합 니 다.(9) 이 진 트 리 에서 학생 기록 을 조회 합 니 다.(10) 이 진 트 리 를 넓 은 의미 표 형식 으로 출력 합 니 다 / / 학생 기록 유형 을 정의 합 니 다 Struct student {Char num [6]; / 학호 Int grade; / 성적}; / /두 갈래 정렬 트 리 노드 값 의 유형 을 학생 기록 형식 type: def student ElemType 으로 정의 합 니 다. /두 갈래 정렬 트 리 의 노드 형식 type: def Struct BSTNode {ElemType data; Struct BSTNode * left; Struct BSTNode * rchild;} BSTNode;

#include 
#define FN "D:\\BST.txt"
//     
using namespace std;
typedef struct student
{
     
    char  num[6];  //  
    int   grade;   //  
} ElemType;
typedef struct BTnode
{
     
    ElemType data;
    BTnode *lchild,*rchild;
} BTnode,*BTtree;
ElemType a[105];
BTtree creatBTtree()
{
     
    BTtree bt=NULL;
    return bt;
}
int nodenum(BTtree T)//    
{
     
    int sum=0;
    if(!T)
    {
     
        return 0;
    }
    else
    {
     
        sum=1+nodenum(T->lchild)+nodenum(T->rchild);
    }
    return sum;
}
int leafnodenum(BTtree T)//    
{
     
    int sum=0;
    if(!T)
    {
     
        return 0;
    }
    else if((T->lchild==NULL)&&(T->rchild==NULL))
    {
     
        return 1;
    }
    else
    {
     
        return leafnodenum(T->lchild)+leafnodenum(T->rchild);
    }
    return sum;
}
void InOrderTraverseBTtree(BTtree T)//    
{
     
    if(T)
    {
     
        InOrderTraverseBTtree(T->lchild);
        printf("  :%s   :%d
",T->data.num,T->data.grade);
        InOrderTraverseBTtree(T->rchild);
    }
}
int Depth(BTtree T)
{
     
    if(!T)return 0;
    else
    {
     
        int m=Depth(T->lchild);
        int n=Depth(T->rchild);
        if(m>n){
     return m+1;}
        else{
     return n+1;}
    }
}

int SearchBST(BTtree T,char no[])//        
//T      ，e       ，f T    ，p                 
{
     
    queue<BTtree>q;
    q.push(T);
    while(!q.empty())
    {
     
        BTtree t=q.front();
        q.pop();
        if (strcmp((t->data.num),no)==0)
        {
     
            return t->data.grade;
        }
        if (t->lchild)
        {
     
            q.push(t->lchild);
        }
        if (t->rchild)
        {
     
            q.push(t->rchild);
        }
    }
    return 0;
}

int InsertBST(BTtree &T,char no[],int e)//    
{
     
    BTtree s=NULL,p,q=NULL;
    s=new BTnode;
    strcpy(s->data.num,no);
    s->data.grade=e;
    s->lchild=s->rchild=NULL;
    if(!T)//   
    {
     
        T=s;
        return 1;
    }
    if(SearchBST(T,no))//         
    {
     
        return 0;
    }
    p=T;
    while(p)
    {
     
        q=p;
        if(p->data.grade > e)//           
        {
     
            p=p->lchild;
        }
        else//           
        {
     
            p=p->rchild;
        }
    }
    if(q->data.grade>e)
    {
     
        q->lchild=s;
        return 1;
    }
    else
    {
     
        q->rchild=s;
        return 1;
    }
    return 0;
}


int Delete(BTtree *p)//         
{
     
    BTtree q,s;
    if((*p)->rchild==NULL)//    
    {
     
        q=*p;
        *p=(*p)->lchild;//      
        free(q);
    }
    else if((*p)->lchild==NULL)//    
    {
     
        q=*p;
        *p=(*p)->rchild;//      
        free(q);
    }
    else// ，      
    {
     
        q=*p;
        s=(*p)->lchild;
        while(s->rchild)
        {
     
            q=s;
            s=s->rchild;
        }
        (*p)->data=s->data;//           
        if(*p!=q)
        {
     
            q->rchild=s->lchild;
        }
        else
        {
     
            q->lchild=s->lchild;
        }
        free(s);
    }
    return 1;
}
int DeleteBST(BTtree *T,int e)//    
{
     
    if(!*T)
    {
     
        return -1;
    }
    else
    {
     
        if((*T)->data.grade==e)
        {
     
            return Delete(T);
        }
        else if(e<(*T)->data.grade)
        {
     
            return DeleteBST(&(*T)->lchild,e);
        }
        else
        {
     
            return DeleteBST(&(*T)->rchild,e);
        }
    }
}

int f_write(BTtree T)
{
     
    FILE *fp;
    if((fp=fopen(FN,"w+"))==NULL)
    {
     
        printf("fail open!
");
        return -1;
    }
    queue<BTtree>q;
    q.push(T);
    while(!q.empty())
    {
     
        BTtree t=q.front();
        q.pop();
        fprintf(fp,"%s %d
",t->data.num,t->data.grade);
        printf("%s %d
",t->data.num,t->data.grade);
        if (t->lchild)
        {
     
            q.push(t->lchild);
        }
        if (t->rchild)
        {
     
            q.push(t->rchild);
        }
    }
    cout<<"      ！"<<endl;
    fclose(fp);
    return 0;
}

int f_read(BTtree &T)
{
     
    FILE *fp;
    if((fp=fopen(FN,"r+"))==NULL)
    {
     
        printf("fail open!
");
        return -1;
    }
    int x;
    char str[6];
    while (!feof(fp))
    {
     
        fscanf(fp,"%s %d
",str,&x);
        //str[6]='\0';
        InsertBST(T,str,x);
    }
    cout<<"      ！"<<endl;
    fclose(fp);
    return 0;
}

void Put(BTtree T)//        
{
     
    if(T!=NULL)
    {
     
        //cout<
        cout<<T->data.num;
        if(T->lchild!=NULL||T->rchild!=NULL)
        {
     
            cout<<"(";
            Put(T->lchild);
            if(T->rchild!=NULL)
            {
     
                cout<<",";
            }
            Put(T->rchild);
            cout<<")";
        }
    }
}
/*
          :

a:      a,       

a(b):      a,    b,     

a(,c):      a,     ,    c

a(b,c)      a,            b c
*/

void menu()
{
     
    printf ("
1.                 
");
    printf ("2.       
");
    printf ("3.             
");
    printf ("4.         
");
    printf ("5.        
");
    printf ("6.                  
");
    printf ("7.              
");
    printf ("8.               
");
    printf ("9.               
");
    printf ("10.              

");
}


int main()
{
     
    printf("--------             --------
");
    BTtree T;
    T=creatBTtree();
    int ch;
    while (1)
    {
     
        menu();
        printf("       ：
");
        cin>>ch;
        switch(ch)
        {
     
        case 1:
            int n;
            ElemType x;
            printf("              ：");
            cin>>n;
            for(int i=1; i<=n; i++)
            {
     
                printf("            ：");
                cin>>x.num>>x.grade;
                InsertBST(T,x.num,x.grade);
            }
            break;
        case 2:
            f_write(T);
            break;
        case 3:
            f_read(T);
            break;
        case 4:
            printf("
              ：
");
            InOrderTraverseBTtree(T);
            break;
        case 5:
            printf("
      :%d
",Depth(T));
            break;
        case 6:
            printf("
       :%d
",nodenum(T));
            printf("
         :%d
",leafnodenum(T));
            break;
        case 7:
            char s[6];
            int score;
            printf ("         
");
            cin>>s;
            if(SearchBST(T,s))
            {
     
                printf("         ，        ！
");
                break;
            }
            printf ("         
");
            cin>>score;
            InsertBST(T,s,score);
            printf ("             
");
            InOrderTraverseBTtree(T);
            break;
        case 8:
            printf ("         
");
            char Del[6];
            cin>>Del;
            if(!SearchBST(T,Del))
            {
     
                printf("     ，        ！
");
            }
            else
            {
     
                DeleteBST(&T,SearchBST(T,Del));
                printf ("             
");
                InOrderTraverseBTtree(T);
            }
            break;
        case 9:
            printf ("         
");
            char no[6];
            cin>>no;
            if(SearchBST(T,no))
            {
     
                printf ("    %s        ：%d
",no,SearchBST(T,no));
            }
            else
            {
     
                printf("       
");
            }
            break;
        case 10:
            printf("
                ：");
            Put(T);
            break;
        default:
            printf("      ，     
");
            break;
        }
    }
    return 0;
}

/*
5
1901 98
1902 100
1903 87
1904 95
1905 65
*/