遍历二叉树非递归算法
A. 先序便利二叉树非递归算法如何理解
递归方式：先访问根，再访问左子树（递归），再访问右子树（递归）
非递归：
当前节点=ROOT;
循环（当前节点不为空）
访问当前节点。--先根，而且处理完后不在需要
如果有右子树，push (右子树）-- 表明在左子树全部处理完后再处理
如果有左子树，当前节点为左子树，continue - 表明优先处理左子树
如果没有子树，当前节点=pop()，continue - 表明一颗子树已经处理完了，需要从堆栈里面把以前记得需要处理的再拿出来。
总的来说，非递归算法是利用堆栈，将不是马上要处理的东西放到堆栈里面，当需要处理的东西不能直接索引的时候。从堆栈中一个再挖出来处理。
B. 二叉树的遍历算法
这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
1.先序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//访问根结点
p=p->rchild;
//通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍历左子树
{
x.ptr
=
p;
x.tag
=
L;
//标记为左子树
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag为R，表示右子树访问完毕，故访问根结点
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec
C. 二叉树中序遍历的非递归算法
推荐这篇文章，把二叉树的前序、中序和后续的递归和非递归算法都讲了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html
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. 二叉树先序非递归遍历c语言算法
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s->base) exit(1); //抛出异常
s->top=s->base; //栈顶=栈尾 表示栈空
s->stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //抛出异常
s->top=s->base+s->stacksize; //感觉这一句没用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //进栈 栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //栈空 返回0
--s->top;*e=*(s->top); //栈顶前移 取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间
ch=getchar();
if(ch!='#'&&ch!='\n') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 骤
return ht;
}
else return NULL;
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根结点
CreateBiTree(&(*T)->lchild); //构造左子树
CreateBiTree(&(*T)->rchild); //构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/
/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r结点表示访问了右子树 代替标志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//层次遍历二叉树 用队列 哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht;
printf("先序非递归建立一个二叉树:");
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建立
{
printf("先序遍历输出二叉树:");
preordertraverse(ht);
putchar('\n');
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar('\n');
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉树\n");
}
F. 二叉树中序遍历非递归算法(c语言实现）
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0
struct node
{
char data;
struct node *lchild;
struct node *rchild;
};
//先序，中序 建树
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;
head=null;
if(n<=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}
//中序递归遍历
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head->lchild );
printf("%c",head->data );
inorder(head->rchild );
}
}
//中序非递归遍历
void inorder1(struct node *head)
{
struct node *p;
struct node *stack[20];
int top=0;
p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%c ",p->data );
p=p->rchild ;
}
}
//主函数
int main()
{
struct node * head;
char pre[30],ord[30];
int n;
gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("\n");
inorder1(head);
printf("\n");
}
//测试事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
几个月前自己编写，原版
vc++ 6.0实验通过
怎么样，老板，第一次上网络知道，好激动
给点面子
给分！给分啊
G. C#的二叉树中序遍历非递归算法求详细解释！
object e = null; //声明一个变量存放地址
SqStack S = new SqStack(); //声明一个栈，用来存放遍历过程中非末级节点
TreeNode p = t; //声明一个节点变量p 接收函数传来的参数 t
while (p != null || !S.SqStackEmpty()) //从跟节点开始遍历，只要 p！=null （当前该节点还有子节点） 或者 栈 S 没用清空，循环执行下去。
{
if (p != null)
{
S.SqStackPush(p); 该节点有子节点，先把该节点保存入栈，（栈是后进先出，正好先遍历完子节点才遍历父节点的控制作用，栈的最底部存的是根节点，最后才弹出遍历，遍历完后，!S.SqStackEmpty() 就不成立了，while循环结束）
p = p.left; // 上一步p变量的节点压入栈保存后，转而获取左边子节点，继续循环，如果这是p=null，也就是刚压入栈的节点没有子节点，开始执行 else 里的语句
}
else
{
S.SqStackPop(ref e); //弹出刚压入栈的节点，存放到 e ref e 是指存放该节点的地址
p = (TreeNode)e; 类型强制转化成 节点类型，因为 e 声明的是
object类型。付值给p，
Console.Write(p.data + " "); //输出p的数据。
p = p.right; //转而读取该节点右边的树，开始新的循环。
}
H. 二叉树的非递归遍历有什么优点
递归和非递归只是解决问题的方法的不同，本质还是一样的。
2. 递归算法相对于非递归算法来说效率通常都会更低
2.1 递归算法会有更多的资源需要压栈和出栈操作（不仅仅是参数，还有函数地址等）
2.2 由于编译器对附加的一些栈保护机制会导致递归执行的更加低效
3. 使用循环代替递归算法，通常可以获得更好的执行效率和空间效率，在二叉树层次较深的情况下，采用非递归方式遍历能够有效的提升遍历的性能。
I. 二叉树先序遍历递归算法和非递归算法本质区别
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空，就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
J. 二叉树后序遍历（非递归）
一，大循环中的第一个循环，当前节点一直往左走一直走到头，并且把走过的节点压栈，这个循环遍历完成后，栈里面都是左边走过但是右边还没有走过的节点
二，从最左边那个没有更左的那个节点，它位于栈顶，因为这时栈顶不是一个右节点，第二个循环跳过，然后把栈顶结点的右节点标记为r并以此作为根节点重复之前的操作
回溯：
因为一直往下层走，总会遇到既没有左节点有没有右节点的节点，就是叶子节点，就开始往回退 取他的右节点，取之前会把该节点标记为r，但是他没有右节点，为null，就会跳过第一个循环，来到第二个，那么这个叶子就从栈中pop掉，新的栈顶结点是那个叶子的父节点，如果没有右节点，那他就成了叶子，更简单，如果有右节点，那么继续二
一步一步推就是这样子，需要考虑所有情况，会把问题想复杂，但是利用递归的思想就好想了
参考递归算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一个函数就是第一个小循环，只走左边，然后把新得到的节点作为根节点，继续调用第一个函数，得到左节点，然后再作为根节点，直到左节点为空；
第二个函数就是最后一个if，非递归算法中是从栈顶取，就是左边走过了的节点，相当于递归中，第一个函数执行完已经返回，然后取他的右节点作为根节点，继续递归
以上回答你满意么？