我试图遍历一个多路树,但我试图以一种有效的方式做,但这并没有真正帮助我,更重要的是我想要递归地做。
我的想法是这样的:我有一棵树,一个孩子和它的兄弟姐妹。我想和孩子一起递归下去,然后只要它有兄弟姐妹也递归下去。
在这里,我将向您介绍我的数据结构以及我是如何尝试实现这一点的。这是一个完整的功能“可测试”,它还将为您创建一张照片,以便您查看树并使用代码:
#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;
}
}
我希望找到孩子,但如果节点不是root的直接子节点,它会返回NULL。期望我想要创建的函数:在树中以最有效的方式查找子项。
这是你的功能:
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;
}
这应该按照您的预期工作。
编辑:
在(无条件的)return
之后,代码永远不会被执行。没有代码路径可以“回避”返回。
如果树中的项不遵循特定顺序,这可能是最有效的方式(就运行时复杂性而言)。如果树是有序的,你可以通过查看当前项目,将其与搜索的项目进行比较然后 - 根据比较结果 - 仅选择两个路径中的一个child
或sibling
而不是遍历两者来利用它。