nullptr =节点分配不正确

Question

请不要对我深入研究，在尝试构建AVL树时，我仍在稳步学习并遇到问题。在插入时遍历树时，我一直走到到达nullptr为止，创建一个新节点，然后将该ptr分配给nullptr。该值永远不会被接受。有人可以找到错误并向我解释吗？ ty！

#ifndef AVLTree_hpp
#define AVLTree_hpp

#include <stdio.h>
#include <stack>
template<typename T>
class AVLTree{
private:
    struct Node{
        T val;
        Node* left;
        Node* right;
        int height;

        Node(T V)
        :left{nullptr},right{nullptr}
        {
            val = V;
        }
        ~Node(){

        }
    };
    Node* head;
    void rightRotate(Node*& node);
    void leftRotate(Node*& node);
    void leftRight(Node*& node);
    void rightLeft(Node*& node);


public:
    AVLTree();
    ~AVLTree();
    AVLTree(const AVLTree &c);
    AVLTree(AVLTree &&c);
    AVLTree &operator=(const AVLTree &c);
    AVLTree &operator=(AVLTree &&c);
    void add(T value);
    int getHeight(Node* n);
};

template <typename T>
AVLTree<T>::AVLTree()
    :head{nullptr}{
}
template <typename T>
AVLTree<T>::~AVLTree(){

}

template <typename T>
void AVLTree<T>::rightRotate(Node*& node){
    Node* temp = node;
    node = node->left;
    Node* leftLL = node->right;
    temp->left = leftLL;
    node->right = temp;
}
template <typename T>
void AVLTree<T>::leftRotate(Node*& node) {
    Node* temp = node;
    node = node->right;
    Node* yL = node->left;
    temp->right = yL;
    node->left = temp;
}
//left right condition
template <typename T>
void AVLTree<T>::leftRight(Node*& node) {
    leftRotate(node->left);
    rightRotate(node);
}

//right left condition
template <typename T>
void AVLTree<T>::rightLeft(Node*& node){
    rightRotate(node->right);
    leftRotate(node);
}
template <typename T>
void AVLTree<T>::add(T value){
    if(head==nullptr){
        head = new Node(value);
        return;
    }
    std::stack<Node*> st;
    Node* it = head;
    while(it!=nullptr){
        st.push(it);
        if(value <= it->val){
            it = it->left;
        }else{
            it=it->right;
        }
    }
//here is where the it is not assigned to the new node pointer. 
//I have tested it and the node is created, "it" just does not hold the value at any point.
    it = new Node(value);
    int count = 0;
    while(!st.empty()){
        int balance = getHeight(st.top()->left) - getHeight(st.top()->right);
        if(balance > 1){
            if(st.top()->left!= nullptr&&st.top()->left!=nullptr){
                leftRotate(st.top());
            }else{
                leftRight(st.top());
            }
        }else if(balance<-1){
            if(st.top()->right!=nullptr&&st.top()->right!=nullptr){
                rightRotate(st.top());
            }else{
                rightLeft(st.top());
            }
        }
        st.pop();
        if(++count==4){
            break;
        }
    }
}
template <typename T>
int AVLTree<T>::getHeight(Node* n){
    int max =0;
    if(n!=nullptr){
        max = std::max(getHeight(n->left),getHeight(n->right))+1;
    }
    return max;
}


#endif /* AVLTree_hpp */

Answer 1

It是指针的副本，对其进行更新对原始指针没有影响。您需要执行以下操作：

Node* it = head;
bool left = true;
while(it!=nullptr){
    st.push(it);
    left = value <= it->val;
    if(left){
        it = it->left;
    }else{
        it=it->right;
    }
}
it = new Node(value);
if (left){
    stack.top()->left = it;
} else {
    stack.top()->right = it;
}