```自己写的蛮烂，将就看看，给个建议啥的最好了
// 乐鑫科技2021提前批软件类笔试
// 题目大意:构建家族树，输出两个家族成员的辈分，亲属关系，其中亲属关系，父子为1.兄弟为2
// 输入：第一行：三个整型，家族成员数量，成员1，成员2
// 之后按家族成员数量输入 父亲，子女
// 输出：辈分差，亲属关系
// 例如;
// 15 7 2 0
// 0 1 1 2
// 0 2 ========》》 3 4 5 6
// 1 3 7 8 9 10 11 12 13 14
// 1 4
// 2 5
// 2 6
// 3 7
// 3 8
// 4 9
// 4 10
// 5 11
// 5 12
// 6 13
// 6 14
// 输出：-2 4
#include <iostream>
#include <vector>
using namespace std ;
struct person
{
public:
int name;
person *firChild;
person *secChild;
person *Father;
};
person* create_person(int m_nanme,person *m_father){
person *m_person = (person *)malloc(sizeof(person));
m_person ->name = m_nanme;
m_person ->firChild = NULL;
m_person ->secChild = NULL;
m_person ->Father = m_father;
return m_person;
}
person* find(person *m_root,int m_name){
person *m_person =NULL;
if(m_root == NULL) return NULL;
if(m_root ->name == m_name) return m_root;
if(m_person = find(m_root->firChild,m_name)) return m_person;
return find(m_root->secChild,m_name);
}
// bool family_has_person(person *m_root,int m_name){
// if(find(m_root, m_name)!=NULL) return true ;
// else return false;
// }
person* create_famliy_tree(int m_generation){
person *m_root = NULL;//根节点
// person *m_root =(person *)malloc(sizeof(person));
person *m_father = NULL;
person *m_child = NULL;
int m_father_name,m_child_name;
for (int i = 0; i < m_generation-1; i++)
{
cin>>m_father_name >>m_child_name;
if (m_root == NULL ){
m_root =(person *)malloc(sizeof(person));
m_root ->name = m_father_name;
printf("加入成员%d\n",m_father_name);
m_child = create_person(m_child_name,m_root);
m_root ->firChild = m_child;
m_root ->secChild = NULL;
m_root ->Father = NULL;
printf("加入成员%d\n",m_child_name);
}else if(m_father = find(m_root,m_father_name)){
if(m_father->firChild ==NULL ){
m_child = create_person(m_child_name,m_father);
m_father ->firChild = m_child;
printf("加入成员%d\n",m_child_name);
}else if(m_father->secChild == NULL){
m_child = create_person(m_child_name,m_father);
m_father ->secChild = m_child;
printf("加入成员%d\n",m_child_name);
}else{
printf("此父亲已有两个孩子\n");
i--;
}
}else{
printf("家族中不存在此成员\n");
i--;
}
}
return m_root;
}
vector<int> find_path_to_root(person *m_person){
vector<int> path_to_root;
person *m_person_point = m_person;
while (m_person_point != NULL)
{
path_to_root.push_back(m_person_point ->name);
m_person_point = m_person_point ->Father;
}
return path_to_root;
}
int find_same_parent(vector<int>path1,vector<int>path2){
for (int i = 0; i < path1.size(); i++)
{
int person_name = path1[i];
for(int j =0 ; j < path2.size();j++){
if(person_name == path2[j]) return person_name;
}
}
}
int generation_to_sameparent(vector<int> m_vec, int m_name){
for (int i = 0; i < m_vec.size(); i++)
{
if(m_vec[i] == m_name ) return i;
}
}
int main(){
int generation,person1_name,person2_name;
cin >>generation>>person1_name>>person2_name;
person *root = create_famliy_tree(generation);
printf("生成家族树\n");
if(find(root,person1_name) !=NULL &&find(root,person2_name) != NULL){
printf("两人均存在\n");
person *person1 = find(root,person1_name);
person *person2 = find(root,person2_name);
vector<int> person1_to_root,person2_to_root;
person1_to_root = find_path_to_root(person1);
person2_to_root = find_path_to_root(person2);
int person1_generation =person1_to_root.size();
int person2_generation =person2_to_root.size();
int same_parent_name = find_same_parent(person1_to_root,person2_to_root);
int generation_to_same_parent =generation_to_sameparent(person1_to_root,same_parent_name);
printf("%d ,%d",person2_generation-person1_generation,person1_generation+person2_generation-2-2*(person1_generation-1-generation_to_same_parent));
}else{
printf("家族中不存在此人\n");
}
}
Processed:
0.011, SQL:
9
