c++ - 二叉搜索树后序和前序遍历错误

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

你没有做错任何事。我编译了它，它运行良好，并通过了那些测试。我不必对您提供的代码进行任何更改 - 只需添加代码即可正确编译和初始化结构。

确保在 TreeNode 的构造函数中将 left/right 指针分配给 NULL，并且正确作为 root 传入 D 节点。还请记住删除您通过 new TreeNode 创建的任何节点。如果您在堆栈上创建它们(没有 new 的普通局部变量)，您当然不必删除它们。