二叉树中序非递归遍历算法

#define MAXNODE 100 //二叉树最大节点数
//定义二叉树链式结构
typedef struct BitNode
{
char data; //数据域
struct BitNode *lchild,*rchild;//左右指针域
}BitNode,*BiTree;
//二叉树进行中序非递归遍历
void NRInorder(BiTree t)
{
BiTree s; //s-指向当前节点
BiTree stack[MAXNODE]; //定义栈
int top=-1; //初始化栈顶指针

if(t==NULL)
return;

stack[++top]=t;//根指针入栈
s=t->lchild; //s指向左子树
while(s!=NULL||top!=-1)//当存在节点(涉及到根下右子树)或者栈不为空,进行遍历
{
while(s!=NULL) //如果存在节点,寻找最左子树并入栈
{
if(top>=MAXNODE-1)
{
printf("栈为满\n");
return;
}
stack[++top]=s;//当前节点入栈
s=s->lchild; //左子树进行遍历
}
if(top==-1)
{
printf("栈为空\n");
return;
}
s=stack[top--]; //弹出栈顶元素到s中
printf("%c ",s->data); //输出当前节点元素值
s=s->rchild; //遍历右子树

}

}

对的，实际上如果p=0，是往左探索到头的意思。先要往左探索到头，只有到头了之后才退栈，看右子树。

探索的过程一直是p=p->lchild，如果p左边没有节点了，p->lchild=nullptr了，就说明到头了，开始执行if的第二个分支：

1. pop(s,p)实际上是恢复了p上一个状态，也就是那个叶子节点；

2. visit(p)，中序访问就是每pop一个紧接着就访问一个就是了；

3. p=p->rchild，访问右边，当然，如果右边还没有，下次pop的就是p的上上个状态了，这相当于是从一个叶子节点离开。以此类推。

   不明白的可以继续问。

中序