我正在做这个作业,我需要按前序、后序和中序打印我的二叉搜索树。但是,似乎只有我的中序方法有效。我使用以下测试用例来检查我的工作。
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;
}