#include<iostream>
#include<stack>
using namespace std; //定义二叉树结点链式存储结构
struct BiTNode{int data;//数据域struct BiTNode *lchild,*rchild;//左右孩子指针
}*BiTree;//中序遍历函数声明
int InOrder(struct BiTNode *BiTree);int main()
{//初始化结点struct BiTNode node1,node2,node3,node4,node5,node6,node7,node8,node9,node10,node11;node1=(struct BiTNode){6,&node2,&node3};node2=(struct BiTNode){4,&node4,&node5};node3=(struct BiTNode){8,&node6,&node7};node4=(struct BiTNode){1,NULL,&node8};node5=(struct BiTNode){5,NULL,NULL};node6=(struct BiTNode){7,NULL,NULL};node7=(struct BiTNode){11,&node9,NULL};node8=(struct BiTNode){3,&node10,NULL};node9=(struct BiTNode){9,NULL,&node11};node10=(struct BiTNode){2,NULL,NULL};node11=(struct BiTNode){10,NULL,NULL};//建树BiTree=&node1;InOrder(BiTree);cout << endl;return 0;
}//中序遍历-非递归实现
int InOrder(struct BiTNode *BiTree){stack<struct BiTNode*> s;struct BiTNode *p;//遍历指针p=BiTree;if(BiTree==NULL){return 0;}while(p||!s.empty()){if(p){s.push(p);//cout << "压栈:" << p->data << endl;p=p->lchild;} else {p=s.top();cout << p->data << " ";s.pop();p=p->rchild;}}return 0;
}