避免在二叉搜索树中插入重复项

Question

所以我有一个二叉搜索树，除了我不想插入重复项之外，它工作得很好。我试过想过几种方法来做到这一点，但似乎无法弄清楚。

我要做的是先调用我的搜索方法，然后再插入任何内容进行检查，如果不存在，则使用插入方法插入课程。

有人知道解决这个问题的好方法吗？我的逻辑对吗？

这是我的插入方法：

bool BinarySearchTree::treeInsert(string courseNumber, string courseTitle)
 {
Course * z = new Course(courseNumber, courseTitle);
Course *x, *y;
y = NULL;
x = root;

while (x != NULL){
    y = x;
    if(z->getCourseNumber() < y->getCourseNumber()){
        x = x->getLeft();
    } else{
        x = x->getRight();
    }
}
z->setParent(y);

if (y == NULL){
    root = z;
} else if (z->getCourseNumber() < y->getCourseNumber()){
        y->setLeft(z);
    }
    else {
        y->setRight(z);
    }
}

提前致谢

Answer 1

在循环末尾的插入方法中，当您尝试插入重复项时，y 中的课程编号将等于 z 中的课程编号。如果是这种情况，请不要做任何事情（除了删除 z 你当前分配的，即使你不需要它）。

Answer 2

我建议在循环中检查是否相等，而不是遵循 >= 的链，如果没有插入发生，return false。仅当确定将使用新元素时才会创建新元素：

 bool BinarySearchTree::treeInsert(string courseNumber, string courseTitle)
 {
     Course *x=root, *y=nullptr;

     while (x != NULL) {
         y = x;
         if(courseNumber < y->getCourseNumber())
             x = x->getLeft();
         else if(courseNumber==y->getCourseNumber()) 
             return false;
         else x = x->getRight();
     }
     Course * z = new Course(courseNumber, courseTitle);
     z->setParent(y);
     if (y == NULL)
         root = z;
     else if (z->getCourseNumber() < y->getCourseNumber())
            y->setLeft(z);
     else   y->setRight(z);
     return true; 
 }

避免在二叉搜索树中插入重复项

Avoid inserting duplicates in binary search tree

c++

insert

binary-search-tree