二叉树：寻找相同的值

Question

我一直在慢慢编写程序并尝试自学二叉树。这个程序是一本 phone 的书，它使用树来存储它的数据。我目前停留在我的 findOrInsert 函数上。最初我只是将数据插入一个开放区域。现在我想在添加之前检查该数据是否已经存在。如果确实如此，则只是 return 提示用户的功能已经存在相同的数据。我尝试了一些东西，但没有运气。我可能只是尝试从头开始重写它。在那之前我想看看我是否能得到任何帮助。

这是我目前拥有的。

struct treeNode * findOrInsert(struct treeNode *p, Entry e) {

    if (p == NULL) {
        p = createNode(NULL, NULL, e);
    }
    else if (strcmp(e.fName, p->data.fName) < 0) {
        p->left = findOrInsert(p->left, e);
    }
    else if (strcmp(e.fName, p->data.fName) > 0) {
        p->right = findOrInsert(p->right, e);
    }
    else {
        if (strcmp(e.lName, p->data.lName) < 0) {
            p->left = findOrInsert(p->left, e);
        }
        else if (strcmp(e.lName, p->data.lName) > 0) {
            p->right = findOrInsert(p->right, e);
        }
        else {
            return p;
        }
    }
    return p;
}

struct treeNode * createNode(struct treeNode *q, struct treeNode *r, Entry e) {
     struct treeNode * newNode;
     newNode = (struct treeNode*)(malloc(sizeof(struct treeNode)));
     newNode->data = e;
     newNode->left = q;
     newNode->right = r;
     return newNode;
}

感谢任何帮助！

Answer 1

为什么不在

之后简单地添加另一个检查

if (p == NULL) {
    p = createNode(NULL, NULL, e);
}

看p和e的名字和姓氏是否相等？（当然假设树中的每个条目都有名字和姓氏）。我在这条语句之后说是因为您不想将空对象与 e 进行比较。所以一旦你确认 p 确实存在，你应该检查 e 的名字和姓氏是否与 p 的名字和姓氏相同。如果是这样，则打印出 e 已经存在于树中或其他任何内容，并打印出 return p 以结束递归（returning 的替代方法是抛出异常但这会停止程序的执行）。它应该看起来像这样，

else if (strcmp(e.fName, p->data.fName) == 0 && strcmp(e.lName, p->data.lName) == 0) {
    printf("Entry already exists in tree");
    return p;
}

二叉树：寻找相同的值

Binary Tree: Finding the same values

c

insert

find

binary-search-tree

data-structures