程序设置二叉树，打印并搜索 - 节点类C++

Question

我创建了一个包含类节点的程序，用于表示任何类型（模板）的二叉树。

在我的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()叫了一个指针未定义的值

- 编辑 -

建议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()梅托德

模板 无效节点:: printTree（）{ 如果（左！= NULL ）{ left-> printTree（）; COUT < <项< < ENDL; //字母顺序 }

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

}

它打印的值（item）仅如果left不NULL。所以它不会打印叶子的值。

意见建议：修改printTree()打印item即使left是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;