Программа для создания двоичного дерева, печать и поиск - Node Class C++

Question

Я создал программу, которая содержит класс Node для представления двоичного дерева любого типа (шаблона).

В моем классе Node.h у меня есть два конструктора, однако я не уверен, правильно ли я их выполнил. Инициализация значений внутри конструкторов меня смутила. В моем файле main.cpp у меня есть функция setUpTree. Моя программа выполняется сейчас, но не печатает настроенное дерево.

Я пытался часами пытаться исправить это, но не до конца. На самом деле я не очень разбираюсь в C++, указателях, конструкторах и т. Д.

Я был бы признателен, если бы кто-нибудь мог помочь мне исправить мой код, чтобы работала функция setUpTree, а также метод printTree.

Благодаря

node.h Класс:

#ifndef NODE_H 
#define NODE_H 
#include <iostream> 
#include <string> 
using namespace std; 

//an object of type node holds 3 things 
// - an item (of type t) 
// - a left subtree 
// - a right subtree 

template<typename T> 
class Node { 
public: 
    Node(T item); //constructor to create a leaf node 
    Node(T item, Node *lft, Node *rht); //constructor which creates an internal node 
    ~Node(); //Destructor 

    //public data member functions: 
    bool searchTree(T key); 
    void printTree(); 

private: 
    //private data member functions: 
    Node* left; 
    Node* right; 
    T item; 
}; 

//constructor 
template<typename T> 
Node<T>::Node(T i, Node<T> *lft, Node<T> *rht) { 
    item = i; 
    left = NULL; 
    right = NULL; 
} 

//constructor 
template <typename T> 
Node<T>::Node(T i) { //should i be a parameter here? 
    item = i; //is this right for this constructor? 
} 

//destructor 
template <typename T> 
Node<T>::~Node() { 
    delete left; 
    delete right; 
    //delete; 
} 


//print tree method 
template <typename T> 
void Node<T>::printTree() { 
    if (left != NULL) { 
     left->printTree(); 
     cout << item << endl;//alphabetical order 
    } 

    if (right != NULL) { 
     right->printTree(); 
     //cout << item << endl; //post order 
    } 
} 

//search Tree method 
template <typename T> 
bool Node<T>::searchTree(T key) { 
    bool found = false; 
    if (item == key) { 
     return true; 
    } 
    if (left != NULL) { 
     found = left->searchTree(key); 
     if (found) return true; 
    } 
    if (right != NULL) { 
     return right->searchTree(key); 
    } 
    return false; //if left and right are both null & key is not the search item, then not found == not in the tree. 
} 

#endif 

main.cpp Класс:

#include "Node.h" 
#include <iostream> 
using namespace std; 

//set up tree method 
Node<string> *setUpTree() { 
    Node<string> *s_tree = 
     new Node<string>("Sunday", 
     new Node<string>("monday", 
     new Node<string>("Friday"), 
     new Node<string>("Saturday")), 
     new Node<string>("Tuesday", 
     new Node<string>("Thursday"), 
     new Node<string>("Wednesday"))); 
    return s_tree; 
} 

int main() { 

    Node<string> *s_tree; 
    s_tree = setUpTree(); //call setUpTree method on s_tree 

    cout << "Part 2 :Printing tree values: " << endl; 
    s_tree->printTree(); //call print tree method 

    cout << endl; 

    //search for range of tree values 
    //searchTree(s_tree, "Sunday"); 
    //searchTree(s_tree, "Monday"); 

    return 0; 
} 

Answer 1

Я не знаю, если это единственная проблема, но ... если вы строите лист, вы должны установить left и right указатели на NULL

template <typename T> 
Node<T>::Node(T i) : left(NULL), right(NULL), item(i) 
{ } 

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

template <typename T> 
Node<T>::~Node() { 
    delete left; 
    delete right; 
    //delete; 
} 

delete вызывается над неопределенными значениями; два раза.

Это идеальный рецепт катастрофы.

Другие проблемы в каждой точке вы используете left или right проверки, если указатель NULL, как и сделано в printTree() или searchTree(): значение не определено, поэтому может быть не NULL, пройти тест и printTree() вызывается через указатель с неопределенное значение

- EDIT -

Предлагаемые contructors.

template <typename T> 
Node<T>::Node (T i, Node<T> * lft, Node<T> * rht) 
: left(lft), right(right), item(i) 
{ } 

template <typename T> 
Node<T>::Node (T i) 
: left(NULL), right(NULL), item(i) 
{ } 

--- EDIT 2 ---

it is now printing some values at least ; monday sunday tuesday. not sure about the rest

Посмотрите на свой printTree() Metod

шаблон аннулируются Node :: printTree() { если (слева! = NULL) { левый-> printTree(); соиЬ < < < < пункт епсИ; // алфавитный порядок }

if (right != NULL) { 
    right->printTree(); 
    //cout << item << endl; //post order 
} 

}

Это напечатает значение (item) только если leftNULL не является. Поэтому он не печатает значение листьев.

Предложение: изменить printTree() для печати item, даже если left is NULL.

К примеру

template <typename T> 
void Node<T>::printTree() { 
    if (left != NULL) { 
     left->printTree(); 
    } 

    cout << item << endl; 

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

Answer 2

Первое возвращение в setupTree должно быть s_tree.

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

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

private: 
    //private data member functions: 
    Node* left = NULL; 
    Node* right = NULL; 
    T item;