Двоичное дерево (вставка и поиск по радиусу)

Question

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

Текстовый файл выглядит следующим образом: Имя Адрес Старое здание 31,2222 Новое здание 21,2111

Как я уже сказал, программа уже читает в файле, так что это не проблема. Однако мне нужно вставить имя и местоположение в узлы двоичного дерева. Затем я должен искать все в пределах диапазона, из которого приходит плюс минус.

Боковое примечание: мой конструктор копирования может быть неправильным, хотя он соответствует требованиям.

Спасибо за помощь!

#ifndef BINTREE_HPP 
#define BINTREE_HPP 

#include <utility> 
#include <string> 
#include <vector> 

class bintree { 

// A binary search tree for locations in Lineland. 

// Notes: 
// - Assume a flat, one-dimensional world with locations from -180 to 180. 
// - All locations and distances are measured in the same units (degrees). 

public: 
// Default constructor 
bintree() { 
    this->root = NULL; 
} 

// Copy constructor 
bintree(const bintree &t) { 
    this -> root = NULL; 
*this = t; 
} 

// Destructor 
~bintree() { 

} 


// Copy assignment is implemented using the copy-swap idiom 

friend void swap(bintree &t1, bintree &t2) { 
using std::swap; 
// Swap all data members here, e.g., 
// swap(t1.foo, t2.foo); 
// Pointers should be swapped -- but not the things they point to. 
} 
bintree &operator= (bintree other) { 
// You don't need to modify this function. 
swap(*this, other); 
return *this; 
} 

void insert(const std::string& name, double p) { 
    // insert node with name and location (p) 
} 

void within_radius(double p, double r, std::vector<std::string> &result) const { 
    // Search for elements within the range `p` plus or minus `r`. 
    // Clears `result` and puts the elements in `result`. 
    // Postcondition: `result` contains all (and only) elements of the 
    // tree, in any order, that lie within the range `p` plus or minus 
    // `r`. 
    } 

private: 

struct node 
{ 
node *left; 
node *right; 

}; 

node* root; 

}; 

#endif 

Answer 1

Во-первых, ваши узлы должны держать данные:

struct node 
{ 
node *left; 
node *right; 
std::string name; // This is the key for your reasearch 
double p;   // followed by other data 
}; 

Тогда вы можете думать, чтобы просматривать через дерево, чтобы вставить новый узел. В этом примере я предполагаю, что вы можете вставить несколько узлов с тем же именем.

void insert(const std::string& name, double p) { 
    node *n = new node;  // create a new node 
    n->name=name; n->p=p;  // intialise the data payload 
    n->left=n->right=nullptr; // and make it a leaf. 

    if (root==nullptr)  // if tree is empty, 
     root = n;     // add the new node. 

    else {     // else find where to insert it 
     node* t=root; 
     while (true) { 
      if (t->name > n->name) {  // go to left 
       if (t->left==nullptr) { 
       t->left = n;  
       break; 
       } 
       else t=t->left; 
      } 
      else if (t->name == n->name) { // insert between current and next 
       n->right = t->right; 
       t->right = n; 
       break; 
      } 
      else {       // go to right 
       if (t->right==nullptr) { 
       t->right = n;  
       break; 
       } 
       else t=t->right; 
      } 
     } 
    } 
} 

Здесь live demo.

Обратите внимание, что я только ответил на ваш вопрос вставки, вам все равно придется делать много на своем собственном (оператор = и конструктор копирования анализ необходим, деструктор должен быть создан, и т.д ...)