题解 | #找出直系亲属#

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

//习题11.1 找出直系亲属
struct TreeNode{
    char data;
    TreeNode *leftchild;
    TreeNode *rightchild;
    TreeNode *father;
    TreeNode(int data):data(data),leftchild(NULL),rightchild(NULL),father(NULL){}
};



TreeNode *root=NULL;

TreeNode *findednode=NULL;
void findnode(TreeNode *t,char x){//使用之前记得清空findednode
    if(t==NULL)return;
    if (t->data==x){
        findednode=t;
        return;
    }
    findnode(t->leftchild,x);
    findnode(t->rightchild,x);
}

void ins(char para1,char para2,char para3){
    findednode=NULL;
    findnode(root,para1);
    if(findednode==NULL){//只有一种可能无法找到：就是第一行
        root=new TreeNode(para1);
        findednode=root;
    }
    findednode->leftchild=new TreeNode(para2);
    findednode->rightchild=new TreeNode(para3);
    findednode->leftchild->father=findednode;
    findednode->rightchild->father=findednode;
}

void query(char q1,char q2){
    string older="nobody";

    findednode=NULL;
    findnode(root,q1);
    TreeNode *node1=findednode;

    findednode=NULL;
    findnode(root,q2);
    //cout<<"q2:"<<q2<<endl;
    TreeNode *node2=findednode;
    //cout<<"find:"<<findednode->data<<endl;

    TreeNode*tmp=node1;

    //cout<<node1->data<<endl;
    //cout<<node2->data<<endl;

    int dist=0;
    while(tmp!=node2&&tmp!=NULL){
        //cout<<tmp->data<<endl;
        tmp=tmp->father;
        dist++;
    }
    if(tmp==node2)older="q1";
    else{
        dist=0;
        tmp=node2;
        while(tmp!=node1&&tmp!=NULL){
            tmp=tmp->father;
            dist++;
        }
    }
    if(tmp==node1)older="q2";
    if(older=="nobody")cout<<"-"<<endl;
    else if(older=="q1"){
        if(dist==1)cout<<"parent"<<endl;
        else if(dist==2)cout<<"grandparent"<<endl;
        else{
            for(int i=dist;i>2;i--){
                cout<<"great-";
            }
            cout<<"grandparent"<<endl;
        }
    }
    else{
        if(dist==1)cout<<"child"<<endl;
        else if(dist==2)cout<<"grandchild"<<endl;
        else{
            for(int i=dist;i>2;i--){
                cout<<"great-";
            }
            cout<<"grandchild"<<endl;
        }
    }
}

int main(){
    int m,n;
    char para1,para2,para3;
    char q1,q2;
    cin>>m>>n;
    while(m--){
        cin>>para1>>para2>>para3;
        ins(para1,para2,para3);
    }
    while(n--){
        cin>>q1>>q2;
        query(q1,q2);
    }
    return 0;
}