C++ binarysearchtree insert

Question

Я работаю над проектом, где мне нужно создать двоичное дерево поиска, в котором хранятся строки и учитываются двойники. Хотя я уже занимался спецификой, я не могу на всю жизнь получить эту чертову функцию вставки. Кажется, он хранит только корневой узел, оставляя его «дочерними» NULL, хотя на самом деле он действительно присваивает левым и правым указателям новые узлы. Однако, когда я пытаюсь вывести его, существует только основной родительский (корневой) узел. Я думаю, что изменения не сохраняются по какой-либо причине.

Вот заголовок файла:

#ifndef BST_H 
#define BST_H 

#include <string> 
#include <vector> 
#include <iostream> 
using namespace std; 

typedef string ItemType; 

class Node 
{ 
public: 
Node(); // constructor 
ItemType data; // contains item 
Node* left; // points to left child 
Node* right;// points to right child 
int dataCount; // keeps track of repeats 
vector<int> lineNumber; // keeps track of line numbers 
}; 

class Tree 
{ 
public: 
Tree(); // constructor 
// ~Tree(); // destructor. not working. 
bool isEmpty(); // tests for empty tree 
Node* find(Node* root, ItemType item); // finds an item 
void insert(Node* root, ItemType item, int lineN, Tree tree); // inserts an item 
void outputTree(Node* root); // lists all items in tree 
void treeStats(Tree tree); // outputs tree stats 
void clearTree(); // erases the tree (restart) 
Node* getRoot(); // returns the root 
void setRoot(Node*& root); 
// void getHeight(Tree *root); // gets height of tree 

private: 
Node* root; // root of tree 
int nodeCount; // number of nodes 
}; 

#endif 

каст:

#include "BST.h" 

bool setRootQ = true; 

/** Node constructor- creates a node, sets children 
* to NULL and ups the count. */ 
Node::Node() 
{ 
left = right = NULL; 
dataCount = 1; 
} 

/** Tree constructor- creates instance of tree 
* and sets parameters to NULL */ 
Tree::Tree() 
{ 
root = NULL; 
nodeCount = 0; 
} 

/** Destructor- deallocates tree/node data; 
* avoids heap leaks. SOMETHING WRONG. CAUSES SEGFAULT 
Tree::~Tree() 
{ 
if(this->root->left) // if a left child is present 
{ 
    delete this->root->left; //recursive call to destructor ("~Tree(->left)") 
    this->root->left = NULL; 
} 
if(this->root->right) // if a right child is present 
{ 
    delete this->root->right; //recursive call to destructor 
    this->root->right = NULL; 
} 
} */ 

/** Returns true if tree is empty. 
* Otherwise returns false (DUH). */ 
bool Tree::isEmpty() 
{ 
return root == NULL; 
} 

/** Searches tree for item; returns the node if found 
* @param root- tree node. 
* item- data to look for. */ 
Node* Tree::find(Node* root, ItemType item) 
{ 
if(root == NULL) // if empty node 
{ 
    return NULL; 
} 
else if(item == root->data) // if found 
{ 
    return root; 
} 
else if(item < root->data) // if item is less than node 
{ 
    find(root->left, item); 
} 
else if(item > root->data) // if item is more than node 
{ 
    find(root->right, item); 
} 

return NULL; 
} 

/** Adds a new node to the tree. If duplicate, increases count. 
* @param item- data to insert. 
* root- tree node/ */ 
void Tree::insert(Node* root, ItemType item, int lineN, Tree tree) 
{ 
Node* temp = find(tree.getRoot(), item); 
if(temp != NULL) // if item already exists 
{ 
    temp->dataCount += 1; 
    temp->lineNumber.push_back(lineN); 
    return; 
} 

if(root == NULL) // if there is an empty space 
{ 
    root = new Node; // insert new node 
    root->data = item; // w/ data value 
    root->lineNumber.push_back(lineN); 
    nodeCount++; 

    if(setRootQ) 
    { 
    setRoot(root); 
    setRootQ = false; 
    } 
    return; 
} 

if(item < root->data) 
{ 
    insert(root->left, item, lineN, tree); 
} 
if(item > root->data) 
{ 
    insert(root->right, item, lineN, tree); 
} 
} 

/** Outputs tree to console in inorder. 
* @param root- tree root. */ 
void Tree::outputTree(Node* root) 
{ 
if(isEmpty()) // if empty tree 
{ 
    cout << "Error: No items in tree" << endl; // error message 
} 
else 
{ 
    if(root->left != NULL) 
    { 
    outputTree(root->left); 
    } 

    cout << "- " << root->data << " (" << root->dataCount << ") line#s: "; 
    for(unsigned int i = 0; i < root->lineNumber.size(); i++) 
    { 
    cout << root->lineNumber[i] << ", "; 
    } 
    cout << endl; 

    if(root->right != NULL) 
    { 
    outputTree(root->right); 
    } 
} 
} 

/** Displays tree stats including number of nodes, 
* tree height, and more frequent item. 
* @param tree- tree instance. */ 
void Tree::treeStats(Tree tree) 
{ 
cout << "Number of entries: " << nodeCount << endl; 
// unfinished 
} 

/** Clears tree. 
void Tree::clearTree() 
{ 
this->~Tree(); 
} */ 

/** Returns the root of the tree. */ 
Node* Tree::getRoot() 
{ 
return root; 
} 

void Tree::setRoot(Node*& rootS) 
{ 
root = rootS; 
} 

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

я думаю, что это мощь что-то делать с

void Tree::insert(Node* root, ItemType item, int lineN, Tree tree) 

и вместо этого должно быть что-то вроде

void Tree::insert(Node* &root, ItemType item, int lineN, Tree tree) 

, но когда я пытаюсь я получаю «нет соответствия функции» ошибка. :/

Answer 1

решение, которое вы предложить себя (с insert() принимая Node *& корень) будет работать. Вы должны внести соответствующее изменение в файл .h, а также изменить getRoot(), чтобы вернуть Node *& в файлы .h и .cc.

Это будет работать. Но у вашего кода есть другие проблемы. Например, setRoot и setRootQ не делают ничего полезного, насколько я могу судить. Четвертый аргумент insert() только путает вещи и ничего не делает для обнаружения дубликатов. Его следует удалить. Чтобы обнаружить дубликат, просто сделайте if (item == root->data) непосредственно перед тем, как сделать if (item < root->data) в методе insert() (т. Е. Он будет больше похож на find()).

Кроме того, если кто-либо, кроме вас, когда-либо будет использовать ваш код, не должен нуждаться в передаче в getRoot() методам, например find() и insert(). Вместо этого создайте частные вспомогательные методы, например find_helper(Node*, Item) и insert_helper(Node*&,Item), а общедоступные методы вызывают их с корневым узлом в качестве первого аргумента. Например .:

Node *find(Item item) { return find_helper(root, item); } 

Это также сделает странный тип возвращаемого getRoot() ненужного, и вы можете изменить его обратно на возвращение простого Node*, или избавиться от этого аксессора вообще.

Answer 2

Похоже, что существует большое количество сравнения указателей, но переменные-члены указателя не инициализируются. Убедитесь, что переменные-члены указателя инициализированы правильно, чтобы они правильно оценивали в операторах if.

Изменение от:

class Node 
{ 
public: 
Node(); // constructor 
... 
}; 

to 

class Node 
{ 
public: 
Node() : left(0), right(0) {} 
... 
};