如何修复似乎覆盖相同顶点的基于 BST 的图形？

Question

我希望这不是重复的，但我找不到任何类似的帖子。

在此基础上的构建可能看起来过于复杂，但我正在尝试学习二叉排序树并将其应用到我的图形知识中。我知道使用邻接表可能更容易。

目前构建使用两个结构和一个类，一个结构用于边，一个用于向量，“图形”类用作二叉搜索树。

    // 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 并存储它的名称以供以后比较，但我的输出是这样的：

    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:

所以我得到了分配给 BST 中节点的值，但我没有得到存储在 Vertex 中的名称。

Answer 1

在你的图形构造函数中你有：

    Vertex* newNode = new Vertex;
    newNode = node;

在局部变量 newNode 中构造一个新顶点和指向它的指针。

然后局部变量被赋值指向不同的顶点，作为参数传入的顶点

然后退出。构建的新顶点仍然存在，但没有任何东西可以引用它。这是内存泄漏。