当前位置:网站首页>An experimental report on the relationship between binary tree genealogy

An experimental report on the relationship between binary tree genealogy

2020-12-08 13:06:38 osc_ k0nlk5n9

Using binary tree to express the family tree and realize various search functions

Write a program exp7-9.cpp, Use a binary tree to represent a family tree ( Composed of several genealogical records , Every genealogy is recorded by the father 、 The names of mother and son constitute , The name is the key word ), The program is required to have the following functions .
(1) File operation function : Input of genealogy records , The output of the genealogy record , Clear all the files and save the genealogy records . It is required to input the genealogy record in the order from ancestor to descendant , The first genealogy records the father domain as the ancestor of all .
(2) Genealogy operation function : Output the binary tree of family tree with bracket representation , Find all the sons of someone , Find all the ancestors of someone ( The ancestor here refers to all the ancestor nodes of a node in the designed binary tree structure ).

 Insert picture description here
My tree is like this ( Learn from others )
 Insert picture description here
The tree in the file looks like this


 Insert picture description here
A family needs three people .

 Insert picture description here
 Insert picture description here
Save to file  Insert picture description here

My code is like this

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
string s[100];// Read file storage node 
int i = 0;// Record the number of nodes when reading a file 
bool flag = false;// Delete empty to confirm   establish ancestor   
struct TreeNode{
   
   
    string name;
    struct TreeNode *lChild;
    struct TreeNode *rChild;
};

// File operations :
// Input of genealogy records ( It is required to input the genealogy record in the order from ancestor to descendant ,
// The first genealogy records the father domain as the ancestor of all .)   
// Input to save parents and children 
TreeNode *savePerson(){
   
   
    cout<<" Enter the names of the parents and children , Separate... By spaces :";
    string s1,s2,s3;
    cin>>s1>>s2>>s3;
    TreeNode *father = new TreeNode;
    father->lChild = father->rChild = NULL;
    father->name = s1;
    TreeNode *mother = new TreeNode;
    mother->lChild = mother->rChild = NULL;
    mother->name = s2;
    TreeNode *son = new TreeNode;
    son->lChild = son->rChild = NULL;
    son->name = s3;
    father->lChild = mother;
    mother->rChild = son;
    return father;
}// Women only have right children , Man left wife , Son on the right 

// Traverse to find people's names  
TreeNode* Find(TreeNode *node,string name){
   
   
    if(node==NULL)return NULL;
    if(node->name==name)return node;
    TreeNode *temp = Find(node->lChild,name);
    if(temp!=NULL)return temp;
    temp = Find(node->rChild,name);
    if(temp!=NULL)return temp;
    return NULL;
}

// Save the child's parents   If the same parent 
void save(TreeNode *root){
   
   
    // This is the case of ancestors already in the genealogy 
    TreeNode *fam = savePerson();// The parent node is the root 
    TreeNode *result = Find(root,fam->name);
    if(result!=NULL){
   
   
        if(result->lChild==NULL){
   
   
            // No wife, son  result It's the parent node found in the family tree 
            result->lChild = fam->lChild;
        }else{
   
   
            // There's a wife and a son 
            TreeNode *temp = result->lChild;// Pointing to father and wife ( mother )
            while(temp->rChild!=NULL){
   
   
            temp = temp->rChild;
            }
            temp->rChild = fam->lChild->rChild; //fam Children in 
        }
    }else if(result==NULL){
   
   
        cout<<" You didn't find your ancestors , No deposit "<<endl;
    }
}
//-------------------------------------------------------------------------------------

// The output of the genealogy record 
void showFamily(TreeNode *node){
   
   

    if(node==NULL)return;
    if(node->lChild!=NULL){
   
   
        cout<<node->name<<" ";
        TreeNode *temp = node->lChild;
        while(temp!=NULL){
   
   
            cout<<temp->name<<" ";
            temp = temp->rChild;
        }
        cout<<endl;
        TreeNode *son = node->lChild->rChild;
        while(son!=NULL){
   
   
            showFamily(son);
            son = son->rChild;
        }
    }
}

// Clear all file records // Release tree 
void freeTree(TreeNode *node){
   
   
    if(node==NULL)return;
    freeTree(node->lChild);
    freeTree(node->rChild);
    delete(node);
    node=NULL;
}
void destroyFile(){
   
   
    fstream file("family.txt",ios::out);
    cout<<" Clear file complete "<<endl;
}

// Keep the genealogical records on file 
//  Tree saved to folder 
void saveInFile(TreeNode *node){
   
   
    ofstream of("family.txt",ios::app);
    if(node==NULL){
   
    
        of<<"NULL"<<" ";
        return;
    }
    of<<node->name<<" ";
    of.close();
    saveInFile(node->lChild);
    saveInFile(node->rChild);
}


// Read the tree from the file 
void readFile(){
   
   // Read the tree nodes in the file into string Array 
    ifstream f("family.txt",ios::in);
    int i = 0;
    while(!f.eof()){
   
   
        f>>s[i];
        i++;
    }
    f.close();
}
// Build up trees 
TreeNode* BuildTree(){
   
   
    if(s[i]=="NULL"){
   
   
        i++;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        return NULL;
    }
    TreeNode *node = new TreeNode;
    node->lChild = node->rChild = NULL;
    node->name = s[i];
    i++;
    node->lChild = BuildTree();
    node->rChild = BuildTree();
    return node;
}


//-------------------------------------------------------

// // Output the binary tree of family tree with bracket representation 
void printBinaryTree(TreeNode *node){
   
   
    if(node){
   
   
        cout<<node->name; // Output when the root node exists 
    }else return; // non-existent , Then return to 
    if(node->lChild!=NULL||node->rChild!=NULL)cout<<'('; // If any of the left and right subtrees exist, it will output (
    else return; // There are no left and right subtrees 
    if(node->lChild){
   
   
        printBinaryTree(node->lChild); // The left subtree exists 
    }
    if(node->rChild){
   
   
        cout<<','; 
        printBinaryTree(node->rChild);
    }
    cout<<')';
}

void ShowSon(TreeNode *node,string name){
   
   
    // It's a matter of judging whether the father or the mother    The father must have left children , The mother must have no left child 
    TreeNode *parent = Find(node,name);
    if(parent==NULL){
   
   cout<<" Check no one "<<endl;return;}
    TreeNode *temp = NULL;
    if(parent->lChild==NULL){
   
   //bug If your brother doesn't have a wife , You'll treat your brother like a child  
        temp = parent->rChild;// Point to the first child 
        cout<<name<<" The child of is :";
        while(temp!=NULL){
   
   
            cout<<temp->name<<" ";
            temp = temp->rChild;
        }
        cout<<endl;
    }else if(parent->lChild!=NULL){
   
   
        temp = parent->lChild->rChild;
        cout<<name<<" The child of is :";
        while(temp!=NULL){
   
   
            cout<<temp->name<<" ";
            temp = temp->rChild;
        }
        cout<<endl;
    }
}

// // Find all the ancestors of someone ( The ancestor here refers to all the ancestor nodes of a node in the designed binary tree structure )
bool ShowAllFather(TreeNode *node,string name){
   
   
    if(node==NULL)return false;
    if(node->name==name)return true;
    if(ShowAllFather(node->lChild,name)||ShowAllFather(node->rChild,name)){
   
   
        cout<<node->name<<" ";
        return true;
    }
    return false;
}

int main(){
   
   
    TreeNode *ancestor = NULL;
    char a;
    while(true){
   
   
        cout<<" choice 1 Create a new family tree , choice 2 With the genealogy stored in the file "<<endl; 
        cin>>a;
        if(a=='1'){
   
   
            ancestor = savePerson(); ;
            break;
        }
        else if(a=='2'){
   
   
            fstream f("family.txt");
            f.seekg(0,ios::end);
            streampos fp = f.tellg();
            if(int(fp)==0){
   
   
                cout<<" The file is empty "<<endl;
            }else{
   
   
                readFile();
                ancestor = BuildTree();
                break;
            }
            f.close();
        }
        else cout<<" Input error "<<endl;
    }

    cout<<"----------------------------- Genealogy ------------------------------"<<endl;
    while(true){
   
   
        char choose1 = -1;
        cout<<" Press 1 Select file operation , Press 2 Select genealogy operation , Press 3 sign out . Your choice is :";
        cin>>choose1;
        if(choose1=='1'){
   
   
            while(true){
   
   
                char choose2 = '-1';
                cout<<" Press 1 Select input genealogy , Press 2 Choose output genealogy , Press 3 Select clear record to return to , Press 4 Select save record and return to . Your choice is :";
                cin>>choose2;
                if(choose2=='1'){
   
   
                    if(flag==false){
   
   
                        save(ancestor);
                    }else if(flag==true){
   
   
                        ancestor = savePerson();
                    }
                }else if(choose2=='2'){
   
   
                    if(ancestor==NULL){
   
   
                        cout<<" The genealogy is empty "<<endl;
                    }else{
   
   
                    showFamily(ancestor);
                    cout<<endl;
                    }
                }else if(choose2=='3'){
   
   
                    freeTree(ancestor);
                    destroyFile();
                    ancestor = NULL;
                    flag = true;
                    break;
                }else if(choose2=='4'){
   
   
                        if(ancestor==NULL){
   
   
                            cout<<" The genealogy is empty "<<endl;
                        }else{
   
   
                            // If it's not empty , Empty the folder first 
                            fstream f("family.txt",ios::out);
                            f.close();
                            saveInFile(ancestor);
                            cout<<" Saved successfully "<<endl;
                            break;  
                        }  
                }else {
   
   
                    cout<<" Input error "<<endl;
                }
            }
        }else if(choose1=='2'){
   
   
            while(true){
   
   
                char choose3 = '-1';
                cout<<" Press 1 Choose the bracket representation to output , Press 2 Choose to find all of someone's sons , Press 3 Choose to find all of one's ancestors , Press 4 Choose to return to . Your choice is :";
                cin>>choose3;
                if(choose3=='1'){
   
   
                    if(ancestor==NULL){
   
   
                        cout<<" The genealogy is empty "<<endl;
                    }else{
   
   
                    printBinaryTree(ancestor);
                    cout<<endl;
                    }
                }else if(choose3=='2'){
   
   
                    if(ancestor==NULL){
   
   
                        cout<<" The genealogy is empty "<<endl;
                    }else{
   
   
                    cout<<" Please enter the name of whose son you are looking for "<<endl;
                    string s ;
                    cin>>s;
                    ShowSon(ancestor,s);
                    cout<<endl;
                    }
                }else if(choose3=='3'){
   
   
                    if(ancestor==NULL){
   
   
                        cout<<" The genealogy is empty "<<endl;
                    }else{
   
   
                    cout<<" Please enter all the ancestors of whom you want to find "<<endl;
                    string s;
                    cin>>s;
                    cout<<s<<" All of our ancestors are :";
                    ShowAllFather(ancestor,s);
                    cout<<endl;
                    }
                }else if(choose3=='4'){
   
   
                    break;
                }else {
   
   
                    cout<<" Output error "<<endl;
                }
            }
        }else if(choose1=='3'){
   
   
            break;
        }else cout<<" Output error "<<endl;
        cout<<"----------------------------------------------------------"<<endl;
    }

    //------------------------------------------------------------------------
   
    system("pause");
    return 0;
}

版权声明
本文为[osc_ k0nlk5n9]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201208130550815d.html