c ++ двоичный поиск в дереве

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

cpp:

#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 *& root) будет работать.Необходимо внести соответствующее изменение в файл .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) {}
...
};