二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。

树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应~

//层次遍历代码

template
void BinTree::view()
{
if (IsNull()) return;
deque*> q;

TreeNode* temp;
q.push_back(root);
while(!q.empty())
{
temp = q.front();
q.pop_front();
coutdata;
if (temp->Left!=NULL)
q.push_back(temp->Left);
if (temp->Right!=NULL)
q.push_back(temp->Right);
}
cout<<endl;
}



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 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语言描述，清华大学出版社，1997年4月第1版），第6章树与二叉树，6.3遍历二叉树和线索二叉树。

遍历二叉树的非递归算法，教材的描述如下（见130页）：

仿照递归算法执行过程中递归工作栈的状态变化状况可直接写出相应的非递归算法。例如，从中序遍历递归算法执行过程中递归工作栈的状态可见：（1）工作记录中包含两项，其一是递归调用的语句编号，其二是指向根结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈；（2）若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶记录中指针所指的根结点；（3）若是从右子树返回，则表明当前曾的遍历结束，应继续退栈。从另一角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。由此可得两个中序遍历二叉树的非递归算法如下：

=============================================================

算法一：

Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。

InitStack(S);
Push(S,T); //根指针进栈

while(!StackEmpty(s))
{
while(GetTop(S,p)&&p)
Push(S,p->lchild); //向左走到尽头
Pop(S,p); //空指针退栈
if(!StackEmpty(S)) //访问结点，向右一步
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
Push(S,p->rchild);
}//if
}//while
return OK;
}//InOrderTraverse 算法一
============================================================
============================================================
算法二：

Status InOrderTraverse(BiTree T, Status (*Visit)(TelemType e))
{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
InitStack(S);
p=T;
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}//if 根指针进栈，遍历左子树
else
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
p=p->rchild;
}//else 根指针退栈，访问根结点，遍历右子树
}//while
}InOrderTraverse() 算法二
============================================================

我的问题是，文字描述中提到的“从中序遍历递归算法执行过程中递归工作栈的状态可见：……”的这一部分。我不明白什么是“栈顶记录中的指针”，什么是“工作记录”。不明白第（2）句话中，先说“栈顶记录中的指针值为空”的时候怎么怎么样，后面为什么又会有对“栈顶记录中指针所指的根结点”的访问？这不是前后矛盾的吗？在读完后面的代码并作了认真的分析之后，仍不明白这一段话到底描述了一个什么样的过程，不理解转化成非递归过程的具体实现。请达人指教。
问题补充：参考：

对代码中与栈有关的函数的说明：
InitStack(&S) 构造一个空栈S；
Push(&S,e) 栈已存在时，插入元素e为新的栈顶元素；
StackEmpty(S) 栈已存在时，若为空栈返回TRUE，否则返回FALSE；
GetTop(S,&e) 栈已存在且非空时，用e返回S的栈顶元素；
Pop(&S,&e) 栈S存在且非空时，删除栈顶元素，并用e返回其值；
——摘自该书45页。

中序遍历二叉树的操作递归定义：
若二叉树为空，则空操作；
否则
（1） 中序遍历左子树；
（2） 访问根结点；
（3） 中序遍历右叉树；
——摘自该书128页。

递归过程转为非递归过程的实质：
将原由系统管理的递归工作栈改为由程序员管理。在非递归过程中，递归工作栈同样起着两个作用：其一是将递归调用室的实在参数和返回地址传递给下一层递归；其二是保存本层参数和局部变量，以便从下一层返回本层时继续恢复使用。如果将栈的每一层视为一项待处理的事务，则栈顶记录则是当前急待处理的事务。
——摘自《数据结构》PASCAL语言描述，严蔚敏、吴伟民著，清华大学出版社。



//利用栈将二叉树递归算法转化为非递归算法

#define struct_sizes 20
#define adds 10

typedef struct bitnode//二叉树的定义
{
int data;//二叉树元素数据类型
struct bitnode *lchild,*rchild;//左右孩子
}*bitree;


typedef struct
//顺序栈的定义
{
bitree *base;//栈底指针
bitree *top;//栈顶指针
int stacksize;
}sqstack;

int initstack(sqstack &S)//新建一个空栈
{
S.base=(bitree *)malloc(struct_sizes*sizeof(bitree));
if(!S.base)return 0;
S.top = S.base;
S.stacksize = struct_sizes;
return 1;
}//initstack

int stackempty(sqstack S)
//判断栈是否为空
{
if(S.base==S.top)return 1;
else return 0;
}

int push(sqstack &S,bitree e)//进栈
{
if(S.top - S.base >= S.stacksize)//栈满重新分配空间
{
S.base = (bitree *)realloc(S.base,(S.stacksize + adds) * sizeof (bitree));
if(!S.base)return 0;
S.top = S.base + S.stacksize;
S.stacksize += adds;
}
*(S.top++)=e;
return 1;
}//push

int pop(sqstack &S,bitree &e)//出栈
{
if(S.top == S.base)return 0;
e = * --S.top;
return 1;
}//pop

int gettop(sqstack S,bitree &e)//取栈顶元素
{
if(S.top == S.base) return 0;
e = *(S.top - 1);
return 1;
}//gettop


int mid_travel(bitree T)//递归二叉树中序遍历
{
if(!T)return 0;
else
{
if(T->lchild)mid_travel(T->lchild);
printf(" %d",T->data);
if(T->rchild)mid_travel(T->rchild);
}
return 1;
}


int mid_norecursion(bitree T)
//中序遍历二叉树T的非递归算法，打印每个数据
{
sqstack S;
bitree p;
if(!T)return 0;
initstack(S);push(S,T);//根指针进栈
while(!stackempty(S))
{
while(gettop(S,p)&&p)push(S,p->lchild);//向左走到尽头
pop(S,p); //空指针退栈
if(!stackempty(S))//访问结点，向右一步
{
pop(S,p);printf(" %d",p->data);
push(S,p->rchild);
}
}
return 1;
}
参考资料：http://zhidao.baidu.com/question/16519850.html

文件 main.cpp 代码如下：

#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
");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：
");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("
中序递归遍历二叉树：
");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("
后序递归遍历二叉树：
");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
这样可以么？

二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。
二叉树有两种存储结构：顺序存储和链式存储
顺序存储： （对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用）
[cpp] view plaincopy
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
链式存储：
[csharp] view plaincopy
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;

二叉树三种递归的遍历方法：
先序遍历 访问根节点→先序遍历左子树→先序遍历右子树
中序遍历 中序遍历左子树→访问根节点→中序遍历右子树
后序遍历 后序遍历左子树→后序遍历右子树→访问根节点
二叉树遍历的递归算法：
[cpp] view plaincopy
void preOrder(BTNode *b) //先序遍历递归算法
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //中序遍历递归算法
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //后序遍历递归算法
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
二叉树非递归遍历算法：
有两种方法：①用栈存储信息的方法 ②增加指向父节点的指针的方法 暂时只介绍下栈的方法
先序遍历：
[cpp] view plaincopy
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
中序遍历：
[cpp] view plaincopy
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
后序遍历：
[cpp] view plaincopy
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //如果标识位为true,则表示入栈
}
}
}
层次遍历算法：（用队列的方法）
[cpp] view plaincopy
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}<span style=""></span>
已知先序和中序求后序的算法：（已知后序和中序求先序的算法类似，但已知先序和后序无法求出中序）
[cpp] view plaincopy
int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */
/* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */
/* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /* 非法子树，完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */
return ;
}
c=pre[pre_s]; /* c储存根节点。 */
k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */
printf("%c",c); /* 根节点输出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}

// 二叉树的建立和遍历算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char TElemtype;
typedef struct Tnode
{
TElemtype data;
struct Tnode *lchild,*rchild;
}Tnode,*BTree;
void createTree(BTree &T);//创建一颗二叉树
void preorder(BTree T);//二叉树的递归先序遍历
void inorder(BTree T);//二叉树的递归中序遍历
void postorder(BTree T);//二叉树的递归后序遍历
void levelorder(BTree T);//二叉树的非递归层次遍历
int main( )
{
BTree T;

printf("请输入先序数据，创建二叉树，@为空\n");
createTree(T);
printf("the preorder is :\n");
preorder(T);
printf("\n");
printf("the inorder is :\n");
inorder(T);
printf("\n");
printf("the postorder is :\n");
postorder(T);
printf("\n");
printf("the levelorder is :\n");
levelorder(T);
printf("\n");
return 0;
}
void createTree(BTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='@')
T=NULL;
else
{
T=(Tnode*)malloc(sizeof(Tnode));
if(!T)
exit (0);
T->data=ch;
createTree(T->lchild );
createTree(T->rchild );
}
}//creatTree
void preorder(BTree T)
{
if(T)
{
printf("%c",T->data );
preorder(T->lchild);
preorder(T->rchild );
}
}//preorder
void inorder(BTree T)
{
if(T)
{
inorder(T->lchild );
printf("%c",T->data );
inorder(T->rchild );
}
}//inorder
void postorder(BTree T)
{
if(T)
{
postorder(T->lchild );
postorder(T->rchild );
printf("%c",T->data );
}
}//postorder
void levelorder(BTree T)
{
int x=0,y=0;
BTree p,Q[100];
if(T)
{
y++;
Q[y]=T;
}
while(x!=y)
{
x++;
p=Q[x];//访问P节点
printf("%c",p->data );
if(p->lchild )//p节点的左右孩子进队列
{
y++;
Q[y]=p->lchild ;
}
if(p->rchild )
{
y++;
Q[y]=p->rchild ;
}
}
}//levelorder

---

南昌县13288095931： 以二叉链表为存储结构,分别写出前序、中序、后序遍历二叉树的递归与非递归算法.(数据结构) - ？
梁废拨云： #include<iostream.h> #include<stdlib.h>typedef char ElemType;struct BTreeNode {ElemType data;BTreeNode*left;BTreeNode*right; };void InitBTree(BTreeNode*& BT) {BT=NULL; } void CreateBTree(BTreeNode*& BT,char*a) {const int ...

南昌县13288095931： 求二叉树的遍历算法 - ？
梁废拨云： 这里有一份以前从网上找到的C语言代码,自己测试过,没有问题,写的很好,分享给你,供参考: #include<stdio.h> #include<stdlib.h> #define STACKINITSIZE 100 #define STACKINCREASESIZE 20 typedef char ElemType; //树结构 typedef ...

南昌县13288095931： .二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现. - ？
梁废拨云： #include using namespace std;//二叉树链式存储的头文件 typedef char datatype;//结点属性值类型 typedef struct node // 二叉树结点类型 { datatype data; struct node* lchild,*rchild; }bintnode; typedef bintnode *bintree; bintree root;//指向二叉树...

南昌县13288095931： 二叉树的中序、前序、后序的递归、非递归遍历算法,应包含建树的实现 - ？
梁废拨云： #include ＂stdlib.h＂#include ＂iostream＂ using namespace std;#define ok 1#define null 0 typedef char telemtype; typedef struct bitnode {telemtype data;<br> struct bitnode *lchild,*rchild;<br> }bitnode,*bitree;/* void visit(bitnode *p) {printf(＂%c＂,...

南昌县13288095931： 设计一个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 // 清空二...

南昌县13288095931： 建立一棵二叉树,要求分别用递归和非递归方法实现二叉树的先序、中序和后序遍历. - ？
梁废拨云： 我们的数据结构实验也是这题,需要我把我的实验报告给你参考下么! 我这里就只发这部分的代码.Status PreOrderTraverse(BiTree T) { //先序遍历二叉树T的递归算法 if (T) { printf(＂%d ＂,T->data); if(T->lchild) PreOrderTraverse(T->lchild); if(T->...

南昌县13288095931： 二叉数的前序、中序、后续三种方式的递归与非递归的算法. - ？
梁废拨云： 小哥分这么少=============tree.cpp=============#include<iostream>#include<queue>#include<stack>#include<fstream> using namespace std;#include＂tree.h＂//构造二叉树 template<class T> bool bitree<T>::insert(const T& e) { btnode<T...

南昌县13288095931： C语言版数据结构 如何理解二叉树的前、中、后序的递归和非递归遍历?? - ？
梁废拨云： 就我看来递归遍历是很容易理解的,除非你不懂C语言递归,难理解的也就是后序非递归遍历.分2步,1、理解前中后遍历流程;2、看算法,回味遍历流程.

南昌县13288095931： 二叉树前序遍历与中序遍历非递归程序思路怎么是一样的? - ？
梁废拨云： 大体思路差不多,但节点访问位置不一样, 先序的话,是先访问,然后节点压栈,移到左子树,至节点空退栈,移到右子树. 而中序的话,是先节点压栈,移到左子树,至节点空退栈,访问节点,然后移到右子树另外,所谓前序、中序、后序遍历,全称是前根序遍历,中根序遍历,后根序遍历,不管哪种遍历,访问左子树 一定在 访问右子树之前,不同的就是根的访问时机.所以三种递归/或非递归,程序思路都是一样的.

南昌县13288095931： 二叉树遍历,递归与非递归,前序中序后序遍历,C代码 - ？
梁废拨云： #include<stdio.h> #include<stdlib.h> typedef struct bitnode { char data; struct bitnode *lchild,*rchild; }bitnode,*bitree;//二叉树节点类型和节点指针类型 bitree create()//先序创建 { bitree root=NULL; char c; scanf(＂%c＂,&c); fflush(stdin); if(c=='#')...