c - 二叉树插入错误

Question

我查看了几篇 BST Insert 文章，但没有一篇与我的结构相同或遇到相同的问题。

我的问题是我的二叉树构建不正确。这真的很奇怪，因为我从以前的项目中复制并粘贴了大部分代码，它工作正常，唯一的区别是节点包含的数据，并且循环遍历树的条件使用 strcmp 而不是整数比较。

这是我的插入函数:

//insert parameter node data into a Binary Tree
TreeNodePtr insertNode(BinaryTree bst, Record d)
{
    //if root is null insert into root
    if(bst.root == NULL)
    {
        bst.root = (TreeNodePtr) malloc(sizeof(TreeNode));
        bst.root->data = d;
        bst.root->left = NULL;
        bst.root->right = NULL;
        return bst.root;
    }

    //we need to traverse the tree so declare a pointer "curr" to do so
    TreeNodePtr curr = (TreeNodePtr) malloc(sizeof(TreeNode));
    curr = bst.root;

    //loop until we find an appropriate empty space or a match (no duplicates)
    while (strcmp(d.lastName, curr->data.lastName) != 0)
    {
        if (strcmp(d.lastName, curr->data.lastName) < 0)
        { // if left
            if(curr->left==NULL) 
            {
                curr->left = (TreeNodePtr) malloc(sizeof(TreeNode));
                curr->left->data = d;
                curr->left->left = NULL;
                curr->left->right = NULL;
                return bst.root;
            }
            curr=curr->left;
        }
        else if (strcmp(d.lastName, curr->data.lastName) > 0)
        { // try right
            if(curr->right==NULL)
            {
                curr->right = (TreeNodePtr) malloc(sizeof(TreeNode));
                curr->right->data = d;
                curr->right->left = NULL;
                curr->right->right = NULL;
                return bst.root;
            }
            curr=curr->right;
        }
    }

    return bst.root;
}

这是使用插入函数构建树的主函数中的代码(请注意，记录是一个正确填充的数组，每个索引包含一个节点的数据):

//declare BST and build it
BinaryTree phoneTree;
phoneTree.root = NULL;

for (int i=0; i < sizeof(records) / sizeof(Record); i++)
{
    Record tmpRecord;
    tmpRecord.firstName = records[i].firstName;
    tmpRecord.lastName = records[i].lastName;
    tmpRecord.phoneNum = records[i].phoneNum;
    phoneTree.root = insertNode(phoneTree, tmpRecord);
}

作为引用，这里是树结构:

//phone data record struct
typedef struct
{
    char *firstName;
    char *lastName;
    char *phoneNum;
}Record;

//define the tree node which contains the data
typedef struct treeNode
{
    Record data;
    struct treeNode *left,*right;
}TreeNode,*TreeNodePtr;

//define binary tree struct
typedef struct
{
    TreeNodePtr root;
}BinaryTree;

我已经盯着运行的程序并将其与该程序进行了大约 5 个小时的比较，但我无法弄清楚哪里出了问题。我知道树没有正确填充，因为如果我尝试打印 phoneTree.root->right.data 或 phoneTree.root->left.data 属性，程序会崩溃。在我借用代码的程序中，这些属性打印时没有错误。根仍然正确插入，并且可以打印它的属性。

非常感谢任何关于我做错了什么的见解。

Answer 1

有一个明显的错误，可能会给您带来麻烦。您需要通过引用传递“bst”，以便该函数可以修改“bst.root”。尝试将函数重写为:

 TreeNodePtr insertNode(BinaryTree* bst, Record d)

并使用“bst->”代替“bst”。

您说过它适用于整数。现在这可能是另一个错误的线索。您的记录仅包含指向字符串的指针。这些指针在树的整个生命周期中是否保持有效？也许您需要复制记录中的字符串。

其他一些小事:

//we need to traverse the tree so declare a pointer "curr" to do so
TreeNodePtr curr = (TreeNodePtr) malloc(sizeof(TreeNode));
curr = bst.root;

这里malloc是多余的，结果马上被覆盖

和:

    }
    else if (strcmp(d.lastName, curr->data.lastName) > 0)
    { // try right

您可以将其替换为“} else {”，因为您已经执行了此 strcmp 操作。