1、#include<iostream>using namespace std;typedef struct BiTnode//二叉树的二叉链表储存表示{ char data; struct BiTnode *lchild,*rchild;}BiTnode,*BiTree;
2、typedef struct //顺序栈的储存结构{ BiTnode *base; BiTnode *top; int stacksize;}SqStack;
3、int InitStack(SqStack &S)//初始化顺序栈{ S.base=new BiTnode[1000]; if(!S.base)exit(0); S.top=S.base; S.stacksize=1000; return 1;}
4、int StackEmpty(SqStack &S)//判断栈是否为空{ if(S.base==S.top) return 1; else return 0;}
5、int Push(SqStack &S,BiTnode *p)//入栈{ if(S.top-S.base==S.stacksize)return 0; *S.top++=*p; return 1;}
6、int Pop(SqStack &S,BiTnode *q)//出栈{ if(S.top==S.base)return 1; *q=*--S.top; return 0;}
7、void InorderTraver(BiTree T)//中序遍历{ SqStack S; InitStack(S);//初始化一个空栈S BiTnode *p,*q; p=T; q=new BiTnode;//申请一个节点空间，用来存放栈顶弹出的元素 while(p||!StackEmpty(S))//当p非空或者栈S非空时，执行以下操作 { if(p) //如果p非空，则将p进栈，p指向该结点的左孩子 { Push(S,p); p=p->lchild; } else //如果p为空，则弹出栈顶元素并访问，将p指向该结点的右孩子 { Pop(S,q); cout<<q->data; p=q->rchild; } }}
8、void CreateBiTree(BiTree &T)//先序创建二叉树{ char ch; cin>>ch; if(ch=='#')T=NULL; else { T=new BiTnode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }}
9、int main(){ BiTnode *T; CreateBiTree(T); InorderTraver(T); return 0;}
10、以“a*b-c”为实例中序遍历输出
