#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct node;
typedef node *pNode;
struct node {
???? char data;
???? pNode left, right;
};
string line;
string::iterator it;
// 前序擴展序列建立二叉樹??
void plant(pNode &root)
{
???? if (it == line.end())
???????? return;
???? char data = *it++;
???? if (data == '/')
???????? root = NULL;
???? else {
???????? root = new node();
???????? root->data = data;
???????? plant(root->left);
???????? plant(root->right);
???? }
}
// 先序遍歷??
void pre_order(pNode root)
{
???? stack<pNode> s;
???? while (root != NULL || !s.empty())
???? {
???????? if (root != NULL) {
???????????? cout << root->data << " ";
???????????? s.push(root);
???????????? root = root->left;
???????? } else {
???????????? root = s.top();
???????????? s.pop();
???????????? root = root->right;
???????? }
???? }
}
// 中序遍歷??
void in_order(pNode root)
{
???? stack<pNode> s;
???? while (root != NULL || !s.empty())
???? {
???????? if (root != NULL) {
???????????? s.push(root);
???????????? root = root->left;
???????? } else {
???????????? root = s.top();
???????????? s.pop();
???????????? cout << root->data << " ";
???????????? root = root->right;
???????? }
???? }
}
// 壓棧的參數類型，包括局部變量和行號??
struct stack_arg {
???? stack_arg(pNode _root, int _line)
???? : root(_root), line(_line) { }
???? pNode root;
???? int line;
};
// 后序遍歷??
void post_order(pNode root)
{
???? stack<stack_arg> s;
???? s.push(stack_arg(root, 1));
???? while (!s.empty())
???? {
???????? switch (s.top().line) {
???????? case 1:
???????????? if (s.top().root == NULL)
???????????????? s.pop();
???????????? else
???????????????? s.top().line = 2;
???????????? break;
???????? case 2:
???????????? s.top().line = 3;??
???????????? s.push(stack_arg(s.top().root->left, 1));
???????????? break;
???????? case 3:
???????????? s.top().line = 4;
???????????? s.push(stack_arg(s.top().root->right, 1));
???????????? break;
???????? case 4:
???????????? cout << s.top().root->data << " ";
???????????? s.pop();
???????????? break;
???????? }
???? }
}
int main()
{
???? cin >> line;
???? it = line.begin();
???? pNode root = NULL;
???? plant(root);
???? cout << "先序遍歷" << endl;??
???? pre_order(root);
???? cout << endl;
???? cout << "中序遍歷" << endl;??
???? in_order(root);
???? cout << endl;
???? cout << "后序遍歷" << endl;??
???? post_order(root);
???? cout << endl;
???? system("pause");
???? return 0;
}
/*
input
???? ABDI//J//EK//LQ///CFM//N//GO//P//
output
???? 先序遍歷:
???? A B D I J E K L Q C F M N G O P
???? 中序遍歷
???? I D J B K E Q L A M F N C O G P
???? 后序遍歷??
???? I J D K Q L E B M N F O P G C A