c - 在 C 中构建 N 叉树(递归？)

Question

我必须构建一棵树，从字符串开始，它根据一些转换规则不断创建新节点。

例如:

给定一个字符串aab以及以下两条变换规则:

ab --> bba
b --> ba

需要构建以下树:

请注意，构建是在广度模式下完成的。在每一步中，我都会对当前节点的每个子字符串应用所有转换规则，这将是子节点。

这是我到目前为止所拥有的:

//Representing the n_ary tree
typedef struct {
    char *value;
    struct t_children_list *children;
} tree;

typedef struct t_children_list {
    tree *child;
    struct t_children_list *next;
} children_list;

void initializeNode(tree **node, char *input)
{
  if((*node = malloc(sizeof(tree))) == NULL) { abort(); }
  (*node)->value = input;
  (*node)->children = NULL;
}

void createChildrenList(children_list **children, tree *transformation)
{
    if((*children = malloc(sizeof(children_list))) == NULL) { abort(); }
    (*children)->child = transformation;
    (*children)->next = NULL;
}

//Given a node, and a needle with a replacement. It will add the childrens to that node. 
void addTransformationsToNode(tree **origin, char *needle, char *replacement)
{
    char *str = (*origin)->value;
    for (char *p = str; *p != '\0'; p++) {
       //Logic to find the value of str_... Not relevant
             tree *transformation = NULL;
            initializeNode(&transformation, str_);
            //Add node to origin children list
            // If node doesn't have children yet, create a new list
            // Otherwise, add to end of children list
            children_list *children = NULL;
            createChildrenList(&children, transformation);
            if ((*origin)->children == NULL) {
                (*origin)->children = children;
            } else {
                children_list *current = (*origin)->children;
                while (current->next != NULL) {
                    current = current->next;
                }
                current->next = children;
            }
        }
    }

  }

void main()
{
  // Create the tree
  char *input = "aab";
  char *target = "bababab";
  tree *my_tree = NULL;
  initializeNode(&my_tree, input);

  addTransformationsToNode(&my_tree, "ab", "bba");
  addTransformationsToNode(&my_tree, "b", "ba");

}

这对于第一级来说是正确的。但我正在寻找一种方法，可以对每个节点及其子节点执行相同的操作。因此，我从原点开始，找到所有转换，然后对于到达转换执行相同的操作。我不明白如何递归地执行此操作...

谢谢!

Answer 1

对于“广度优先”，您可能需要查看通用二叉树(可以为任何树构建)，其中每个节点链接到第一个子和下一个- sibling 。您可以构建二叉树(呼吸优先)，然后转换为 n 进制。

从单个字符串构建一代，您将结果放入节点列表中，通过next-sibling链接。下一代是从列表中的每个节点构建一代。

通过迭代或递归方式，您可以使用重复来协调应用于一个节点的一系列调用。

addTransformationsToNode(&my_tree, "ab", "bba");

addTransformationsToNode(&my_tree->children->child, "ab", "bba");
addTransformationsToNode(&my_tree->children->next->child, "ab", "bba");
addTransformationsToNode(&my_tree->children->next->next->child, "ab", "bba");

addTransformationsToNode(&my_tree->children->child->children->child, "ab", "bba");
addTransformationsToNode(&my_tree->children->child->children->next->child, "ab", "bba");

因此，对于body，您将遵循next指针并为每个子元素调用addTransformationsToNode(我会在循环中执行此操作) )。然后，您可以递归并对每个 child 的 child 执行相同的操作。

您需要一个额外的参数来控制递归的深度:某种结束树构造的方法。

<小时/>

我尝试编写该函数，但感到很困惑。我认为您的 children_list 结构不必要地复杂。我会从更简单的事情开始。

typedef struct tree {
    char *val;
    struct tree *first_child;
    struct tree *next_sibling;
} tree;

tree *newnode(char *val){
    tree *node;
    node = malloc(sizeof(*node));
    if (node) {
        node->val = val;
        node->first_child = NULL;
        node->next_sibling = NULL;
    }
    return node;
}

void printtree(tree *node) {
    if (node) {
        if (node->val)
            printf("%s, ", node->val);
        printtree(node->next_sibling);
        puts("");
        printtree(node->first_child);
    }
}