后序遍历的非递归算法

❶ c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法

#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}

void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}

void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}

❷ 求一个二叉树的后序遍历非递归算法

// 中序遍历伪代码：非递归版本，用栈实现，版本2
void InOrder2(TNode* root)
{
Stack S;
if( root != NULL )
{
S.push(root);
}
while ( !S.empty() )
{
TNode* node = S.pop();
if ( node->bPushed )
{ // 如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了
Visit(node);
}
else
{ // 左右子树尚未入栈，则依次将 右节点，根节点，左节点 入栈
if ( node->right != NULL )
{
node->right->bPushed = false; // 左右子树均设置为false
S.push(node->right);
}
node->bPushed = true; // 根节点标志位为true
S.push(node);
if ( node->left != NULL )
{
node->left->bPushed = false;
S.push(node->left);
}
}
}
}
对比先序遍历，这个算法需要额外的增加O(n)的标志位空间。另外，栈空间也扩大，因为每次压栈的时候都压入根节点与左右节点，因此栈空间为O(n)。时间复杂度方面，每个节点压栈两次，作为子节点压栈一次，作为根节点压栈一次，弹栈也是两次。因此无论从哪个方面讲，这个方法效率都不及InOrder1。

后序

void postOrder(TreeNode<T> *root)
{
stack<TreeNode<T>*> st;
TreeNode<T> *p = root;
TreeNode<T> *pre = NULL;//pre表示最近一次访问的结点

while(p || st.size()!=0)
{
//沿着左孩子方向走到最左下 。
while(p)
{
st.push(p);
p = p->left;
}
//get the top element of the stack
p = st.top();
//如果p没有右孩子或者其右孩子刚刚被访问过
if(p->right == NULL || p->right == pre)
{
/ isit this element and then pop it
cout << "visit: " << p->data << endl;
st.pop();
pre = p;
p = NULL;

}
else
{
p = p->right;

}
}//end of while(p || st.size()!=0)

}

❸ 求二叉树的前序遍历和后序遍历的算法（非递归）

网络一下就可以知道答案了。直接搜”二叉树的前序遍历和后序遍历的算法“

第一条就是：

http://blog.csdn.net/sky04/article/details/4510266

我只解释一下先序遍历非递归算法，其他的自学一下吧！：

//先序遍历非递归算法

voidPreOrderUnrec(Bitree*t)
{
Stacks;
StackInit(s);//初始化
Bitree*p=t;//二叉树根节点

while(p!=NULL||!StackEmpty(s))
{
while(p!=NULL)//遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;//lchild左子树
}

if(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;//rchild右子树
}//endif

}//endwhile
}

/*Stacks；创建堆栈。这也是堆栈的一个应用。既然你已经学到了二叉树，就应该知道堆栈，可以把以前编写的堆栈程序拿来用。
POP，PUSH堆栈的弹出，压栈。
按照该程序步骤，来演示s和指针p的内容：（完全二叉树为例）
前序遍历次序为：ABCDEFG
1.第一次执行while语句后
栈s[底部，ABC]p=NULL访问了：ABC节点
2.第一次执行if
栈s[底部，AB]p=NULL访问了：ABC节点由于c的右子树为空，所以p=NULL
3.第二次跳过了while
4.第二次执行if
栈s[底部，A]p指向了D访问了：ABC节点
5.第三次执行while语句后
栈s[底部，AD]p=NULL访问了：ABCD节点，本次while循环，只访问了D
。
。
。
剩下步骤的自己来吧!
实际上，递归也是在操作堆栈。
一般的书上应该有这么类似的话：
“利用一个辅助堆栈，可以将递归算法转化为等价的分递归算法”

*/

❹ 后序遍历非递归算法

#include<stdio.h>
#include <stdlib.h>
#define maxsize 50
typedef struct Bnode //声明二叉树的数据结构
{
char data;
struct Bnode *lchild,*rchild;
}bnode,*btree;
typedef struct type
{
btree node;
int flag;
}datatype,*pdatatype;
typedef struct{ //声明栈的数据结构
datatype data[maxsize];//pdatatype data[maxsize]; //类型改为datatype
int top;
}seqstack,*pseqstack;
int i=0;
btree creatbtree(char *s) //创建二叉树
{
btree t;
if(s[i]=='#')
{t=NULL;i++;}
else
{
t=(btree)malloc(sizeof(bnode));
t->data=s[i];i++;
t->lchild=creatbtree(s);
t->rchild=creatbtree(s);
}
return t;
}
void postorder(btree t) //二叉树的后序遍历(非递归)
{
int cout;
pseqstack p;
//pdatatype sq;
//sq=(pdatatype)malloc(sizeof(datatype));
p=(pseqstack)malloc(sizeof(seqstack));
p->top=0;
while(t||!(p->top==0))
{
if(t)
{
//sq->flag=0;
//sq->node=t;
//p->data[p->top]=sq;
p->data[p->top].node = t;
p->data[p->top].flag = 0;
(p->top)++;
t=t->lchild;
}
else
{
//sq=p->data[(p->top)-1];
//t=sq->node;
if(p->data[p->top-1].flag==0)
{
p->data[p->top-1].flag=1;
//sq->node=t;
//p->data[p->top]=sq;
//(p->top)++;
t = p->data[p->top-1].node->rchild;//t=t->rchild;
}
else
{
printf("%c",p->data[p->top-1].node->data); //printf("%c",t->data);
(p->top)--;

//printf("%c",t->data);
//t=NULL;

}
}
}
}

main()
{
btree t;
char *s;
s="abd#g###ce##fh###";
t=creatbtree(s);
printf("\n后序遍历：");
postorder(t);

}

❺ 二叉树后序遍历（非递归）

一，大循环中的第一个循环，当前节点一直往左走一直走到头，并且把走过的节点压栈，这个循环遍历完成后，栈里面都是左边走过但是右边还没有走过的节点

二，从最左边那个没有更左的那个节点，它位于栈顶，因为这时栈顶不是一个右节点，第二个循环跳过，然后把栈顶结点的右节点标记为r并以此作为根节点重复之前的操作

回溯：
因为一直往下层走，总会遇到既没有左节点有没有右节点的节点，就是叶子节点，就开始往回退 取他的右节点，取之前会把该节点标记为r，但是他没有右节点，为null，就会跳过第一个循环，来到第二个，那么这个叶子就从栈中pop掉，新的栈顶结点是那个叶子的父节点，如果没有右节点，那他就成了叶子，更简单，如果有右节点，那么继续二

一步一步推就是这样子，需要考虑所有情况，会把问题想复杂，但是利用递归的思想就好想了
参考递归算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一个函数就是第一个小循环，只走左边，然后把新得到的节点作为根节点，继续调用第一个函数，得到左节点，然后再作为根节点，直到左节点为空；
第二个函数就是最后一个if，非递归算法中是从栈顶取，就是左边走过了的节点，相当于递归中，第一个函数执行完已经返回，然后取他的右节点作为根节点，继续递归
以上回答你满意么？

❻ 二叉树的遍历算法

这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
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

❼ 二叉树后序遍历非递归算法

#include
<stdio.h>
#include
<stdlib.h>
struct
tree
{
char
data;
struct
tree
*lchild;
struct
tree
*rchild;
};
typedef
struct
tree
*
treptr;
treptr
build(treptr
t)//先序建树
{
char
c;
c=getchar();
if(c=='#')
{
t=NULL;
}
else
{
t=(treptr)malloc(sizeof(struct
tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return
t;
}
void
postdorder(treptr
root)//这是递归实现
{
if
(root!=NULL)
{
postdorder(root->lchild);
postdorder(root->rchild);
printf("%c",root->data);
}
}
struct
stack
{
treptr
*top,*base;
};
typedef
struct
stack
*stackptr;
void
init
(stackptr
s)//初始化栈
{
s->base=(treptr*)malloc(sizeof(treptr)*100);
s->top=s->base;
}
void
push(stackptr
s,treptr
t)//入栈
{
*(s->top++)=t;
}
treptr
pop(stackptr
s)//弹出栈顶元素
{
treptr
t;
t=*(--(s->top));
return
t;
}
treptr
gettop(stackptr
s)//取栈顶元素
{
treptr
*l=s->top-1;
return
*(l);
}
void
postorder(treptr
t)//这是非递归后序实现
{
stackptr
s=(stackptr)malloc(sizeof(struct
stack));
treptr
temp=t;
treptr
p;
treptr
lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist)
{
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
int
main()
{
treptr
t=NULL;
t=build(t);
postdorder(t);
printf("非递归后序遍历\
");
postorder(t);
printf("\
");
return
0;
}
程序如上，可以运行。
我空间中有中序遍历的非递归实现。
不过给你写的是后序遍历的递归实现和非递归实现，它两个输出的结果是一致的。
输入
234##5#6##7##回车
就可以看到结果。
中序遍历及其对应树可以参考我空间中的文章
http://hi..com/huifeng00/blog/item/2ca470f56694f62e730eec39.html

❽ 后序遍历的非递归算法是什么

对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历，使用的方法是深度优先遍历树的每一个节点，这些遍历方法都是使用递归函数来进行实现的。

在数据量大的情况下是比较低效的，原因在于系统帮助我们调用了一个栈并且做了诸如保护现场和恢复现场等复杂的操作。

才使得遍历可以使用非常简单的代码来实现，所以我们可以模仿系统中调用的栈自己可以来写一下栈，模仿其中的过程就可以完成对于三种遍历算法的实现，使用自定义的栈来代替系统栈可以得到效率上的提升，下面是对于后序遍历的非递归算法的实现。

简介

从逆后序遍历与先序遍历的关系中我们可以知道逆后序遍历序列为先序遍历交换左右子树的遍历顺序得到的。

所以我们得到了逆后序序列之后然后逆序就可以得到后序遍历的序列了，所以需要两个栈，第一个栈用来存储先序遍历交换左右子树的遍历的中介结果。

❾ 下面是后序遍历二叉树的非递归算法的实现，别人写的，但看不太明白，求详细解释！

先明白后序遍历的原理，再看程序就容易了。后序遍历先访问左子树，再访问右子树，最后访问根。但你的程序从根开始查找，所以先把查找过的根放入栈中（后进先出），然后访问左子树，在根据栈顶的根节点访问右子树（右子树依然要从根判断），最后访问根，访问完后，可以弹出根节点了。那么上一层的根节点就处于栈顶了。这个没人能给你讲清楚。你看懂了，编程和树的遍历也就都懂了。

❿ 后序遍历（ 用递归和非递归的方法一起都要）

我们的数据结构实验也是这题，需要我把我的实验报告给你参考下么！
我这里就只发这部分的代码。
Status PreOrderTraverse(BiTree T)
{
//先序遍历二叉树T的递归算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status PreOrder(BiTree T)
{
//先序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//后序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//后序遍历二叉树T的递归算法
unsigned sign;//记录结点从栈中弹出的次数
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到结点T时压入其指针
push(1);//置标志为1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走过T的左子树
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子树都已走过
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}
另外,团IDC网上有许多产品团购,便宜有口碑