二叉树中序遍历非递归算法
A. 如何理解二叉树中序遍历的非递归算法
#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; //遍历右子树
}
}
B. 二叉树中序非递归遍历算法
对的，实际上如果p=0，是往左探索到头的意思。先要往左探索到头，只有到头了之后才退栈，看右子树。
探索的过程一直是p=p->lchild，如果p左边没有节点了，p->lchild=nullptr了，就说明到头了，开始执行if的第二个分支：
pop(s,p)实际上是恢复了p上一个状态，也就是那个叶子节点；
visit(p)，中序访问就是每pop一个紧接着就访问一个就是了；
p=p->rchild，访问右边，当然，如果右边还没有，下次pop的就是p的上上个状态了，这相当于是从一个叶子节点离开。以此类推。
不明白的可以继续问。
中序
C. 非递归中序遍历二叉树
//以前曾写过,仅供参考,因为这是截取部分源码,
#include "afx.h"
#include "stdio.h"
#include"iostream.h"
#include "iomanip.h"
#include<malloc.h>
#include<conio.h>
typedef char ElemType; //定义二叉树结点值的类型为字符型
const int MaxLength=100; //结点个数不超过50个
typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void PreCreateBiTree(BiTree &T) //按先序次序输入，构造二叉树
{
char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
PreCreateBiTree(T->lchild);
PreCreateBiTree(T->rchild);
}
}
void NRInOrder(BiTree bt) //非递归的中序遍历算法
{
BiTree stack[MaxLength],p;
int top;
if (bt!=NULL)
{
top=0;
p=bt;
while(p!=NULL||top>0)
{
while(p!=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{
top--;
p=stack[top];
cout<<p->data<<" ";
p=p->rchild;
}
}
}
}
D. 先序遍历二叉树的非递归算法
InitStack(S);//初始化栈
p=T;//取栈顶
while(P||!StackEmpty(S)){ //P存在或者栈非空
if(p) { //p非空，即左子树或者右子树存在
Push(S,p); //将左子树入栈
p=p->lchild; //取下一个左子树
}
else{
Pop(S,p); //出栈，相当于先序遍历了，因为左子树都TMD入栈了，现在反向输出
p=p->rchild; //弹出一个左子树，就同时取其右子树右子树，然后又跳到这个if的最开头那里，p存在的那个分支。接下来再取右子树的左子树
}
}
//其实，用递归也许你更能理解一些。但是，递归本质上也是压栈，只不过是程序压栈，还不如这个效率高
E. 二叉树后序遍历非递归算法程序跪求解释
一，大循环中的第一个循环，当前节点一直往左走一直走到头，并且把走过的节点压栈，这个循环遍历完成后，栈里面都是左边走过但是右边还没有走过的节点
二，从最左边那个没有更左的那个节点，它位于栈顶，因为这时栈顶不是一个右节点，第二个循环跳过，然后把栈顶结点的右节点标记为r并以此作为根节点重复之前的操作
回溯：
因为一直往下层走，总会遇到既没有左节点有没有右节点的节点，就是叶子节点，就开始往回退 取他的右节点，取之前会把该节点标记为r，但是他没有右节点，为null，就会跳过第一个循环，来到第二个，那么这个叶子就从栈中pop掉，新的栈顶结点是那个叶子的父节点，如果没有右节点，那他就成了叶子，更简单，如果有右节点，那么继续二
一步一步推就是这样子，需要考虑所有情况，会把问题想复杂，但是利用递归的思想就好想了
参考递归算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一个函数就是第一个小循环，只走左边，然后把新得到的节点作为根节点，继续调用第一个函数，得到左节点，然后再作为根节点，直到左节点为空；
第二个函数就是最后一个if，非递归算法中是从栈顶取，就是左边走过了的节点，相当于递归中，第一个函数执行完已经返回，然后取他的右节点作为根节点，继续递归
F. 二叉树的非递归中序遍历算法 要有结果输出 跪求了 谢谢
太懒了，就不告诉你
G. 数据结构的中序遍历二叉树的结点的非递归算法
如图
H. 关于《中序遍历二叉树的非递归算法》的论文
实用《数据结构》编程——二叉树的建立、中序遍历非递归C程序 宋丽敏 <正>近年来,伴随着计算机应用技术的快速发展,系统程序和应用程序的规模越来越大,应用领域越来越广泛.计算机的应用已不再局限于科学计算,而更多地应用于控制、管理及数据处理等非数值计算的处理工作.需要通过计算机加工、处理的数据对象也日益复杂化.《数据结构》课程就是一门以这些复杂的非数值型数据为研究对象,研【作者单位】：河北省廊坊职业技术学院(西校区) 065000【分类号】：G634.6【DOI】：cnki:ISSN:1005-9741.0.2004-02-009【正文快照】：近年来,伴随着计算机应用技术的快速发展,系统程序和应用程序的规模越来越大,应用领域越来越广泛.计算机的应用已不再局限于科学计算,而更多地应用于控制、管理及数据处理等非数值计算的处理工作.需要通过计算机加工、处理的数据对象也日益复杂化.《数据结构》课程就是一门以这 …… http://www.cnki.com.cn/Article/CJFDTotal-LKJX200402009.htm