问题描述
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
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)<0 ){
if ( (*ptr)->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;
}
以上是一个简化的程序,一些定义code给出,所以我不能改变的基本结构,如表,表,节点,tree_ptr,而另一些人可以改变。
我想实现是一个拼写检查,存储在树和树的其他一些属性(此处省略)的头表,树被实现为一个有序的二叉树。
The above is a simplified program, some definition code is given, so I could not change the basic structure, like table, Table, node, tree_ptr, while others could be changed.What I am trying to implement is a spellchecking, the table stored the head of the tree and some other properties of the tree(which is omitted here), the tree is implemented as an ordered binary tree.
我发现,插入()效果很好最多两次的(* PTR)后=(* PTR) - >右键;在T->头部被改变了。因此,使用它两次之后,我失去了树头。
I find that, insert() works well up to two times, after the (*ptr) = (*ptr)->right; the t->head is changed as well. So after using it two times, I lost the head of the tree.
如何修改我的插入()?
How to modify my insert()?
推荐答案
要插入一个节点到一棵树,你首先要寻找一个空的叶子。除了这个,你不要修改 T
,所以没有必要通过返回值写回的:
To insert a node into a tree you first have to search for an empty leaf. Apart from this you do not modify t
, so there is no need of writing it back by return value:
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;
}
通过这个递归函数可以打印你的树:
With this recursive function you can print your tree:
void printTree( tree_ptr ptr )
{
if ( ptr == NULL )
return;
printTree( ptr->left );
printf( "%s\n", ptr->element );
printTree( ptr->right );
}
printTree( t->head );
和这一个,你可以免费
你的树的所有节点:
And with this one you can free
all nodes of your tree:
void deleteTree( tree_ptr ptr )
{
if ( ptr == NULL )
return;
deleteTree( ptr->left );
deleteTree( ptr->right );
free( ptr );
}
deleteTree( t->head );
t->head = NULL;
这篇关于嵌套结构的指针的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!