Узел дерева печати и все его дочерние элементы эффективно

Question

Я пытаюсь создать функцию, которая печатает узел и все его дочерние элементы, но я пытаюсь сделать его эффективным и рекурсивным.Но на самом деле это не работает.

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

#define SIZE    100

typedef struct tree {
    int value;
    struct tree *child, *sibling, *parent;
} *Tree;

Tree initTree(int value) {
    Tree root = malloc(sizeof(struct tree));
    root->value = value;
    root->parent = NULL;
    root->child = NULL;
    root->sibling = NULL;
    return root;
}

void drawTreeHelper(Tree tree, FILE* stream) {
    Tree tmp;
    if (tree == NULL) {
        return;
    }
    fprintf(stream, "    %ld[label=\"%d\", fillcolor=red]\n", (intptr_t) tree, tree->value);
    tmp = tree->child;

    while (tmp != NULL) {
        fprintf(stream, "    %ld -> %ld \n", (intptr_t) tree, (intptr_t) tmp);
        drawTreeHelper(tmp, stream);
        tmp = tmp->sibling;
    }
}

void drawTree(Tree tree, char *fileName) {
    FILE* stream = fopen("test.dot", "w");
    char buffer[SIZE];
    fprintf(stream, "digraph tree {\n");
    fprintf(stream, "    node [fontname=\"Arial\", shape=circle, style=filled, fillcolor=yellow];\n");
    if (tree == NULL)
        fprintf(stream, "\n");
    else if (!tree->child)
        fprintf(stream, "    %ld [label=\"%d\"];\n", (intptr_t) tree, tree->value);
    else
        drawTreeHelper(tree, stream);
    fprintf(stream, "}\n");
    fclose(stream);
    sprintf(buffer, "dot test.dot | neato -n -Tpng -o %s", fileName);
    system(buffer);
}

Tree uniteTries(Tree child, Tree parent)
{
    if (parent)
    {
        if (!parent->child) parent->child = child;
        else
        {
            Tree iter = parent->child;
            while (iter->sibling) iter = iter->sibling;
            iter->sibling = child;
        }
    }
    return parent;
}

Tree uniteForest(Tree root, Tree *forest, int n)
{
    int i;
    for (i = 0; i < n; ++i)
    {
        if (forest[i]) root = uniteTries(forest[i], forest[i]->parent);
    }
    root = forest[0];
    return root;
}

void printParentChildRec(Tree root)
{
    if(!root) return;
    printf("%d ", root->value);

    printParentChildRec(root->sibling);
    printParentChildRec(root->child);
}

int main() {
    int i;
    char buffer[SIZE];
    Tree *forest = malloc(6 * sizeof(Tree));
    for (i = 0; i < 6; i++) {
        forest[i] = initTree(i);
    }

    forest[1]->parent = forest[0];
    forest[2]->parent = forest[0];
    forest[3]->parent = forest[0];
    forest[4]->parent = forest[1];
    forest[5]->parent = forest[1];

    Tree root = uniteForest(root, forest, 6);

    printParentChildRec(root);

    drawTree(root, "tree.png");

    return 0;
}

Этот код предоставит вам проверяемый пример, и вот что я пытался сделать:

void printParentChildRec(Tree root) {
    if (!root)
        return;
    printf("%d ", root->value);

    printParentChildRec(root->sibling);
    printParentChildRec(root->child);
}

Результаты, которые я получаю, просто0 1 2 3 4 5 это все узлы, но я хочу напечатать что-то вроде этого:

0 1 2 3
1 4 5
2
3
4
5

Answer 1

Я думаю, что ваша функция объединения деревьев является проблемой здесь.Я запустил этот код с помощью моего отладчика, и вот как он выглядит из корня

Это корень, введенный в функцию печати после метода объединения деревьев:

Можете ли вы сказать мне, чего вы пытаетесь достичь здесь, и, возможно, я могу вам помочь!

Answer 2

В вашем коде есть некоторые проблемы:

• Вы скрываете указатели за typedefs, это сбивает с толку читателей вашего кода и часто приводит к ошибкам программирования.
• Вы печатаете intptr_t значения с %ld, что является неопределенным поведением на платформах, где intptr_t не является псевдонимом для long и имеет другой размер, например, 64-битная Windows. Для этого типа не существует определенного формата printf, вам следует либо изменить значение как (long)(intptr_t)tree или (long long)(intptr_t)tree и использовать %lld, либо их неподписанные версии, либо использовать формат %p с (void *)tree.
• ожидаемый результат не в виде текста, а в некоторой форме графического рендеринга, которую сложно проанализировать из кода. Сначала будет проще отладить вывод текста.

В вашем коде больше проблем:

• in main(), Tree root = uniteForest(root, forest, 6); передает неопределенную переменную root в uniteForest.

• аргумент root в Tree uniteForest(Tree root, Tree *forest, int n) никогда не используется, он используется только для хранения временных результатов. Вы должны просто удалить аргумент и упростить код как:

  Tree uniteForest(Tree *forest, int n) {
      for (int i = 0; i < n; i++) {
          if (forest[i])
              uniteTries(forest[i], forest[i]->parent);
      }
      return forest[0];
  }
  

• main печатает только корень дерева, следовательно рекурсивно значение forest[0] и его потомков. Вместо этого вы хотите напечатать значение узла и его непосредственных потомков: , а затем recurse для каждого потомка.

Вот исправленная версия:

void printParentChildRec(Tree node) {
    if (node) {
        printf("%d ", node->value);
        for (Tree child = node->child; child; child = child->sibling) {
            printf("%d ", child->value);
        }
        printf("\n");
        for (Tree child = node->child; child; child = child->sibling) {
            printParentChildRec(child);
        }
    }
}

Выход:

0 1 2 3
1 4 5
4
5
2
3