Двоичное дерево поиска PostOrder и PreOrder неверны

Question

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

http://www.theteacher99.btinternet.co.uk/theteacher/newalevel/cp4_5_4.htm

Можете ли вы взглянуть на мой код ниже и посмотреть, что я делаю не так. Любая помощь / ориентация будет оценена. Вам не нужно решать это за меня, просто дайте мне знать, что я делаю неправильно. Благодарю.

#include <iostream>
#include <fstream>
#include <cstddef>
#include <string>
#include <sstream>
#include <string>

using namespace std;

struct TreeNode
{
    string item;
    TreeNode *left;
    TreeNode *right;
};

class BinarySortTree
{
public:
    BinarySortTree();
    void readFile(string fileName);
    void insert(string key);
    void preorder();
    void postorder();
    void inorder();
    void test();

private:
    TreeNode *root;
    void insert(string key, TreeNode *node);
    void preorderTraverse(TreeNode *node);
    void postorderTraverse(TreeNode *node);
    void inorderTraverse(TreeNode *node);
};


//default constructor, create new binary tree
BinarySortTree::BinarySortTree()
{
    root = NULL;
}

//reads the file and puts items in the tree
void BinarySortTree::readFile(string fileName)
{
    ifstream inputStream(fileName.c_str());

    if(inputStream.is_open())
    {
        string line;

        while( getline(inputStream, line) )
        {
            insert(line);
        }
    }
}

void BinarySortTree::insert(string key)
{
    if(root != NULL)
    {
        insert(key, root);
    }
    else
    {
        root = new TreeNode;
        root->item = key;
        root->left = NULL;
        root->right = NULL;
    }
}

void BinarySortTree::insert(string key, TreeNode *node)
{
    bool done = false;

    while(!done)
    {
        if(key.compare(node->item) < 0)
        {
            if(node->left != NULL)
            {
                node = node->left;
            }
            else
            {
                node->left = new TreeNode;
                node->left->item = key;
                node->left->left = NULL;
                node->left->right = NULL;
                done = true;
            }
        }
        else if(key.compare(node->item) > 0)
        {
            if(node->right != NULL)
            {
                node = node->right;
            }
            else
            {
                node->right = new TreeNode;
                node->right->item = key;
                node->right->left = NULL;
                node->right->right = NULL;
                done = true;
            }
        }
        else if(key.compare(node->item) == 0)
        {
            done = true;
        }
    }
}

void BinarySortTree::preorder()
{
    cout << "PreOrder Traversal" << endl;
    preorderTraverse(root);
    cout << endl;

}

/*
   1. Start at the root node
   2. Traverse the left subtree
   3. Traverse the right subtree
*/
void BinarySortTree::preorderTraverse(TreeNode *node)
{
    if(node != NULL)
    {
        cout << node->item << " ";
        preorderTraverse(node->left);
        preorderTraverse(node->right);
    }

}

void BinarySortTree::postorder()
{
    cout << "PostOrder Traversal" << endl;
    postorderTraverse(root);
    cout << endl;
}

/*
   1. Traverse the left subtree
   2. Traverse the right subtree
   3. Visit the root node
*/
void BinarySortTree::postorderTraverse(TreeNode *node)
{
    if(node != NULL)
    {
        postorderTraverse(node->left);
        postorderTraverse(node->right);
        cout << node->item << " ";
    }
}

void BinarySortTree::inorder()
{
    cout << "InOrder Traversal" << endl;
    inorderTraverse(root);
    cout << endl;
}

/*
   1. Traverse the left subtree
   2. Visit the root node
   3. Traverse the right subtree
*/
void BinarySortTree::inorderTraverse(TreeNode *node)
{
    if(node!= NULL)
    {
        inorderTraverse(node->left);
        cout << node->item << " ";
        inorderTraverse(node->right);
    }
}

void BinarySortTree::test()
{
    cout << root->item << endl;
}


int main()
{
    string fileName = "a4.txt";
    BinarySortTree bst;
    bst.readFile(fileName);
    bst.test();

    bst.preorder();
    bst.postorder();
    bst.inorder();

    return 0;
}

Answer 1

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

Убедитесь, что вы назначаете left/right указатели на NULL в вашем конструкторе для TreeNodeи правильно передать в D-узле как root, Также не забудьте удалить любые узлы, которые вы создаете через new TreeNode, Если вы создаете их в стеке (обычная локальная переменная без new), вы, конечно, не должны их удалять.

Answer 2

Ваш код правильный. Но где функция main()?