使树水平增长，应用对当前节点的修改

给定一个输入，我正在尝试构建一个树，该树应该水平增长，将变换应用于该输入和随后的子节点。

例如，给定输入’aab’和两个转换规则，如：

ab -> bba b -> ba 

需要构建这样的树：

我已经编写了代码，但是我已经完成了它，我的树垂直工作，我不想那样做。 我需要它水平工作，我不知道我将在何处/如何编写递归。 这就是我现在所拥有的：

  #include  #include  #include  #include  typedef struct t_string_node { struct t_string_node *next; char *value; } string_node; typedef struct t_transformation_rule { struct t_transformation_rule *next; char *needle; char *replacement; } transformation_rule; void findTransformations(char *origin, string_node **transformations, char *needle, char *replacement) { char *str = origin; for (char *p = str; *p != '\0'; p++) { if (strncmp(p, needle, strlen(needle)) == 0) { char *str_ = malloc(strlen(str)+1+strlen(replacement)-strlen(needle)); strcpy(str_, str); char *p_ = p - str + str_; memmove(p_+strlen(replacement), p_+strlen(needle), strlen(p_)+1-strlen(replacement)); memcpy(p_, replacement, strlen(replacement)); //Create new string node. string_node *transformation; transformation = malloc(sizeof(string_node)); transformation->value = str_; transformation->next = NULL; while (*transformations != NULL) { transformations = &(*transformations)->next; } *transformations = transformation; } } } int hasTransformation(char *origin, char *target, transformation_rule *list_of_rules) { int level; level = 0; int found; string_node *current; current = malloc(sizeof(string_node)); current->value = origin; current->next = NULL; if(list_of_rules == NULL) { if (strcmp(origin, target) == 0) { printf("Solution in 0 steps"); return 1; } else { printf("No solution"); return 0; } } string_node *transformations; transformations = NULL; while (current != NULL) { findTransformations(current->value, target, &transformations, list_of_rules->needle, list_of_rules->replacement); findTransformations(current->value, &transformations, list_of_rules->next->needle, list_of_rules->next->replacement); current = current->next; } while (transformations != NULL) { printf("%s \n", transformations->value); transformations = transformations->next; } return 1; } void main() { char *input = "aab"; char *target = "bababab"; char *needle = "ab"; char *replacement = "bba"; transformation_rule *list_of_rules; list_of_rules = NULL; list_of_rules = malloc(sizeof(transformation_rule)); list_of_rules->needle = "ab"; list_of_rules->replacement = "bba"; list_of_rules->next = NULL; //Create another rule transformation_rule *new_rule; new_rule = malloc(sizeof(transformation_rule)); new_rule->needle = "b"; new_rule->replacement = "ba"; new_rule->next = NULL; list_of_rules->next = new_rule; int has_trans; has_trans = hasTransformation(input, target, list_of_rules); } 

任何人都可以帮助我意识到我将如何做到这一点，使树水平而不是垂直生长？

谢谢

Answer 1

@All：这个问题是对这个问题的延续（即使使用我制作的图片）。

现在是深度优先与广度优先问题的答案：对此，您根本不应该构建树数据结构。 你需要关心的只是当前层和下一层。

所以你只需为每个创建一个列表。 在开始时，你将你的起始字符串放在当前，然后你的下一个是空的。 然后你会看到你可以aaba abba和aaba所以你把它们放到下一个。 然后清除 当前状态并将下一个内容放入当前状态 ，然后清除。

你不断重复这个，直到你发现你正在将目标字符串添加到下一个然后你可以停止搜索。

并且 ：正如我在上面提到的答案中所说的：这可能不会终止并且是否最终将终止（Halting-problem）是不可判定的，但是在特定情况下有许多启发式检测非终止。

编辑 ：好的，这是代码！

 #include "stdlib.h" #include "stdio.h" #include "string.h" struct list_s { struct list_s* next; char* entry; }; char* paste(char* begin, int len1, char* mid, int len2, char* end, int len3) { char* a = malloc(len1+len2+len3+1); memcpy(a, begin, len1); memcpy(a+len1, mid, len2); memcpy(a+len1+len2, end, len3); a[len1+len2+len3] = '\0'; return a; } void push(struct list_s** top, char* p) { struct list_s* l = malloc(sizeof(struct list_s)); l->next = *top; l->entry = p; *top = l; } char* pop(struct list_s** top) { char* res = (*top)->entry; struct list_s* next = (*top)->next; free(*top); *top = next; return res; } int main() { char* input = "aab"; // char* target = "bbabaa"; // 11th try char* target = "abbaa"; // 5th try // char* target = "bababab";// has no solution #define cRules 2 char* from[cRules] = {"ab", "b"}; // ab->bba and b->ba char* to[cRules] = {"bba", "ba"}; struct list_s* current = 0; struct list_s* nextLayer = 0; char* inputAlloc = malloc(strlen(input)); strcpy(inputAlloc, input); push(&current, inputAlloc); int counter = 0; while(current) { // = while not empty char* cur = pop(&current); int lenCur = strlen(cur); printf("%s:\n", cur); int iRule=0; for(; iRule%s\n", mod); if(!strcmp(mod, target)) { printf("DONE\n"); return 0; } push(&nextLayer, mod); ++pos; } } free(cur); if(!current) { // next round! current = nextLayer; nextLayer = 0; } ++counter; // here you can add some of the fail-conditions we talked about if(counter==100) { printf("heuristic: no solution\n"); return 0; } } return 0; }