c++ - 在节点中使用原始指针，在树中使用 unique_ptr

Question

我是一名业余程序员，试图找到合适的位置将 unique_ptr 放入我的二叉树中。最初，我对左右子节点使用 unique_ptr，但这“意味着”每个节点“拥有”每个后续节点。我在 previous post 中被告知树应该拥有它的节点。这是我对这个问题的解决方案:所有的树节点都存储在一个唯一指针的 vector 中，unique_ptr::get 用于提取以通常方式使用的原始指针(示例添加).

#include "pch.h"
#include <iostream>
#include <sstream>
#include <string>
#include <memory>
#include <vector>
#include <unordered_map>

class Node
{
public:
    Node(int data = 0) : data_(data), left_child(nullptr), 
        right_child(nullptr) {}

    int data_;
    Node *left_child;
    Node *right_child;
};

class Tree
{
public:
    Tree(int data = 0) {
        store.emplace_back(std::make_unique<Node>(data));
        root = store.at(0).get();
    }
    void add(int data) {
        Node *index = root;
        while (true) {
            if (data == index->data_) {
                std::stringstream ss;
                ss << data << " already exists\n";
                throw std::invalid_argument(ss.str());
            }
            if (data < index->data_) {
                if (index->left_child != nullptr) {
                    index = index->left_child;
                    continue;
                }
                std::unique_ptr<Node> temp = std::make_unique<Node>(data);
                index->left_child = temp.get();
                store.push_back(std::move(temp));
                return;
            }
            if (index->right_child != nullptr) {
                index = index->right_child;
                continue;
            }
            std::unique_ptr<Node> temp = std::make_unique<Node>(data);
            index->right_child = temp.get();
            store.push_back(std::move(temp));
            return;
        }
    }
private:
    std::vector<std::unique_ptr<Node>> store;
    Node* root;
};

删除节点似乎会非常缓慢。在树中查找值(快)，在 std::vector 中查找指针(慢)，从 vector 中删除条目，最后从父项中删除指针。我在正确的轨道上吗？如果没有，欢迎提供提示。

Answer 1

对 child 使用 std::unique_ptr 是快速而肮脏的解决方案，但它不符合问题的要求。由于复杂的代码和涉及的时间复杂性，将指针放入 vector 中不是一个好主意。

快速而肮脏的解决方案是在树中编写一个函数，它将递归地删除节点。如果树不平衡(就像子级上的 std::unique_ptr 一样)，缺点是可能会出现堆栈溢出。有几种方法可以解决潜在的堆栈溢出问题:

有效的解决方案，没有堆栈溢出，也没有 std::bad_alloc 异常的可能性。它是一种 DFS 算法，使用释放的树节点作为堆栈。 Node::left 条目将指向有效负载(要释放的子树)，而 Node::right 将在 DFS 堆栈(链表)中扮演 next 的角色。

static Node * & nextNode(Node & node)
{ return node.right_child; }
static Node * & payload(Node & node)
{ return node.left_child; } 

Tree::~Tree()
{
    Node temp;
    Node *stack = & temp;
    payload(*stack) = root;
    nextNode(*stack) = nullptr;
    constexpr bool TRACE = false;

    while (stack) {
        Node * treeNode = payload(*stack);
        Node * toPush1 = treeNode->left_child;
        Node * toPush2 = treeNode->right_child;
        if (toPush1) {
            payload(*stack) = toPush1;
            if (toPush2) {
                payload(*treeNode) = toPush2;
                nextNode(*treeNode) = stack;
                stack = treeNode;
            } else {
                if (TRACE) std::cout << treeNode->data_ << " ";
                delete treeNode;
            }
        }
        else if (toPush2) {
            payload(*stack) = toPush2;
            if (TRACE) std::cout << treeNode->data_ << " ";
            delete treeNode;
        }
        else { // nothing to push 
            Node *nextStack = nextNode(*stack);
            if (TRACE) std::cout << treeNode->data_ << " ";
            delete treeNode;
            if (stack != &temp) {
                if (TRACE) std::cout << stack->data_ << " ";
                delete stack;
            }
            stack = nextStack;
        }
    }
    // free the stack.
    while (stack) {
        Node *nextStack = nextNode(*stack);
        if (stack != &temp) {
            if (TRACE) std::cout << stack->data_ << " ";
            delete stack;
        }
        stack = nextStack;
    }
    if (TRACE) std::cout << '\n';
}

这将使您既提高内存效率，增加 O(1) 的内存，又提高时间效率，时间复杂度为 O(N)。

为了完整起见，这里是 Tree 类的其余部分:

class Tree
{
public:
    Tree(int data = 0) {
        root = new Node(data);
    }
    ~Tree();
    Copy ctor, assignment, move ctor, move assignment

    void add(int data) {
        Node *index = root;
        while (true) {
            if (data == index->data_) {
                std::stringstream ss;
                ss << data << " already exists\n";
                throw std::invalid_argument(ss.str());
            }
            if (data < index->data_) {
                if (index->left_child != nullptr) {
                    index = index->left_child;
                    continue;
                }
                std::unique_ptr<Node> temp = std::make_unique<Node>(data);
                index->left_child = temp.release();

                return;
            }
            if (index->right_child != nullptr) {
                index = index->right_child;
                continue;
            }
            std::unique_ptr<Node> temp = std::make_unique<Node>(data);
            index->right_child = temp.release();

            return;
        }
    }
private:
    // owning the root and all descendants recursively
    Node* root;
};