#include <iostream>
#include <stack>
using namespace std;
template<typename T>
struct BiTreeNode
{
T data;
BiTreeNode *Lchild, *Rchild;
BiTreeNode() :Lchild(NULL), Rchild(NULL){}
BiTreeNode(const T& d, BiTreeNode *lchild = NULL, BiTreeNode *rchild = NULL) :data(d), Lchild(lchild), Rchild(rchild){}
};
template<typename T>
class BiTree
{
public:
BiTree(){ root = NULL; }
~BiTree(){ /*makeEmpty();*/ }
//void makeEmpty(BiTreeNode<T>* &root);
void createBiTree(BiTreeNode<T>* &root);
void output(BiTreeNode<T> *root);
void preOrder(BiTreeNode<T>* &root);
void preOrder_2(BiTreeNode<T>* &root);
void levelOrder(BiTreeNode<T>* &root);
void inOrder(BiTreeNode<T>* &root);
void postOrder(BiTreeNode<T>* &root);
BiTreeNode<T> * root;
};
template<typename T>
void BiTree<T>::createBiTree(BiTreeNode<T>* &root)
{
//按照广义表方式输入
stack<BiTreeNode<T>* >s;
root = NULL;
BiTreeNode<T> *p, *t;
int k;
char ch;
cin >> ch;
while (ch != '#')
{
switch (ch)
{
case '(':
s.push(p); k = 1; break;
case ')':
t = s.top(); s.pop(); break;
case ',':
k = 2; break;
default:
p = new BiTreeNode<T>(ch);
if (root == NULL)
{
root = p;
}
else if (k==1)
{
t=s.top();
t->Lchild = p;
}
else
{
t=s.top();
t->Rchild = p;
}
}
cin >> ch;
}
cout << endl;
}
template<typename T>
void BiTree<T>::output(BiTreeNode<T> *root)
{
if (root)
{
cout << root->data << " ";
output(root->Lchild);
output(root->Rchild);
}
}
template<typename T>
void BiTree<T>::preOrder(BiTreeNode<T>* &root)
{
//先存右结点，再存做结点，出栈真好相反：先出左结点，后出右结点
stack<BiTreeNode<T>* > s;
BiTreeNode<T> * current;
s.push(root);
while (!s.empty())
{
current = s.top();
s.pop();
cout << current->data << " ";
if (current->Rchild)
{
s.push(current->Rchild);
}
if (current->Lchild)
{
s.push(current->Lchild);
}
}
cout << endl;
}
template<typename T>
void BiTree<T>::preOrder_2(BiTreeNode<T>* &root)
{
//只存右结点
stack<BiTreeNode<T>* > s;
BiTreeNode<T>* current = root;
s.push(NULL);
while (current)
{
cout << current->data << " ";
if (current->Rchild)
{
s.push(current->Rchild);
}
if (current->Lchild)
{
current = current->Lchild;
}
else
{
current = s.top();
s.pop();
}
}
cout << endl;
}
template<typename T>
void BiTree<T>::levelOrder(BiTreeNode<T>* &root)
{
}
template<typename T>
void BiTree<T>::inOrder(BiTreeNode<T>* &root)
{
stack<BiTreeNode<T>* > s;
BiTreeNode<T> *current = root;
do
{
while (current)
{
s.push(current);
current = current->Lchild;
}
if (!s.empty())
{
current = s.top();
cout << current->data << " ";
s.pop();
current = current->Rchild;
}
} while (current||!s.empty());
cout << endl;
}
/************************************************************************
//后序遍历（非递归形式）
//思想：从根节点开始，向左走到尽头，并入栈，同时设置标志位为1.
//出栈时如果这个节点有右子树，则判断是第几次访问，如果是第1次访问，
//则不出栈，将标志位改为2；如果是第二次访问，则出栈。
************************************************************************/
template<typename T>
void BiTree<T>::postOrder(BiTreeNode<T>* &root)
{
stack<BiTreeNode<T>* > s;
stack<int> flag_s;
unsigned flag;
BiTreeNode<T>* current = root;
s.push(current);
flag_s.push(1);
while (!s.empty())
{
while ( current && current->Lchild )
{
current = current->Lchild;
s.push(current);
flag_s.push(1);
}
if (!s.empty())
{
flag = flag_s.top();
flag_s.pop();
current = s.top();
if (current->Rchild && flag==1)
{
flag_s.push(2);
current = current->Rchild;
s.push(current);
flag_s.push(1);
}
else
{
s.pop();
cout << current->data << " ";
current = current->Rchild;
}
}
}
cout << endl;
}
void main()
{
BiTree<char>* bt = new BiTree<char>();
cout << "广义表的方式非递归建立二叉树：eg:A(B(D,E),C(,F)):" << endl;
bt->createBiTree(bt->root);
/*cout << endl << endl;
bt->output(bt->root);*/
cout << "非递归先序（方法1）：" << endl;
bt->preOrder(bt->root);
cout << "非递归先序(方法2）：" << endl;
bt->preOrder_2(bt->root);
cout << "非递归中序遍历：" << endl;
bt->inOrder(bt->root);
cout << "非递归后序遍历：" << endl;
bt->postOrder(bt->root);
while (1)
{
}
}
