如何修复基于BST的图中顶点被重复覆盖的问题？

尝试将二叉搜索树（BST）知识应用到图结构中，用两个结构体和一个类实现：Edge结构体、Vertex结构体，Graph类作为BST节点存储Vertex。当前程序仅能获取BST节点的value，但无法正确存储Vertex的name，所有节点的name都被覆盖为同一个值。

相关代码如下：

结构体与类定义 #

// Vertex node stores name and neighbors
struct Vertex {
    string name;
    vector<Edge *> *neighbors;
};

class Graph {
    // Functions like BST and stores a Vertex object with each node
    int value;
    Graph *left, *right;
    struct Vertex *node;
    // 此处省略其他成员函数声明
};

构造函数实现 #

Graph::Graph() : value(0), left(NULL), right(NULL), node(){};

Graph::Graph(int data, Vertex* node) {
    value = data;
    left = right = NULL;
    Vertex* newNode = new Vertex;
    newNode = node;
};

addVertex函数实现 #

Graph* Graph::addVertex(Graph* root, string name, int data){
    if (!root) {
        Vertex* newVertex = new Vertex;
        newVertex->name = name;
        newVertex->neighbors = new vector<Edge *>();
        node = newVertex;
        return new Graph(data, node);
    }
    if (value > root->value){
        root->right = addVertex(root->right, name, data);
    }
    else if (value < root->value){
        root->left = addVertex(root->left, name, data);
    }
    return root;
};

程序输出示例：

Vertex name: g Graph Node Value: 3
vertex name: g Neighbors:
Vertex name: g Graph Node Value: 2
vertex name: g Neighbors:
Vertex name: g Graph Node Value: 1
vertex name: g Neighbors:

1. 构造函数的无效操作 #

带参构造函数中，newNode = node;属于无效代码：先创建了新的Vertex对象，随后立刻将指针指向传入的node，既造成内存泄漏，也没有把传入的node赋值给Graph类的成员变量。正确写法：

Graph::Graph(int data, Vertex* node) {
    value = data;
    left = right = NULL;
    this->node = node; // 直接赋值给类成员变量
};

2. addVertex函数的逻辑错误 #

• 创建新节点时，错误修改了当前调用函数的Graph对象的node成员，而非新创建的Graph对象的node，导致所有新节点共享同一个node指针，名称被反复覆盖。
• BST插入方向判断错误：用当前对象的value和root->value比较，而非待插入的data和root->value比较，导致插入路径完全混乱。

修正后的addVertex函数：

Graph* Graph::addVertex(Graph* root, string name, int data){
    if (!root) {
        Vertex* newVertex = new Vertex;
        newVertex->name = name;
        newVertex->neighbors = new vector<Edge *>();
        // 直接创建新Graph对象并返回，无需修改当前对象的node
        return new Graph(data, newVertex);
    }
    // 用待插入的data与当前root的value比较，确定插入方向
    if (data > root->value){
        root->right = addVertex(root->right, name, data);
    }
    else if (data < root->value){
        root->left = addVertex(root->left, name, data);
    }
    // 重复值可根据需求添加处理逻辑
    return root;
};

3. 额外优化建议 #

• 给Vertex结构体添加构造函数，自动初始化neighbors，避免手动初始化出错：

struct Vertex {
    string name;
    vector<Edge *> *neighbors;
    // 构造函数自动初始化邻接表
    Vertex(string n) : name(n), neighbors(new vector<Edge*>()) {}
};

后续创建Vertex时可直接写new Vertex(name)，更简洁安全。

• 需实现析构函数，释放Vertex和neighbors容器的内存，避免内存泄漏。

内容的提问来源于stack exchange，提问作者Bran The Builder