使用 std::unique ptr 的二叉搜索树

Question

我正在尝试使用智能指针实现二叉搜索树，我读到推荐的实现方法是使用 unique_ptr，因为 parent 拥有 child 并且二叉搜索树中没有多个所有者。

以这棵树为例，

                       10
            4                      20       
      2           5          11          30
         3

这里 4 在 10 的左 child 和 2 在 4 的左 child 和 3 在 2 的右 child 等等。

现在结构看起来像，

template<typename T>
struct TreeNode {
    T data;
    std::unique_ptr<TreeNode<T>> left, right; 
};

有一个 unique_ptr<TreeNode<T>> root 指向根。

现在，如果我理解正确的话，unique_ptr's 不能被复制或分配，他们拥有 object.

的唯一所有权

所以如果我想遍历树，我不能做一些像初始化 std::unique_ptr<TreeNode<T>> temp 到根并从那里遍历每个节点的事情，因为一旦我尝试设置

就会抛出错误=16=] 这是 unique_ptr 到 temp.

那么我是否需要使用TreeNode*类型的原始指针来遍历树并执行操作？这样做好还是安全？对于我在这棵树上的所有操作，我是否必须使用原始指针？

另一个问题是删除节点。如果我说要删除值为 3 的节点。如果我初始化类型为 TreeNode* temp 的原始指针并到达 Treenode 3。那么如果我调用 delete(temp) 会发生什么？来自 TreeNode 2 的 unique_ptr 指向 TreeNode 3。这个指针会发生什么？

Answer 1

Then if I call delete(temp) what will happen?

TreeNode将被摧毁。请注意 delete 不需要括号

A unique_ptr from TreeNode 2 is pointing at TreeNode 3. What will happen to this pointer?

指针变得无效，unique_ptr对象被销毁是未定义的行为，因为它会尝试delete一个无效的指针。

So do I need to use a raw pointer of type TreeNode* to traverse the tree and perform operations? is it good or safe to do so? For all my operations on this tree then will I have to use raw pointers?

您可以有一个 std::unique_ptr 的引用（或指针），您不需要复制它。

而不是 delete 原始指针，您可以调用 unique_ptr 的 reset 成员函数来释放指向的 TreeNode

使用 std::unique ptr 的二叉搜索树

Binary Search Tree using std::unique ptr

c++

pointers

smart-pointers

unique-ptr

binary-search-tree