- #include<iostream>
- #include<stack>
- using namespace std;
- typedef char ElemType ;
- struct BiTreeNode
- {
- ElemType data ;
- BiTreeNode * lchild ,*rchild;
- BiTreeNode ():lchild (0),rchild (0),data(0){} // 构造函数 初始化 bitreeNode;
- };
- typedef BiTreeNode * BiTree;
- void CreateBiTree(BiTree &);
- void PreOrderTraverse(BiTree T);
- void InOrderTraverse(BiTree T);
- void PostOrderTraverse(BiTree T);
- int main()
- {
- BiTree T ; //-+a00*b00-c00d00/e00f00 将此串输入 enter看结果
- CreateBiTree (T);
- PreOrderTraverse(T);
- cout<<endl;
- InOrderTraverse(T);
- cout<<endl;
- PostOrderTraverse(T);
- cout<<endl;
- system ("pause");
- return 0;
- }
- void CreateBiTree (BiTree &T)
- {
- ElemType ch;
- cin>>ch;
- if (ch=='0')
- return ;
- T = new BiTreeNode ;
- T->data = ch ;
- CreateBiTree (T->lchild );
- CreateBiTree (T->rchild );
- }
- void PreOrderTraverse (BiTree T)
- {
- stack<BiTree> s ;
- BiTree p = T;
- while (s.empty ()==false || p )// 栈不为空 或者 不为空树 循环
- {
- if(p) // 树 不为空
- {
- while (p)
- {
- cout<<p->data ;
- s.push (p);
- p=p->lchild ; // 若 p 不为空 则 继续while 循环
- }
- }
- else // 树为空 栈不为空执行 else
- {
- p = s.top()->rchild ; // 此时改变第一个中的 while p
- s.pop(); // 随着 pop 栈会变空
- } // 最后 栈 为空 P 树 为空则 终止循环
- }
- }
- void InOrderTraverse (BiTree T)
- {
- stack <BiTree > s;
- BiTree p=T;
- while (s.empty ()==false || p)
- {
- if(p)
- {
- while (p)
- {
- s.push(p);
- p=p->lchild ; // p进栈 不输出 p 这是开始指向左孩子
- }
- }
- else
- {
- cout<<s.top()->data; // 既 左 孩子的 数据
- p = s.top()->rchild ; // 既 将 p 变为空 下次 在 进入 else 里面 执行 :
- s.pop(); // 此 题 必须 动手画图 以便于 理解 二叉树 和 栈 图
- }
- }
- }
- void PostOrderTraverse (BiTree T )
- {
- stack<BiTree> s;
- stack<bool> bs;
- BiTree p = T ;
- while (s.empty()==false || p )
- {
- if (p)
- {
- while(p)
- {
- s.push(p);
- bs.push(false);
- p=p->lchild ; // 当lchild 为空 时 p为空 那么跳出循环 p为空
- } // 下次大while 是以 栈 s 来判断循环的 直接进入下面 else
- }
- else
- {
- if(bs.top()) // 此时 bs.top 的值 为false 故 直接 进入else 执行
- { // 最好动笔 画出图形 便于理解
- cout<<s.top()->data ;
- s.pop();
- bs.pop();
- }
- else
- bs.top()=true,p=s.top()->rchild ;
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/020120148367.html
来源: http://www.codesnippet.cn/detail/020120148367.html