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

⑴ 二叉树非递归遍历的算法

以下为先序，中序，后序三种递归算法

#include
#define MAX 30
typedef struct TreeNode
{
char a;
TreeNode *left;
TreeNode *right;
}TreeNode,*BinTree;
typedef struct
{
TreeNode* data[MAX];
int top;
}SeqStack;
void InitStack(SeqStack &S)
{
S.top=0;
}
int StackEmpty(SeqStack S)
{
if(S.top==0)
return 1;
else return 0;
}
int StackFull(SeqStack S)
{
if(S.top==MAX) return 1;
else return 0;
}
void Push(SeqStack &S,TreeNode *node)
{
if(!StackFull(S))
{
S.data[S.top]=node;
S.top++;
}
else cout<<"Stack is full!\n";
}
void Pop(SeqStack &S,TreeNode* &e)
{
if(!StackEmpty(S))
{
S.top--;
e=S.data[S.top];
}
else cout<<"Stack is empty!";
}
TreeNode* GetTop(SeqStack S)
{
if(!StackEmpty(S))
{
TreeNode *node;
node=S.data[S.top-1];
return node;
}
else cout<<"Stack is empty!";
}

void CreateBinTree(BinTree &T)
{
char b;
cin>>b;
if(b=='0')T=NULL;
else
{
T=new TreeNode;
T->a=b;
CreateBinTree(T->left);
CreateBinTree(T->right);
}
}
void Inorder(BinTree T)
{
TreeNode * p;
SeqStack S;
p=T;
InitStack(S);
while(!StackEmpty(S)||p)
{
while(p)
{
Push(S,p);
p=p->left;
}
if(!StackEmpty(S))
{
Pop(S,p);
cout cout<<"\nA----------二叉树的建立\n";
cout<<"\nB----------非递归先序遍历\n";
cout<<"\nC----------非递归中序遍历\n";
cout<<"\nD----------非递归后序遍历\n";
cout<<"\nX----------退出\n";
}
void main()
{
BinTree T;
char ch='\0';
bool flag=true;
while(flag)
{
info();
cin>>ch;
switch(ch)
{
case'a':
case'A':
cout<<"请按先序次序输入结点，空结点用'0'表示:\n";
CreateBinTree(T);
cout<<"二叉树建立成功!\n";
break;
case'b':
case'B':
cout<<"先序遍历的结果为:\n";
Preorder(T);
break;
case'c':
case'C':
cout<<"中序遍历的结果为:\n";
Inorder(T);
break;
case'd':
case'D':
cout<<"后序遍历的结果为:\n";
Postorder(T);
break;
case'x':
case'X':
flag=false;
break;
default:
cout<<"输入无效,请重新输入!\n";
}
}
}

⑵ 二叉树先序遍历递归算法和非递归算法本质区别

在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
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;
}

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

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

第一条就是：

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
。
。
。
剩下步骤的自己来吧!
实际上，递归也是在操作堆栈。
一般的书上应该有这么类似的话：
“利用一个辅助堆栈，可以将递归算法转化为等价的分递归算法”

*/

⑷ 二叉树非递归先序遍历

题目是
1）问题描述：在主程序中提供下列菜单：
1…建立树
2…前序遍历树
3…中序(非递归)遍历树
4…后序遍历树
0…结束
2）实验要求：定义下列过程：
CreateTree(): 按从键盘输入的前序序列，创建树
PreOrderTree()：前序遍历树（递归）
InOrderTree()：中序(非递归)遍历树
LaOrderTree(): 后序遍历树（递归）
我做得是：
求帮忙改错 或者给我一个程序 求啊啊啊 要下课了 啊啊啊啊
及时的话有追加啊啊啊啊
#include <iostream.h>
#include <stdio.h>
#include <malloc.h>
#define MaxNode 100
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;

void CreateTree(BTNode *&b,char *str)//建立一个二叉树
{
BTNode *St[100];
BTNode *p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':top++;St[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}

void PreOrder(BTNode *b)//前序遍历
{
if(b!=NULL)
{
printf("%c ",b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}

void InOrder(BTNode *b)//中序遍历
{

BTNode *p,*stack[MaxNode];
int top=0;
if(b==NULL) return;
p=b;
while(!(p == NULL && top == 0))
{
while(p!=NULL)
{

if(top<MaxNode-1){stack[top]=p;top++;}
else{printf("栈溢出");return;}
p=p->lchild;
}
if(top<=0)return;
else{top--;p=stack[top];printf("%c",p->data);p=p->rchild;}
}
}

void LaOrder(BTNode *b)//后序遍历
{
if(b!=NULL)
{
LaOrder(b->lchild);
LaOrder(b->rchild);
printf("%c ",b->data);
}
}
void main()
{
int number;
BTNode *b=NULL;
cout<<" 【1】创建树"<<endl<<endl;
cout<<" 【2】先序遍历树"<<endl<<endl;
cout<<" 【3】中序遍历树"<<endl<<endl;
cout<<" 【4】后序遍历树"<<endl<<endl;
cout<<" 【5】结束"<<endl<<endl<<endl;
cout<<"请输入您的选择"<<endl;
cin>>number;
while(number!=5)
{

if(number==1)
{
char str[100];
printf("请输入：");
scanf("%s",&str);
CreateTree(b,str);
printf("树创建成功!\n");
}
else if(number==2)
{
if(b==NULL)
{
printf("对不起，您还没有创建树!\n");
}
else
{
PreOrder(b);
printf("\n");
}
}
else if(number==3)
{
if(b==NULL)
{
printf("对不起，您还没有创建树!\n");
}
else
{
InOrder(b);
printf("\n");
}
}
else if(number==4)
{
if(b==NULL)
{
printf("对不起，您还没有创建树!\n");
}
else
{
LaOrder(b);
printf("\n");
}
}
printf("请输入您的选择:\n");
scanf("%d",&number);
}

}

//以上内容来源于网络知道。http://..com/question/259268815.html
希望对你有帮助

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

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存在的那个分支。接下来再取右子树的左子树
}
}
//其实，用递归也许你更能理解一些。但是，递归本质上也是压栈，只不过是程序压栈，还不如这个效率高

⑹ 先序便利二叉树非递归算法如何理解

递归方式：先访问根，再访问左子树（递归），再访问右子树（递归）

非递归：
当前节点=ROOT;
循环（当前节点不为空）
访问当前节点。--先根，而且处理完后不在需要
如果有右子树，push (右子树）-- 表明在左子树全部处理完后再处理
如果有左子树，当前节点为左子树，continue - 表明优先处理左子树
如果没有子树，当前节点=pop()，continue - 表明一颗子树已经处理完了，需要从堆栈里面把以前记得需要处理的再拿出来。

总的来说，非递归算法是利用堆栈，将不是马上要处理的东西放到堆栈里面，当需要处理的东西不能直接索引的时候。从堆栈中一个再挖出来处理。

⑺ 二叉树先序非递归遍历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");
}

⑻ 二叉树的遍历算法

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

template<class ElemType>//声明类模板 void NonRecurPreOrderHelp(BinTreeNode<ElemType>*r, void(*Visit)(ElemType&))//传递一个模板类型二叉树节点的指针作为参数 { BinTreeNode<ElemType>*cur=r;//接收传递进来的节点指针（作为遍历起始点） Linkstack<BinTreeNode<ElemType>*>s;//链表栈，用于控制将遍历的数据出入栈 while(cur!=NULL) { (*Vitis)(cur->data);//首先将当前节点处的数据转换为*Vitis类型 s.Push(cur);将当前节点压入栈中 if(cur->leftChild!=NULL)//若当前节点的左边的子节点不为空 { cur=cur->leftChild;//将当前遍历节点指向其左子节点 } else if(!s.Empty())//若当前节点的左边的子节点为空，但栈不为空（即栈内还有元素） { while(!s.Empty())//当但栈不为空时 {s.Pop(cur);//将栈内元素出栈 cur=cur->rightChild;//将当前遍历节点设为其右子节点 if(cur!=NULL)break;//若当前的节点不为空，直接退出循环 } } else//若当前节点的左边的子节点为空，但栈为空（即栈内无元素） {cur=NULL;}//将当前遍历节点设为空 }

麻烦采纳，谢谢!

⑽ 怎样实现二叉树的前序遍历的非递归算法

在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
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;
}