c++ - 树类根节点不更新

Question

我正在尝试用 C++ 编写一个 AVL Tree 类，我只是从为普通 BST 编写代码开始，但我遇到了问题。我遇到的问题是我的插入功能。我尝试将元素插入到树中，但实际上并没有这样做。我不太确定为什么不这样做，我的直觉是我正在从函数内部更改树，但我没有做任何事情来保存这些更改，而且我不知道该怎么做那个。

#ifndef AVLTREE_H
#define AVLTREE_H
#include <iostream>

template <class K, class V>
struct AVLNode{
    K Key;
    V Value;
    AVLNode<K,V> *left;
    AVLNode<K,V> *right;
};

template <class K, class V>
class AVLTree{
    public:
        AVLTree();
        ~AVLTree();
        void insert(const K& Key, const V& Value);
        void print_AVL();
    private:
        void print_AVL2(AVLNode<K,V> *node);
        void insert2(AVLNode<K,V> *node, const K& Key, const V& Value);
        AVLNode<K,V> *root;
};

template <class K, class V>
AVLTree<K,V>::AVLTree(){
    root = nullptr;
}

template <class K, class V>
AVLTree<K,V>::~AVLTree(){
    delete root;
}
template <class K, class V>
void AVLTree<K,V>::insert(const K& Key, const V& Value){
    std::cout << "Trying to insert " << Key << ", " << Value << std::endl;
    insert2(root, Key, Value);
}

template <class K, class V>
void AVLTree<K,V>::insert2(AVLNode<K,V> *n, const K& Key, const V& Value){
    std::cout << n << std::endl;
    if(n== nullptr){
        n = new AVLNode<K,V>;
        n->Key = Key;
        n->Value = Value;
        n->parent = nullptr;
        n->left = nullptr;
        n->right = nullptr;
    }
    else if(n->Key > Key){
        insert2(n->left, Key, Value);
    }
    else{
        insert2(n->right, Key, Value);
    }
    std::cout << n << std::endl;
}

template <class K, class V>
void AVLTree<K,V>::print_AVL(){
    print_AVL2(root);
}


template <class K, class V>
void AVLTree<K,V>::print_AVL2(AVLNode<K,V> *n){
    std::cout << n << std::endl;
    if(n == nullptr){
        return;
    }
    print_AVL2(n->left);
    std::cout << "Name, ID: " << n->Value << ", " << n->Key << std::endl;
    print_AVL2(n->right);
}


#endif

我的主要功能是这样的:

#include "AVLTree.hpp"
#include <iostream>

int main() 
{
    AVLTree<std::string,std::string> Tree;
    Tree.insert("Hello","World");
    Tree.print_AVL();
    return 0;
}

Answer 1

请记住，即使在 C++ 中，除非另有明确说明，否则参数按值传递因此:

void AVLTree<K,V>::insert2(AVLNode<K,V> *n, const K& Key, const V& Value)

加上这个:

n = new AVLNode<K,V>;

只会将 new 调用的结果分配给一个自动变量 n，该变量将在此函数返回时消失。

如果你想保留那个结果，通过引用传递指针:

void AVLTree<K,V>::insert2(AVLNode<K,V>*& n, const K& Key, const V& Value)
// reference to the caller's pointer ===^

声明和实现都发生了变化。剩下的 parent 指针未声明成员我留给你修复，以及一旦你开始向树中添加更多节点，根节点的未销毁子节点随之而来的内存泄漏。