C++ Двоичное дерево Программирование новых узлов, оставляющих проблему с областью

Question

Я программист Java, преподающий сам C++.

При написании двоичного дерева я обнаружил, что моя программа не добавила значения к дереву.

#include "stdafx.h" 
#include <cstdlib> 
#include <iostream> 
using namespace std; 
class BinaryTree { 

    struct Node { 
    public: 
     int val; 
     Node* left; 
     Node* right; 
     Node::Node(int v) { 
      val = v; 
      left = nullptr; 
      right = nullptr; 
     } 
    }; 
public: 
    BinaryTree() { 
     root = nullptr; 
    } 

    int size = 0; 
    int length(); 
    bool BinaryTree::add(int v); 
    void printTree(); 
private: 
    void printTree(Node* n); 
    Node* root; 

}; 
bool BinaryTree::add(int v) { 

    if (root == nullptr) { 
     root = new Node(v); 
     ++size; 
     return true; 
    } 
    Node* ref = root; 
    cout << ref->val; 
    while (ref != nullptr) { 
     if (v < ref->val) { 
      ref = ref->left; 
     } 
     else if (v > ref->val) { 
      ref = ref->right; 
     } 
     else if (v == ref->val) { 
      return false; 
     } 
    } 
    Node *newNode = new Node(v); 
    ref = newNode; 
    ++size; 
    return true; 
} 
void BinaryTree::printTree() { 
    printTree(root); 
} 
void BinaryTree::printTree(Node* n) { 
    if (n == nullptr) { 
     return; 
    } 
    printTree(n->left); 
    cout << n->val << endl; 
    printTree(n->right); 
} 
int BinaryTree::length() { 
    return size; 
} 
void main(int i) { 
    BinaryTree tree = BinaryTree(); 
    tree.add(6); 
    tree.add(3); 
    tree.add(5); 
    tree.add(7); 
    tree.add(1); 
    tree.add(0); 
    tree.add(0); 

    tree.printTree(); 
    cout << "binary tree sz is " << tree.length() << endl; 
    while (true) {}; 
} 

Я не смог найти проблему в отношении того, почему дерево не совершает новых узлов, кроме корня.

Я использовал «новый» в коде при записи (ref = new Node) и т. Д. В методе добавления, потому что это должно препятствовать уничтожению нового узла после его удаления.

Если кто-нибудь может просветить меня по этому вопросу, я буду очень благодарен.

Answer 1

Чтобы добавить узел в дереве, вы должны связать его с какой-то существующий узел, как и в

existing_node->{left or right} = new_node; 

ref После того, как становится nullptr, вы не имеете действительный существующий узел больше, и это тоже поздно сделать что-нибудь. Вместо этого, перемещаться по дереву, пока ref->{left or right} действует:

if (v < ref->val) { 
     if (ref->left) { 
      ref = ref->left; 
     } else { 
      ref->left = newNode; 
      return true; 
     } 
    } 

    // etc for v > ref->val