C++非二叉树类实现问题：添加子节点后无法正确展示

问题根源 #

你遇到的问题核心在于对象拷贝：

• addChild方法中，children.push_back(child)会将传入的child对象完整拷贝一份存入向量，而非引用或指向原对象的指针。
• 当你先执行a.addChild(tmp1)再给tmp1添加tmp2时，修改的是栈上的原tmp1对象，但a的children向量里存储的是tmp1的拷贝，这个拷贝并没有tmp2子节点，所以printTree无法输出这条边。
• 反过来先给tmp1加tmp2再加入a，拷贝时已经包含了tmp2，因此能正常显示。

解决方案 #

要实现动态更新已添加子节点的需求，必须让树节点之间共享同一对象实例，改用指针存储子节点是唯一可行的方案，推荐使用智能指针避免内存泄漏。

方案1：使用shared_ptr（推荐） #

修改类定义与实现，用智能指针管理子节点：

#include <iostream>
#include <vector>
#include <queue>
#include <memory>

// 继承enable_shared_from_this以在成员函数中获取自身的shared_ptr
class Tree : public std::enable_shared_from_this<Tree> {
private:
    int root;  
    std::vector<std::shared_ptr<Tree>> children;  

public:
    Tree(int root);
    int getRoot();
    std::vector<std::shared_ptr<Tree>> getChildren();
    void addChild(std::shared_ptr<Tree> child);
    void printTree();
};

Tree::Tree(int root){
    this->root = root;
}

int Tree::getRoot(){
    return root;
}

std::vector<std::shared_ptr<Tree>> Tree::getChildren(){
    return this->children;
}

void Tree::addChild(std::shared_ptr<Tree> child){
    children.push_back(child);
}

void Tree::printTree(){
    std::queue<std::shared_ptr<Tree>> nextToPrint;

    std::cout << "Edges:" << std::endl;
    nextToPrint.push(shared_from_this());
    while (!nextToPrint.empty()) {
        auto current = nextToPrint.front();
        nextToPrint.pop();
        for (auto& child : current->getChildren()){
                nextToPrint.push(child);
                std::cout << "{" << current->getRoot() << ", " << child->getRoot() << "}" << std::endl;
        }
    }
    std::cout << std::endl;
}

使用示例：

int main() {
    auto a = std::make_shared<Tree>(5);
    auto tmp1 = std::make_shared<Tree>(1);
    auto tmp2 = std::make_shared<Tree>(2);
    auto tmp3 = std::make_shared<Tree>(3);

    a->addChild(tmp1);
    tmp1->addChild(tmp2);
    a->addChild(tmp3);

    a->printTree();
    return 0;
}

方案2：使用原始指针（需手动管理内存） #

如果不想用智能指针，可改用原始指针，但必须手动处理内存释放：

#include <iostream>
#include <vector>
#include <queue>

class Tree {
private:
    int root;  
    std::vector<Tree*> children;  

public:
    Tree(int root);
    ~Tree(); // 析构函数释放子节点内存
    int getRoot();
    std::vector<Tree*> getChildren();
    void addChild(Tree* child);
    void printTree();
};

Tree::Tree(int root){
    this->root = root;
}

Tree::~Tree(){
    // 递归释放所有子节点
    for (auto child : children) {
        delete child;
    }
}

int Tree::getRoot(){
    return root;
}

std::vector<Tree*> Tree::getChildren(){
    return this->children;
}

void Tree::addChild(Tree* child){
    children.push_back(child);
}

void Tree::printTree(){
    std::queue<Tree*> nextToPrint;

    std::cout << "Edges:" << std::endl;
    nextToPrint.push(this);
    while (!nextToPrint.empty()) {
        Tree* current = nextToPrint.front();
        nextToPrint.pop();
        for (Tree* child : current->getChildren()){
                nextToPrint.push(child);
                std::cout << "{" << current->getRoot() << ", " << child->getRoot() << "}" << std::endl;
        }
    }
    std::cout << std::endl;
}

使用示例：

int main() {
    Tree* a = new Tree(5);
    Tree* tmp1 = new Tree(1);
    Tree* tmp2 = new Tree(2);
    Tree* tmp3 = new Tree(3);

    a->addChild(tmp1);
    tmp1->addChild(tmp2);
    a->addChild(tmp3);

    a->printTree();

    // 释放根节点即可递归释放所有子节点
    delete a;
    return 0;
}

总结 #

你的问题既不是打印函数逻辑错误，也不是类设计逻辑错误，而是子节点的存储方式导致对象状态无法共享。改用指针存储子节点后，所有操作都会作用于同一对象实例，就能实现动态更新已添加子节点的需求。

内容的提问来源于stack exchange，提问作者kasimaru13