Бинарное дерево поиска с корневой системой. Сохранение ссылки на своего родителя

Question

Я пытаюсь создать двоичное дерево поиска, сохраняя путь: каждый узел имеет ссылку на своего родителя. Ниже представлен бинарный поиск classi c. Как мне изменить его, чтобы решить мою проблему? Я попытался добавить к структуре указатель «отца», но у меня нет проблем с пониманием того, как и когда его сохранить. Я новичок в этом языке, так что наберитесь терпения. огромное спасибо

#include <iostream>

template <class T>
class BinaryTree
{

    struct node {
        T value;
        struct node* right;
        struct node* left;
    };

public:
    BinaryTree();
    ~BinaryTree();
    void add(T val);
    void printPreOrder();
    void printInOrder();
    void printPostOrder();
    int size();
    bool lookup(T val);

private:
    struct node* root;
    int treeSize;
    void add(struct node** node, T val);
    bool lookup(struct node* node, T val);
    void printPreOrder(struct node* node);
    void printInOrder(struct node* node);
    void printPostOrder(struct node* node);
    void deleteTree(struct node* node);
};

template <class T>
BinaryTree<T>::BinaryTree() {
    this->root = NULL;
    this->treeSize = 0;
}

template <class T>
BinaryTree<T>::~BinaryTree() {
    deleteTree(this->root);
}

template <class T>
int BinaryTree<T>::size() {
    return this->treeSize;
}

template <class T>
void BinaryTree<T>::add(T val) {
    add(&(this->root), val);
}

template <class T>
void BinaryTree<T>::add(struct node** node, T val) {

    if (*node == NULL) {
        struct node* tmp = new struct node;
        tmp->value = val;
        tmp->left = NULL;
        tmp->right = NULL;
        *node = tmp;

        this->treeSize++;
    }
    else {
        if (val > (*node)->value) {
            add(&(*node)->right, val);
        }
        else {
            add(&(*node)->left, val);
        }
    }
}

template <class T>
void BinaryTree<T>::printInOrder() {
    printInOrder(this->root);
    std::cout << std::endl;
}

template <class T>
void BinaryTree<T>::printInOrder(struct node* node) {
    if (node != NULL) {
        printInOrder(node->left);
        std::cout << node->value << ", ";
        printInOrder(node->right);
    }
}

template <class T>
void BinaryTree<T>::printPreOrder() {
    printPreOrder(this->root);
    std::cout << std::endl;
}

template <class T>
void BinaryTree<T>::printPreOrder(struct node* node) {
    if (node != NULL) {
        std::cout << node->value << ", ";
        printInOrder(node->left);
        printInOrder(node->right);
    }
}

template <class T>
void BinaryTree<T>::printPostOrder() {
    printPostOrder(this->root);
    std::cout << std::endl;
}

template <class T>
void BinaryTree<T>::printPostOrder(struct node* node) {
    if (node != NULL) {
        printInOrder(node->left);
        printInOrder(node->right);
        std::cout << node->value << ", ";
    }
}


template <class T>
void BinaryTree<T>::deleteTree(struct node* node) {
    if (node != NULL) {
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
}

template <class T>
bool BinaryTree<T>::lookup(T val) {
    return lookup(this->root, val);
}

template <class T>
bool BinaryTree<T>::lookup(struct node* node, T val) {
    if (node == NULL) {
        return false;
    }
    else {
        if (val == node->value) {
            return true;
        }

        if (val > node->value) {
            return lookup(node->right, val);
        }
        else {
            return lookup(node->left, val);
        }
    }

}

Answer 1

Я дам вам рекурсивное решение, поскольку это естественный способ его реализации: сначала было бы неплохо определить конструктор в вашей структуре следующим образом:

node(T value, node* left = nullptr, node* right = nullptr){
    this->value = value;
    this->left = left;
    this->right = right;
}

Выньте структуру в узле структуры * root.

void insert(T value){
    Node* temp = root;
    insert(value, root);
}
//helper function
void insert(T value, Node* root){
    if(root->left == nullptr && root->right == nullptr){
       if(root->value < value){
          root->left = new Node(value);
       }
       else{
          root->right = new Node(value);
       }
       return;
    }
    if(value < root->value)insert(value, root->left);
    else{
        insert(value, root->right);
    }
}

Не уверен, где у вас есть код, он выглядит некорректно ....

Answer 2

Я не понимаю необходимости указывать указатель на struct node в вашем коде. Указателя на struct node будет достаточно. Что касается вашего вопроса, вы можете передать родительский элемент текущего узла в качестве третьего параметра в методе add. Первоначально он будет нулевым. Теперь, если вам нужно go вниз к дочернему элементу текущего узла, тогда текущий узел становится его родительским. Когда вам нужно выделить память для значения val, установите его здесь родителя.

template <class T>
void BinaryTree<T>::add(struct node** node, T val, struct node* parent = nullptr) {

    if (*node == NULL) {
        struct node* tmp = new struct node;
        tmp->value = val;
        tmp->left = NULL;
        tmp->right = NULL;
        temp->parent = parent;
        *node = tmp;

        this->treeSize++;
    }
    else {
        if (val > (*node)->value) {
            add(&(*node)->right, val, *node);
        }
        else {
            add(&(*node)->left, val, *node;
        }
    }
}