C 中的树结构不正确

Question

我有这个代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LINE_LENGTH 63

typedef struct node
{
    char* name;
    struct node *mom; //left
    struct node *dad; //right
    int isRoot;
} t_node;

t_node* createNode(char* name) {
    t_node* newNode = malloc(sizeof(t_node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(1);
    }
    newNode->name = strdup(name); // Allocate memory for the name and copy it
    newNode->mom = NULL;
    newNode->dad = NULL;
    newNode->isRoot = 1;

    return newNode;
}

void freeMemory(t_node* nodeArray[], int numNodes){
    for (int i = 0; i < numNodes; i++) {
        free(nodeArray[i]->name);
        free(nodeArray[i]);
    }
}

void printNodes(t_node* nodeArray[], int numNodes){
    printf("Nodes created:\n");
    for (int i = 0; i < numNodes; i++) {
        printf("%s\n", nodeArray[i]->name);
    }
}

t_node* findNodeByName(t_node* nodeArray[], int numNodes, const char* name) {
    for (int i = 0; i < numNodes; i++) {
        if (strcmp(nodeArray[i]->name, name) == 0) {
            return nodeArray[i];
            
        }
    }
    return NULL; // Node not found
}

void addFather(t_node* currentNode, t_node* fatherNode) {
    if (currentNode->dad != NULL) {
        fprintf(stdout, "Kļūda: 2 tēvi nav atļauti.\n");
        exit(1);
    }
    if (fatherNode->dad == currentNode || fatherNode->mom == currentNode) {
        fprintf(stdout, "Kļūda: cikliskas attiecības.\n");
        exit(1);
    }
    currentNode->dad = fatherNode;
    fatherNode->isRoot = 0;
}

void addMother(t_node* currentNode, t_node* motherNode) {
    if (currentNode->mom != NULL) {
        fprintf(stdout, "Kļūda: 2 mātes nav atļautas.\n");
        exit(1);
    }
    if (motherNode->dad == currentNode || motherNode->mom == currentNode) {
        fprintf(stdout, "Kļūda: cikliskas attiecības.\n");
        exit(1);
    }
    currentNode->mom = motherNode;
    motherNode->isRoot = 0;
}


void printTree(t_node* rootNode, int depth, FILE *stdout) {
    if (rootNode == NULL) {
        return;
    }

    // Print the right subtree (father) first
    printTree(rootNode->dad, depth + 1,stdout);

    // Print the left subtree (mother)
    printTree(rootNode->mom, depth + 1,stdout);

    // Print the current node
    for (int i = 0; i < depth; i++) {
    }
    fprintf(stdout,"%s\n", rootNode->name);
}


int main() {
    char line[MAX_LINE_LENGTH];
    char* name;


    t_node* nodeArray[10000]; // Array to store pointers to created nodes
    int numNodes = 0;

    while (fgets(line, MAX_LINE_LENGTH, stdin) != NULL) {
    if (strstr(line, "NAME")) {
        name = strstr(line, "NAME") + 5;
        name[strcspn(name, "\n")] = 0; // Remove newline character

        // Check if the node already exists
        t_node* person = findNodeByName(nodeArray, numNodes, name);
        if (person == NULL) {
            // Create a node for the person
            person = createNode(name);
            nodeArray[numNodes++] = person;
        }
    } else if (strstr(line, "FATHER")) {
        char* father = strstr(line, "FATHER") + 7;
        father[strcspn(father, "\n")] = 0;
    
        // Check if the father node already exists
        t_node* fatherNode = findNodeByName(nodeArray, numNodes, father);
        if (fatherNode == NULL) {
            // Create a node for the father
            fatherNode = createNode(father);
            nodeArray[numNodes++] = fatherNode;
        }
    } else if (strstr(line, "MOTHER")) {
        char* mother = strstr(line, "MOTHER") + 7;
        mother[strcspn(mother, "\n")] = 0;

        // Check if the mother node already exists
        t_node* motherNode = findNodeByName(nodeArray, numNodes, mother);
        if (motherNode == NULL) {
            // Create a node for the mother
            motherNode = createNode(mother);
            nodeArray[numNodes++] = motherNode;
        }
    }
}

rewind(stdin);
t_node* currentNode; 

    while (fgets(line, MAX_LINE_LENGTH, stdin) != NULL) {
    if (strstr(line, "NAME")) {
        name = strstr(line, "NAME") + 5;
        name[strcspn(name, "\n")] = 0; // Remove newline character

        // Find the current node by name
            currentNode = findNodeByName(nodeArray, numNodes, name);
        if (currentNode == NULL) {
            return 1;
        }
    } else if (strstr(line, "FATHER")) {
        char* fatherName = strstr(line, "FATHER") + 7;
        fatherName[strcspn(fatherName, "\n")] = 0;
        
        // Find the father node by name
        t_node* fatherNode = findNodeByName(nodeArray, numNodes, fatherName);
        if (fatherNode == NULL) {
            return 1;
        }

        // Add father to the current node
        addFather(currentNode, fatherNode);
    } else if (strstr(line, "MOTHER")) {
        char* motherName = strstr(line, "MOTHER") + 6;
        motherName[strcspn(motherName, "\n")] = 0;

        // Find the mother node by name
        t_node* motherNode = findNodeByName(nodeArray, numNodes, motherName);
        if (motherNode == NULL) {
            return 1;
        }

        // Add mother to the current node
        addMother(currentNode, motherNode);
    }
}
  // Assuming rootNode is the root node of the tree


    for (int i = 0; i < numNodes; i++) {
        if (nodeArray[i]->isRoot) {
            printTree(nodeArray[i], 0, stdout);
                fprintf(stdout,"\n");
        }
    }
    


   //printNodes(nodeArray, numNodes);
   freeMemory(nodeArray, numNodes);

    return 0;
}

输入txt文件如下所示：

NAME Dels
FATHER Tevs
MOTHER Mate

NAME Tevs 
MOTHER Vecmate

NAME CitsDels
MOTHER CitaMate
FATHER CitsTevs

NAME Vecmate
FATHER Vecvectevs
MOTHER Vecvecmate

输出：

Tevs
Mate
Dels

Vecvectevs
Vecvecmate
Vecmate
Tevs 

CitsTevs
CitaMate
CitsDels

输入：

NAME Dels
FATHER Tevs
MOTHER Mate

NAME Tevs
MOTHER Vecmate

NAME CitsDels
MOTHER CitaMate
FATHER CitsTevs

我得到了我所期望的：

Vecmate
Tevs
Mate
Dels

CitsTevs
CitaMate
CitsDels

我的想法是在txt文件中为每个人创建节点并在他们之间创建关系。我有 isRoot 变量来按降序打印所有家庭成员，并提供如果人们没有关系，我可以打印多个家谱。树用空行分隔。为什么在第一种情况下看起来 Tevs 成为根并拥有自己的树，但它应该从 Dels 到 Vecvectevs

任务：从txt文件中获取输入，其中每个人的描述以单词NAME开头，人之间可以是多行，我们应该从所有人创建家谱，并按级别降序打印它们，祖父母-2，父母-1，根- 0。我们应该一开始就打印所有父母的所有祖父母。

正确输出：

Vecvectevs
Vecvecmate
Vecmate
Tevs 
Mate
Dels

CitsTevs
CitaMate
CitsDels

寻求帮助解决这个问题，该节点成为根，即使它不应该成为根。

Answer 1

问题似乎出在树的打印上。您在左子树（母亲）之前递归地打印右子树（父亲），这会导致树被颠倒打印。您需要在 printTree 函数中切换打印父亲和母亲的顺序。这是 printTree 函数的更正版本：

void printTree(t_node* rootNode, int depth, FILE *stdout) {
    if (rootNode == NULL) {
        return;
    }

    // Print the left subtree (mother) first
    printTree(rootNode->mom, depth + 1, stdout);

    // Print the right subtree (father)
    printTree(rootNode->dad, depth + 1, stdout);

    // Print the current node
    for (int i = 0; i < depth; i++) {
        fprintf(stdout, "   ");
    }
    fprintf(stdout, "%s\n", rootNode->name);
}

通过此修改，树应该正确打印，祖父母出现在父母上方，根节点出现在顶部。尝试用这个更正后的版本替换 printTree 函数，看看是否可以解决问题。