#include <stack>
#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;
typedef struct node
{
int flag;
char value;
struct node *lchild;
struct node *rchild;
}Node, *PNode;
void CreateBinaryTree(PNode &root) /* 前序遍历的递归方式动态建立二叉树 */
{
char ch;
scanf("
%c", &ch);
if(ch == '#') {root = NULL; return ;}
root = (Node *)malloc(sizeof(Node));
root->flag = 0; // flag==0 ---> 第一次经过:父节点-->自身-->左孩子
// flag==1 ---> 第二次经过:左孩子-->自身-->右孩子
// flag==2 ---> 第三次经过:右节点-->自身-->父节点
root->value = ch;
CreateBinaryTree(root->lchild);
CreateBinaryTree(root->rchild);
}
void visit(PNode &pointer)
{
printf("%c ", pointer->value);
}
void OrderTraversal(PNode &root) /* 调整visit(temp)出现位置实现前中后序遍历 */
{
stack<Node> ss;
PNode temp = root;
while(!ss.empty() || temp->flag!=2 /* while内部:if --- else if --- else 结构 */
{
if(temp->flag == 0)
{
visit(temp); // PreorderTraversal
if(temp->lchild != NULL)
{
temp->flag = 1;
ss.push(*temp);
temp = temp->lchild;
}
else
{
//visit(temp); // InorderTraversal / PostorderTraversal
temp = &(ss.top());
ss.pop();
}
}
else if(temp->flag == 1)
{
//visit(temp); // InorderTraversal
temp->flag = 2;
ss.push(*temp);
temp = temp->rchild;
}
else
{
//visit(temp); // PostorderTraversal
temp = &(ss.top());
ss.pop();
}
}
//visit(temp); // PostorderTraversal
}
int main()
{
cout << "Input element in preorder:" << endl;
PNode root;
CreateBinaryTree(root);
OrderTraversal(root);
return 0;
}