程序設置二叉樹，打印並搜索 - 節點類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;