C++实现AVL树

Question

我有一个 TreeSet 类用 C++ 描述一棵树:

class TreeSet
{
private:
    AVLNode * root;
    int count;

protected:
    void clearRec(AVLNode*root);


public:
    TreeSet();
    ~TreeSet();
    void clear();
    // print out the set in ascending order
    friend ostream& operator<<(ostream& os, const TreeSet& t);


    int add(int val);
}

和一个AVL节点类来表示一个AVL节点:

class AVLNode {
public:
    int key;            // data 
    AVLNode* left;      // left child
    AVLNode* right;     // right child
    int balance;        // balance factor

    AVLNode(int key) {
        this->key = key;
        left = right = NULL;
        balance = 0;
    }
    AVLNode(int key, int balance) {
        this->key = key;
        this->balance = balance;
        left = right = NULL;
    }
};

这是我在 TreeSet 中没有任何内容时添加函数的实现

int TreeSet::add(int val) {
    if (root == NULL) {
        AVLNode newNode(val);
        root = &newNode;        
        count++;
    }
}

主要函数:

int main() {
    TreeSet set, temp, *subSet;
    ifstream ifs;
    ifs.open("input.txt");
    char command;
    int val;
    try
    {
        while (ifs >> command) {
            switch (command) {
            case 'a': // add an element to the set
                ifs >> val;
                set.add(val);
                break;
            }
        }
    }
}

但是当我有一个 txt 文件时 一个 4

它不会将 4 打印到屏幕上。你能帮我解决这个问题吗？

Answer 1

    AVLNode newNode(val);
    root = &newNode;      

newNode 是局部变量，您将指针指向此 var，但 newNode 在 add 方法结束时超出范围，因此您有悬空指针。您需要通过 new 运算符在堆上分配 AVLNode:

    root = new AVLNode(val);