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

[关于树的对联]明月秋风无尽藏长楸古柏是佳朋成阴乔木天然爽过雨闲花自在香绿树岩前疏复密白云窗外卷还舒柳絮一天晴如雪松亭十里夜闻朝千条嫩柳垂青琐百啭流莺入建章名园另有天...+阅读

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

typedef struct node { //定义树的结点

int data;

struct node *left;

struct node *right;

} *btree;

void AfterTraverseNotRecursive(node *root) //非递归后序遍历

{

btree p;

btree stack[5];

int tag[5];

int top = 0;

if (root != NULL)

{

p = root;

while (p != NULL || top != 0) {

while (p != NULL)

{

stack[++top] = p;

tag[top] = 0;

if (p != NULL)

p = p->left;

}

if (top > 0)

{

p = stack[top];

while(tag[top] == 1)

{

printf(＂%d＂, p->data);

p = stack[--top];

}

if (top > 0)

{

p = p->right;

tag[top] = 1;

}

};

free(stack);

free(tag);

free(p);

}

二叉树非递归后序遍历的思路是什么

前序：根-左-右；

中序：左-根-右；

后序：左-右-根。

遍历的思路有3个重点：

1）利用堆栈实现递归

2）树中结点要有指向父结点的指针 //后序遍历用不上这一条

3）树中结点要有标志记录是否已被访问过

上述3点其实就是自己来完成原来递归实现中系统帮你做的事

还有一点要注意，是“左-右-根”，压栈就要先右后左

Class B-Tree{

B-Tree left;

B-Tree right;

B-Tree father;

Boolean visited = false； //初始值设为false

value； //树中存的值，可以是任何类型

}

Stack s;

B-Tree t； //要遍历的树

s.push(t)

while (!s.empty()){

Boolean hasChildren = false; //hasChildren是有子结点需要处理的意思

t = s.top();

if(t.right null & ! t.right.visited) {

s.push(t.right);

hasChildren = true;

}

if (t.left null ! t.left.visited){

s.push(t.left);

hasChildren = true;

}

if (! hasChildren) {

out.print(t.value)； // 输出结点

t.visited = true;

s.pop();

}

下面是后序遍历二叉树的非递归算法的实现别人写的但看不太明

#includeusing namespace std;#include#include#include#define maxsize 20 //最大结点个数//#define N 14 //必须输入结点个数（包含虚结点）#define M 10 //最大深度 typedef struct node{ char data; int m； //结点的深度 struct node*lchild,*rchild; }Bitree; Bitree*Q[maxsize]; Bitree*creatree() { char ch; int front,rear; // int i=1; Bitree *T,*s; T=NULL; front=1; rear=0; coutch; s=NULL; if(ch!='') { s=(Bitree*)malloc(sizeof(Bitree)); s->data =ch; s->lchild =s->rchild =NULL; } rear++; Q[rear]=s; if(rear==1) { T=s; T->m=1； //父结点深度为一 } else{ if(s!=NULL&Q[front]!=NULL) if(rear%2==0) { Q[front]->lchild =s; Q[front]->lchild ->m =Q[front]->m+1; } else { Q[front]->rchild =s; Q[front]->rchild ->m =Q[front]->m+1; } if(rear%2==1) front++; } //i++; cin>>ch; } return T; } int countleaf(Bitree* T) { if(T==NULL) return (0); else if((T->lchild==NULL)&(T->rchild==NULL)) return(1); else return (countleaf(T->lchild)+countleaf(T->rchild)); } int treedepth(Bitree *T) { if(T==NULL) return (0); else { if(treedepth(T->lchild )>treedepth(T->rchild )) return(treedepth(T->lchild )+1); else return (treedepth(T->rchild )+1); } } void output(Bitree*T) //输出打印二叉数 { int i; if(T!=NULL) { output(T->rchild )； //右根左遍历二叉数，结果从上到下显示 for(i=1;im) cout

分别写出以非递归方式按前序中序和后序遍历二叉树的程序

#include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode * lchild,*rchild; }BiTNode,*BiTree; typedef BiTree SElemType; typedef struct{ SElemType *base,*top; int stacksize; }SqStack； //栈的基本操作 void InitStack(SqStack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) printf(＂OVERFLOW＂); S.top=S.base; S.stacksize=STACK_INIT_SIZE; } int GetTop(SqStack S,SElemType &e){ if(S.top==S.base) return 0; e=*(S.top-1); return 1; } int StackEmpty(SqStack S){ if(S.top==S.base) return 1; else return 0; } int Push(SqStack &S,SElemType e){ if(S.top-S.base>=S.stacksize){ S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) printf(＂OVERFLOW＂); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return 1; } int Pop(SqStack &S,SElemType &e){ if(S.top==S.base) return 0; e=*--S.top; return 1； } //树的基本操作 void InitBiTree(BiTree &T){ T=(BiTNode *)malloc(sizeof(BiTNode)); if(!T) printf(＂OVERFLOW＂); T->lchild=NULL; T->rchild=NULL; } void CreatBiTree(BiTree &T){ char ch; scanf(＂%c＂,&ch); if(ch==' ') T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf(＂OVERFLOW＂); T->data=ch; CreatBiTree(T->lchild); CreatBiTree(T->rchild); } } int Depth(BiTree T){ // 返回二叉树的深度 int depth,depthLeft,depthRight; if (!T) depth = 0; else { depthLeft=Depth( T->lchild ); depthRight=Depth( T->rchild ); depth=1+ (depthLeft>depthRight? depthLeft:depthRight); } return depth; } int Print(TElemType e){ printf(＂%c＂,e); return 1; }