带指针的嵌套结构

#include  #include  #include  typedef struct node *tree_ptr; typedef struct table * Table; struct node { char* element; tree_ptr left, right; }; typedef struct table { tree_ptr head; int tree_h; }table; char* key = NULL; Table insert(char* insert_key,Table t) { int height = 0; //tree_ptr ptr = t->head; tree_ptr *ptr = &(t->head); key = strdup(insert_key); tree_ptr new_node = malloc(sizeof(struct node)); new_node->element = key; new_node->left = NULL; new_node->right = NULL; if ( t->head==NULL ){ *ptr = new_node; t->tree_h = 0; printf("head:%s\n",t->head->element); return t; } while(1){ if ( strcmp(insert_key, (*ptr)->element)left ==NULL ){ (*ptr)->left = new_node; height++; if ( height > t->tree_h) t->tree_h = height; break; } else{ (*ptr) = (*ptr)->left; height++; } } else if ( strcmp(insert_key, (*ptr)->element)>0 ){ if ( (*ptr)->right ==NULL ){ (*ptr)->right = new_node; height++; if ( height > t->tree_h) t->tree_h = height; break; } else{ (*ptr) = (*ptr)->right; height++; } } else break; } return t; } int main() { Table t = malloc(sizeof(table)); t->head = NULL; t = insert("one", t); t = insert("two", t); t = insert("three", t); printf("%s\n",t->head->element); return 0; } 

以上是一个简化的程序，给出了一些定义代码，因此我无法更改基本结构，如表，表，节点，tree_ptr，而其他可以更改。 我想要实现的是拼写检查，表存储树的头部和树的一些其他属性（这里省略），树被实现为有序二叉树。

我发现，在（* ptr）=（* ptr） – > right之后，insert（）最多可以工作两次; t->头也改变了。 因此，在使用它两次之后，我失去了树的头部。

如何修改我的insert（）？

Answer 1

要将节点插入树中，首先必须搜索空叶。 除此之外，你不要修改t ，所以不需要通过返回值写回：

 void insert( char* insert_key, Table t ) { // serach empty leaf, where to insert the new node tree_ptr *ptr = &(t->head); // start at head while ( *ptr != NULL ) // end if empty leaf is found { int cmpRes = strcmp( insert_key, (*ptr)->element ); if ( cmpRes == 0 ) return; // insert_key already is member of tree if ( cmpRes < 0 ) ptr = &((*ptr)->left); // step down to left child else ptr = &((*ptr)->right); // step down to right child } // create new node tree_ptr new_node = malloc( sizeof(struct node) ); new_node->element = strdup( insert_key ); new_node->left = NULL; new_node->right = NULL; // place new node at empty leaf *ptr = new_node; } 

使用此递归function，您可以打印您的树：

 void printTree( tree_ptr ptr ) { if ( ptr == NULL ) return; printTree( ptr->left ); printf( "%s\n", ptr->element ); printTree( ptr->right ); } printTree( t->head ); 

使用这个，您可以free树的所有节点：

 void deleteTree( tree_ptr ptr ) { if ( ptr == NULL ) return; deleteTree( ptr->left ); deleteTree( ptr->right ); free( ptr ); } deleteTree( t->head ); t->head = NULL; 

Answer 2

问题是ptr指向结构节点的指针的地址，而不是直接指向结构节点：

 tree_ptr *ptr = &(t->head); 

然后在while循环中迭代时，你不是在改变指针ptr ，而是指向它指向的指针，即t->head ：

  (*ptr) = (*ptr)->left; 

这会在每次迭代时覆盖指针t->head ，有效地擦除指针指向的节点，并泄漏内存。

而是使用指向struct节点的普通指针：

 struct node* iter = t->head; ... if ( strcmp(insert_key, iter->element)<0 ){ ... } else{ iter = iter->left; .... 

---

我强烈建议删除隐藏指针的那些typedef，因为它们使代码难以阅读并模糊类型，这在这种情况下是不可取的：

 typedef struct node *tree_ptr; typedef struct table * Table; 

---

另请注意，如果循环发现重复，则不会释放分配的节点，从而泄漏内存。