Как обойти дерево многолучевого дерева - PullRequest
Новая
       23

Как обойти дерево многолучевого дерева

1 голос
/ 11 апреля 2019

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

Моя идея былавот так: у меня есть дерево, ребенок и его братья и сестры.Я хочу рекурсивно разобраться с детьми и затем, если у него есть братья и сестры, рекурсивно опускаться и на них.

Здесь я представлю вам свою структуру данных и то, как я пытался реализовать это.Вот полный ФУНКЦИОНАЛЬНЫЙ «тестируемый», который ТАКЖЕ создаст фотографию для вас, чтобы вы могли увидеть дерево и использовать код: 

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

#define SIZE    100

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

Tree initTree(int value) {
    Tree root = malloc(sizeof(struct tree));
    root->value = value;
    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);
}

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

    forest[4]->child = forest[3];
    forest[4]->child->sibling = forest[2];
    forest[1]->child = forest[0];
    forest[1]->child->sibling = forest[4];

    for (i = 0; i < 5; i++) {
        sprintf(buffer, "tree_%d.png", i);
        if (forest[i]) {
            drawTree(forest[i], buffer);
        }
    }
    return 0;
}

Функция, которую я хочу создать, остается той же самой: 

Tree findChild(Tree root, int value)
{
    if(!root) return NULL;
    if(root->value == value) return root;

    return findChild(root->child, value);
    Trie iter = root;
    while(iter)
    {
        return findChild(iter->sibling, value);
        iter = iter->sibling;
    }
}

Я ожидал бы найти дочерний элемент, но он возвращает мне NULL, если узел не является прямым дочерним элементом root.Ожидание функции, которую я хочу создать: найти ребенка наиболее эффективным способом в дереве.

1 Ответ

0 голосов
/ 11 апреля 2019

Это ваша функция: 

Tree findChild(Tree root, int value)
{
    if(!root) return NULL;
    if(root->value == value) return root;

Здесь вы пересекаете дочерние узлы, но говорите return! 

    return findChild(root->child, value);

Таким образом, этот код никогда не выполняется: 

    Tree iter = root;
    while(iter)
    {
        return findChild(iter->sibling, value);
        iter = iter->sibling;
    }
}

Кроме того, итерация бесполезна, так как вы все равно перебираете следующего брата с помощью вызова findChild. Так что функция должна выглядеть примерно так: 

Tree findChild(Tree root, int value)
{
    if(!root) return NULL;
    if(root->value == value) return root;

    Tree *ret = findChild(root->child, value);
    if (!ret)
        ret = findChild(root->sibling, value);

    return ret;
}

Это должно работать так, как вы ожидаете.

Edit:

После (безусловного) return код никогда не выполняется. Просто нет кодового пути, чтобы «обойти» этот возврат.

Это, вероятно, самый эффективный способ (если говорить о сложности времени выполнения) , если элементы в дереве не следуют определенному порядку . Если дерево упорядочено, вы можете воспользоваться этим, взглянув на текущий элемент, сравнив его с искомым элементом, а затем, основываясь на результате сравнения, выберите только один из двух путей child или sibling вместо обхода. как.

...