在 C++ 中实现树

Question

我想实现一个二叉树，其中每个节点都包含 left 和 right 子树。这是我的 class 的样子：

class KDTree
{
public:
    KDTree(...);   
    ~KDTree();

private:
    LatLng element; // The value of the node
    KDTree left;    // The left sub-tree
    KDTree right;   // The right sub-tree
};

然后我的构造函数如下所示：

KDTree::KDTree(...)
{   
    value = ...;
    if(not_finished)
    {
        left  = KDTree(...);
        right = KDTree(...);
    }
    else
    {
        left = NULL; // how to implement this properly ?
        right= NULL; // how to implement this properly ?
    }
}

如果我尝试像上面显示的那样放置 NULL，那么编译器会抱怨 left 和 right 属性未初始化。我怎样才能正确地做到这一点？

Answer 1

左右应该是这样的 KDTree 指针：KDTree* 左，KDTree* 右。然后 Null 将按原样工作

此外，您可能需要更改第一个 if 语句

left = KDTree (...);
right = KDTree (...);

至

left = new KDTree (...);
right = new KDTree (...);

Answer 2

示例不完整，所以我只是根据我所看到的进行猜测。

KDTree left 和 KDTree right 是对象，不是指针。所以你不能给他们分配 NULL 。尝试将它们变成指针：

class KDTree
{
    public:
        KDTree(...);   
        ~KDTree();
        // Note: You'll have to clean up your left and right trees in the destructor!

    private:
        LatLng element;   // The value of the node
        KDTree * left;    // The left sub-tree
        KDTree * right;   // The right sub-tree
};


KDTree::KDTree(...)
{   
    value = ...;
    if(not_finished)
    {
        left  = new KDTree(...); // recursive constructor call (nuh-uh! see below)
        right = new KDTree(...); // recursive constructor call (nuh-uh! see below)
    }
    else
    {
        left = NULL; // how to implement this properly ?
        right= NULL; // how to implement this properly ?
    }
}

附加信息：我看到了您的 "recursive constructor call" 评论。这不太对。在您的原始代码中，left = KDTree(...); 确实 而不是 递归调用您的构造函数。它只是将一个新的 KDTree 分配给 left （我猜 KDTree 有一个赋值运算符）。

在 C++ 中实现树

Implementing trees in c++

c++

tree