2017-3

/* 2020/4/16 第二遍 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>struct a
{
    char s1[20];char s2[20];char s3[20];
}input[100];int N;
char str1[20];
char str2[20];typedef struct node
{
    char name[20];int layer;node* parent;node* lchild;node* rchild;
}Node,*Tree;Node* newNode(char name[])
{
    Node* temp = (Node*)malloc(sizeof(Node));strcpy(temp->name,name);temp->layer = 0;temp->parent = temp->lchild = temp->rchild = NULL;return temp;
}void createTree(Node* root)
{
    int i;for(i = 0;i<N;i++)if(strcmp(root->name,input[i].s1) == 0)break;if(i == N) return ;Node* temp1 = newNode(input[i].s2);temp1->layer = root->layer + 1;temp1->parent = root;root->lchild = temp1;createTree(temp1);Node* temp2 = newNode(input[i].s3);temp2->layer = root->layer + 1;temp2->parent = root;root->rchild = temp2;createTree(temp2);
}void preOrder(Node* root)
{
    if(root){
    if(root->parent!=NULL){
    printf("%s %d %s\n",root->name,root->layer,root->parent->name);}else{
    printf("%s %d\n",root->name,root->layer);}preOrder(root->lchild);preOrder(root->rchild);}
}Node* findChildPosition(Node* root,char name[20])
{
    if(root == NULL) return NULL;if(strcmp(root->name,name) == 0)return root;Node* temp1 = findChildPosition(root->lchild,name);if(temp1) return temp1;Node* temp2 = findChildPosition(root->rchild,name);if(temp2) return temp2;return NULL;//通过左右子树都没有找到
}//第一种方法求公共祖先节点
Node* LeastCommonAncient(Node* root,char name1[],char name2[])
{
    Node* temp1 = findChildPosition(root,name1);Node* temp2 = findChildPosition(root,name2);int layer1 = temp1->layer;int layer2 = temp2->layer;if(layer1 > layer2){
    int c = layer1 - layer2;printf("%d\n",c);while(c--){
    temp1 = temp1->parent;}}if(layer1 < layer2){
    int d = layer2 - layer1;printf("%d\n",d);while(d--){
    temp2 = temp2->parent;}}if(temp1 == temp2) return temp1;while(temp1->parent != temp2->parent){
    temp1 = temp1->parent;temp2 = temp2->parent;}return temp1->parent;
}int main()
{
    scanf("%d",&N);for(int i = 0;i<N;i++){
    scanf("%s%s%s",input[i].s1,input[i].s2,input[i].s3);}scanf("%s%s",str1,str2);Node* root = newNode(input[0].s1);root->layer = 1;createTree(root);printf("%s\n",LeastCommonAncient(root,str1,str2)->name);return 0;
}/* IN: 4 Ye Shu Ba Shu Ge Mei1 Ba Self Mei2 Ge Son1 Son2 Son2 Mei1 OUT: 1 Shu */

• 注意：

//如果没有输入N怎么办？int N = 0while( scanf("%s%s%s",t1,t2,t3) == 3){
    strcpy(ssd[N].n1,t1);strcpy(ssd[N].n2,t2);strcpy(ssd[N].n3,t3);N++;}strcpy(tmp1,t1);strcpy(tmp2,t2);

//如果给定的数据没有指定根节点，如何自己寻找？
#include<stdio.h>
#include<stdlib.h>
#include<string.h>struct a
{
    char s1[20];char s2[20];char s3[20];
}input[100];int N = 0;
char str1[20];
char str2[20];typedef struct node
{
    char name[20];int layer;node* parent;node* lchild;node* rchild;
}Node,*Tree;int main()
{
    char t1[20],t2[20],t3[20];N = 0;while(scanf("%s%s%s",t1,t2,t3) == 3){
    strcpy(input[N].s1,t1);strcpy(input[N].s2,t2);strcpy(input[N].s3,t3);N++;}strcpy(str1,t1);strcpy(str2,t2);int i;/*for(i = 0;i<N;i++){printf("%s %s %s\n",input[i].s1,input[i].s2,input[i].s3);}*/char nameFather[20];strcpy(nameFather,input[0].s1);printf("%s\n",nameFather);i = 0;while(i != N){
    if(strcmp(nameFather,input[i].s2) == 0){
    strcpy(nameFather,input[i].s1);//printf("1 %s\n",nameFather);i = 0;}else if(strcmp(nameFather,input[i].s3) == 0){
    strcpy(nameFather,input[i].s1);//printf("2 %s\n",nameFather);i = 0;}else{
    //printf("3 %d\n",i);i++;}}printf("%s\n",nameFather);return 0;
}
/* IN: Shu Ge Mei1 Ba Self Mei2 Ye Shu Ba Ge Son1 Son2 Son2 Mei1 ^Z OUT: Shu Ye */