C++ Binary Tree Programmierung neue Knoten verlassen Scope Problem

Question

Ich bin ein Java-Programmierer Lehre mich C++.

Beim Schreiben eines Binärbaums habe ich festgestellt, dass mein Programm keine Werte in den Baum "hinzugefügt" hat.

#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) {}; 
} 

Ich habe es nicht gelungen, das Problem in Bezug auf die finden, warum der Baum begehen keine neuen Knoten außer der Wurzel.

Ich verwendete "neu" im Code beim Schreiben (ref = neuer Knoten) usw. in der Methode adds, da dies verhindern sollte, dass der neue Knoten zerstört wird, sobald er den Bereich verlässt.

Wenn mich jemand über dieses Thema aufklären kann, werde ich sehr dankbar sein.

Answer 1

Um einen Knoten zu dem Baum Sie es bis zu einem gewissen vorhandenen Knoten zu verknüpfen haben hinzuzufügen, wie in

existing_node->{left or right} = new_node; 

Sobald ref nullptr wird, Sie haben keinen gültigen mehr vorhandenen Knoten, und es ist zu spät, etwas zu tun. Stattdessen durchquert den Baum solange ref->{left or right} gültig ist:

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

    // etc for v > ref->val