如何在c中创建一个n-ary树

#include  #include  struct node{ char *word; int depth, children; struct node **child; }; typedef struct node node; node *createTree(); node *createNode(char *word,int depth); int main(int argv,char *argc[]){ node *root,*current_node; root=createNode("root",0); char *array[]={"string1","string2","string3"}; current_node=root; printf("root has been created with word: %s \n",current_node->word); int i; for (i=0; ichild[i]=createNode(array[i],(current_node->depth)+1); current_node->children++; printf("%s has been inserted to the tree\n",current_node->word); } } node *createTree(){ printf("root has been created\n"); return createNode("",0); /*creates the first node*/ } node *createNode(char *word,int depth){ node *new_node; new_node=malloc(sizeof(node)); new_node->word=word; new_node->depth=depth; new_node->children=0; new_node->child=NULL; } 

所以我在这里要做的是构建一个n-ary树。 我使用createNode函数来创建root的子项，但是当我尝试将新节点的地址链接到子节点时，程序会因分段错误而崩溃。 我知道我的错误可能是，我试图创造孩子的方式，但我找不到。 帮助任何人？

Answer 1

在使用它之前，只需为child结构成员分配内存：

 current_node->child = malloc(3 * sizeof(node *)); for (i=0; i<3; i++) { current_node->child[i] = createNode(array[i],(current_node->depth)+1); current_node->children++; printf("%s has been inserted to the tree\n",current_node->word); } 

您定义的结构意味着您必须将每个级别作为具有潜在动态元素数量的节点数组进行管理。 用于C中的n元树表示的更常见结构将是：

 struct node { char *word; int depth, children; // Reconsider if you need these // for maintenance effort versus benefit struct node *child; // point to children of this node struct node *next; // point to next node at same level }; 

所以结构看起来像这样：

 Root -> NULL | V Child-1.1 -> Child-1.2 -> ... -> Child-1.n -> NULL | | | | VV | ... Child-1.n.1 -> ... -> NULL V Child-1.1.1 -> Child-1.1.2 -> ... -> NULL | ... etc 

然后，您需要修改createNode并相应地编写其他树管理例程。 它们可能看起来的部分和非常简洁的样本（不一定包含所有正确的有效性检查或节点删除/解除分配）：

 struct node { int data; struct node *next; struct node *child; }; typedef struct node node; node * new_node(int); node * add_sibling(node *, int); node * add_child(node *, int); int main(int argc, char *argv[]) { int i; node *root = new_node(0); for ( i = 1; i <= 3; i++ ) add_child(root, i); } node * new_node(int data) { node *new_node = malloc(sizeof(node)); if ( new_node ) { new_node->next = NULL; new_node->child = NULL; new_node->data = data; } return new_node; } node * add_sibling(node * n, int data) { if ( n == NULL ) return NULL; while (n->next) n = n->next; return (n->next = new_node(data)); } node * add_child(node * n, int data) { if ( n == NULL ) return NULL; if ( n->child ) return add_sibling(n->child, data); else return (n->child = new_node(data)); } 

Answer 2

一些可能有用的附加function

 void remove_node(node* node, node* new_root) { if(node->parent != NULL) remove_node(node->parent, new_root) if(node->next != NULL) remove_node(node->next, new_root) if((node->child != NULL) && (node->child != new_root)) remove_node(node->child, new_root) free(node) } // new root must be element of the tree void new_root_tree(node **root, node *new_root) { *root = new_root remove_node(new_root->parent); remove_node(new_root->next); }