我正在尝试编写一个程序,将带有成员字符串的节点插入到BST中,然后打印有关该BST的信息,如高度,顺序遍历,叶子数等等...
到目前为止,当我进行inorder遍历时,它会打印输入的最后一个字符串作为根,即使它应该在树的底部 .
这是代码:
插入功能:
void insert_node(Node* root, char *nextString) {
int newLessThanRoot = strcmp( root->Word, nextString ) > 0 ? 1 : 0; // test if nextString is left or right from root
if (newLessThanRoot && root->Left != NULL) {
return insert_node(root->Left, nextString);
}
if (!newLessThanRoot && root->Right != NULL) {
return insert_node(root->Right, nextString);
}
Node* freshNode = newNode();
freshNode->Word = malloc(strlen(nextString) +1);
strcpy(freshNode->Word, nextString);
freshNode->Left = NULL;
freshNode->Right = NULL;
if (newLessThanRoot) {
root->Left = freshNode;
}
else {
root->Right = freshNode;
}
}
inorder遍历功能:
void inorder(Node *temp) {
if (temp != NULL) {
inorder(temp->Left);
printf("%s ",temp->Word);
inorder(temp->Right);
}
}
如何使用它们:
char inputString[15];
char *inputStringPtr = &inputString[0];
Node* root;
root = newNode();
fscanf(infile,"%s",inputStringPtr);
root->Word = inputString;
//printf("Root's word: %s\n",root->Word);
while (fscanf(infile,"%s",inputStringPtr) == 1) {
insert_node(root,inputStringPtr);
printf("%s\n",inputString);
}
int numberOfStrings = num_of_strings(root);
int heightOfBST = height_of_tree(root);
int numberOfLeaves = num_of_leaves(root);
inorder(root);
输入看起来像这样:
b a c e d l m n o p z
所以输出(在执行inorder遍历时)应该是:
a b c d e l m n o p z
但相反,它是:
z a c d e l m n o p z
2 回答
在这里,您可以读取根节点的值:
在这里,您使用第二个节点的值再次覆盖它:
您可以使用strdup()来创建根值的副本:
这应该可以解决您的问题 .
在
insert_node()
中,您正确复制了每个新节点的值 . 您可以考虑在那里使用strdup()
,而不是malloc(strlen())/ strcpy() .您的inOrder函数和insert_node函数没有问题 . 用法有一些问题 . 在线
您将本地商店地址分配给root . 随着本地存储的不断变化,根Word也会发生变化 .