c - 二叉树搜索是在骗我吗？

Question

嘿，我正在尝试编写一个程序，该程序将采用字符串列表(这些是按顺序排列的):

polymorphism
object
templates
structure
class
pointer
reference
traversal
inheritance
exceptions
recursive
overloading

然后将这些字符串存储到二叉树中，最后进行中序遍历。但是，我遇到了一个我无法弄清楚的问题。我添加节点的函数不断告诉我我已经添加了该节点，但是它实际上从未被添加？我的输出是这样的:

ADDED NODE: polymorphism
ERROR: Same Data: object, object
ERROR: Same Data: templates, templates
ERROR: Same Data: structure, structure
ERROR: Same Data: class, class
ERROR: Same Data: pointer, pointer
(etc...)
ERROR: overloading, overloading
ERROR: overloading, overloading
FINISHED BUILDING

overloading

最后，这是源代码:

#include <stdlib.h>
#include <stdio.h>

struct tree {
    char* data;
    struct tree *left;
    struct tree *right;
};

void buildTree(struct tree**);
void printAlpha(struct tree*);
void insert(struct tree **root, char *n);

int main(int argc, char* argv[]) {
    struct tree* myTree = NULL;

    buildTree(&myTree);
    printf("FINISHED BUILDING\n\n");
    printAlpha(myTree);

    system("PAUSE");
    return 0;
}

/*Builds tree from text file*/
void buildTree(struct tree **root) {
    FILE* fIn = fopen("./in.txt", "r");
    char* input = (char*) malloc(sizeof(char));

    if(!fIn) {
        printf("ERROR: Cannot find file\n");
        return;
    }

    while(!feof(fIn) && fscanf(fIn, "%s", input)) {
        // printf("INP:%s\n", input);
        insert(root, input);
    }
}

void insert(struct tree **root, char *n) {
    if (*root == NULL) {
        // found the spot, create and insert the node
        struct tree *newNode = NULL;
        newNode = (struct tree*) malloc(sizeof(struct tree) );
        newNode->data = n;
        newNode->left = NULL;
        newNode->right = NULL;
        *root = newNode;

        printf("ADDED NODE: %s\n", newNode->data);
    }

    else if(strcmp(n, (*root)->data) < 0)
    insert(&((*root)->left), n);
    else if(strcmp(n, (*root)->data) > 0)
    insert(&((*root)->right), n);
    else
    printf("ERROR: Same data: %s, %s\n", (*root)->data, n);
}

/*In order traversal*/
void printAlpha(struct tree *root) {
    struct tree *curNode = root;

    /*If empty something went wrong*/
    if(!curNode) {
        printf("Error: Binary Tree Is Empty!\n");
        //  return;
    }

    if(curNode->left != NULL) {
        printAlpha(root->left);
    }

    printf("%s\n", curNode->data);

    if(curNode->right != NULL) {
        printAlpha(curNode->right);
    }
}

Answer 1

您正在创建一个字符串 (char* input = (char*) malloc(sizeof(char));) 并每次都覆盖其内容。您将这个单个字符串插入到树中，然后下次将其与自身进行比较。

解决方案:将 malloc 移至循环内。