0

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

例如：

给定一个字符串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");

}

这适用于第一级。但我正在寻找一种方法，可以对每个节点和该节点的子节点执行相同的操作。所以，我从原点开始，找到所有的转换，然后为到达转换做同样的事情。我看不到如何递归地做到这一点......

谢谢！

4

1 回答 1

1

对于“广度优先”，您可能想查看通用二叉树（可以为任何树构造），其中每个节点都链接到first-child和next-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，您将遵循下一个指针并调用addTransformationsToNode每个孩子（我会在循环中执行此操作）。然后，您可以递归并为每个孩子的孩子做同样的事情。

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

我尝试编写函数并感到困惑。我认为您的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);
    }
}
于 2013-02-23T18:40:31.567 回答