0

文字列から始めて、いくつかの変換規則に従って新しいノードを作成し続けるツリーを構築する必要があります。

例えば：

与えられた文字列aab と、次の 2 つの変換規則:

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-ary に変換できます。

1 つの文字列から 1 つの世代を構築し、結果をノードのリストに入れ、next-siblingでリンクします。次の世代は、リスト内の各ノードから 1 つの世代を構築することです。

繰り返しまたは再帰的に、繰り返しを使用して、1 つのノードに適用される一連の呼び出しを調整します。

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 に答える