c++ - 二叉搜索树不添加到根的右侧

Question

我正在编写一个模板化的二叉搜索树类，我用来创建二叉搜索树的函数如下：

void insert(const Comparable & x, BinaryNode<Comparable> * & t)
    {
        if (t==NULL)
            t = new BinaryNode<Comparable>(x, NULL, NULL);

        else if (x < t->element)
            insert(x, t->left);
        else if (x>t->element)
            insert(x, t->right);
        else
            ; // Duplicate; 
    }

BinaryNode 是另一个模板类，如下所示：

template <class Comparable>
class BinaryNode
{
public:
    Comparable element;
    BinaryNode *left;
    BinaryNode *right;

    BinaryNode(const Comparable & theElement,
        BinaryNode *lt, BinaryNode *rt)
        : element(theElement), left(lt), right(rt) { }
};

问题是，每当我创建一棵新树时，它都会将第一个元素添加为根。然后，即使我要添加的下一个元素大于它添加到根左侧的根。对于树左侧的元素，不会出现此问题，它会在必要时将其适当地添加到右侧。你能帮我吗？

编辑：问题解决了。我正在逐行读取文件并将这些行存储到节点中，结果发现 getline 以一种以奇怪字符开头的方式获取文件的第一行 - 即使不存在任何字符。这些字符总是比其他普通字母具有更大的价值，因此它总是在树的左边。

标签： c++templatesbinary-search-tree