二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法
数据结构课程设计报告
题目：二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法。
学生姓名：* * *
学号：***************
专业班级：计算机科学与技术专业
***班
同组姓名：*****
指导教师：*****老师
设计时间：年下学期第周
指导老师意见：
目录
一、课题简介 (3)
二、系统项目设计. . . . . . . . . . . . . . .3
三、系统实现 (3)
1.二叉树的建立 (4)
2.先序遍历 (4)
a.递归算法 (7)
b.非递归算法 (7)
3.中序遍历 (6)
a.递归算法 (7)
b.非递归算法 (7)
4.后序遍历 (6)
a.递归算法 (7)
b.非递归算法 (7)
5.主菜单程序 (4)
5.子菜单程序 (4)
四、系统测试 (18)
1.二叉树的建立 (4)
2.先序遍历 (4)
a.递归算法 (7)
b.非递归算法 (7)
2.中序遍历 (6)
a.递归算法 (7)
b.非递归算法 (7)
3.后序遍历 (6)
a.递归算法 (7)
b.非递归算法 (7)
4.主菜单程序 (4)
5.子菜单程序 (4)
五、小结 (22)
六、参考文献．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．23 一．课题简介：
通过这个课题设计主要掌握三种遍历方法，包括前序遍历，中序遍历和后序遍历，以及后续遍历的非递归算法。
二．项目设计：
图1：系统功能模块图
图2：系统存盘功能流程图
三系统实现
系统核心代码：
1.二叉树的建立：
二叉树的遍历算法需要先建立二叉树，二叉树的建立需要建立栈和数组栈和数组的建立：
typedef struct node /*结点定义*/
{ char data;
struct node * lchild, * rchild;
} BinTreeNode;
typedef struct{ //栈的定义
BinTreeNode * ptr;
int tag;
}StackNode;
二叉树的建立：
BinTreeNode * CreateBinTree (BinTreeNode * Tree )
/*,按先序序列建立二叉树，输入并建立一棵二叉树Tree*/
{
char c;
scanf("%c",&c);
if(c=='&') Tree = NULL;
else
{
Tree=(BinTreeNode * )malloc(sizeof(BinTreeNode));
Tree->data=c;
Tree->lchild= CreateBinTree(Tree->lchild);
Tree->rchild= CreateBinTree(Tree->rchild);
}
return(Tree);
}
2.先序遍历：
a.递归算法：
先序遍历的递归算法：
/*二叉树的先序遍历*/
void PreOrder ( BinTreeNode *T ) {
if ( T != NULL )
{
printf("%c",T->data);
PreOrder ( T->lchild );
PreOrder ( T->rchild );
}
}
b.非递归算法：
先序遍历的非递归算法：
/*二叉树的先序遍历的非递归算法*/
void PreOrderTwo ( BinTreeNode *T )
{
BinTreeNode *p,*S[Max];
int top=-1;
p=T; /*初始化*/
do
{
while ( p != NULL )
{
printf("%c",p->data);
top++;S[top]=p;
p=p->lchild;
}
if( top >-1 ) /*栈非空*/
{
p=S[top]; top--; /*取栈顶元素，出栈*/
p = p->rchild;
}
}while (( p != NULL ) ||(top>-1));
}
2.中序遍历：
检查该用户是否可以使用该系统，如果没有该用户则重新输入输入，若用户密码输入错误，三次错误时，退出登录系统，并且该用户被冻结。
void common_user()// 普通用户登录
{
char ch;
char pass[20];
char uname[20];
int i=0;
Lab:
if(i==3) exit(1);
puts("\n请输入用户名：");
cin>>uname;
for(user *p= head; p!= NULL;p= p->next)
{
if(!strcmp(uname,p->getmingzi()))
{
if(p->getstate() >=3)
{
cout<<"该账户已经被冻结！\n";
i++;
goto Lab;
}
else break;
}
}
if(!p)
{
cout<<"该用户不存在，请重新输入！\n";
i++;
goto Lab;
}
int x = 0;
cout<<"请输入密码：\n";
while((ch=getch())!= -1 && ch!= '\r')
{
pass[x++]= ch;
putchar('*');
}
pass[x]='\0';
if(!strcmp(p->getmima1(), pass))
while(1)
{
system("cls");
int a;
cout< cout<<" ===============★欢迎使用本银行★=============="< cout<<" ***** 取钱2 *****"< cout<<" ***** 转帐3 *****"< cout<<"请输入您的选择:"< cin>>a; switch(a) { case 1:cunqian(); system("cls");break; case 2:quqian();system("cls");break; case 3:zhuanzhang();system("cls");break ; case 4: { chaxun();//cout<<"请输入帐号："< system("cls"); break; } case 5:guashi();system("cls");return; case 6: xiugai();system("cls");break; case 7: { cunyonghu(); cunzhanghu(); cunguanli(); exit(1); } case 0:return; } } else { cout<<"密码错误！\n"; p->setstate(p->getstate()+1); //如果密码错误，在以前基础上加状态一并存盘cunyonghu(); i++; goto Lab; } } void display() //打印函数 { p= head; while(p!= NULL) { cout<<"用户名："< <<"普通密码："< <<"状态："< p=p->next; } } 1)没有此用户： 2）用户密码错误： 3）密码正确： 3.后序遍历： 检查该用户是否可以使用本系统，三次密码错误则退出登录系统。void manage() // 管理员 { char ch; char pass[20]; char uname[20]; int i=0; Lab: if(i==3) exit(1); puts("\n请输入用户名："); cin>>uname; for(user *p= head; p!= NULL;p= p->next) { if(!strcmp(uname,p->getmingzi())) { if(p->getstate() <0 ) { cout<<"该账户已经被冻结！\n"; i++; goto Lab; } else break; } } if(!p) { cout<<"该用户不存在，请重新输入！\n"; i++; goto Lab; } int x = 0; cout<<"请输入密码：\n"; while((ch=getch())!= -1 && ch!= '\r') { pass[x++]= ch; putchar('*'); } pass[x]='\0'; if(!strcmp("133", pass)) while(1) { system("cls"); int x; cout< cout<<" =============★欢迎使用本银行★==========="< cout<<" ***** 销户 2 *****"< cin>>x; switch(x) { case 1: { system("cls"); kaihu(); system("cls"); break; } case 2: { xiaohu(); //销户 system("cls"); break; } case 3: { chakan(); // 查询 system("cls"); break; } case 4: { xiugai(); //修改密码才 system("cls"); break; } case 5: { Delete(); //修改状态 system("cls"); break; } case 6: { xiugai1(); system("cls"); break; } case 7: { xiugaiyh(); system("cls"); break; } case 8: { cunyonghu(); cunzhanghu(); cunguanli(); exit(1); } case 0: { return; } } } else { cout<<"\n密码错误！\n"; i++; goto Lab; } } 1)密码错误： 2）密码正确： ④开户功能： 使用该功能可以拥有自己的账户，使用银行系统 void kaihu() { char zhanghao[20]; //用户帐号 char id[20]; //身份证号码 char mima[20]; //普通用户密码 int s= 0; //状态初始化为0，等于3时账户冻结cout<<"\t\t增加用户操作中\n"; cout<<"请输入用户的帐号：\n"; cin>>zhanghao; cout<<"请输入用户的身份证号码：\n"; cin>>id; cout<<"请输入普通用户的密码：\n"; cin>>mima; oz= new zhanghu; oz->setzhanghao(zhanghao); oz->setid(id); oz->setmima(mima); oz->setleixing(s); oz->next = headz; headz= oz; cout<<"注册完成！\n"; system("pause"); } ⑤销户功能： 取消没有用了的账户。 void xiaohu () //注销一个帐户 { char ch; char s[20]; int n=0; cout<<"请输入用户名："; 树与二叉树复习 一、填空 1、由二叉树的（中）序和（前、后）序遍历序列可以唯一确定一棵二叉树。 2、任意一棵二叉树，若度为0的结点个数为n0，度为2的结点个数为n2，则n0等于（n0=n2+1 ）。 3、一棵二叉树的第i（i≥1）层最多有（2i-1 ）个结点。 4、一棵有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点个数n1=（n-2n0+1 ）。 5、在一棵高度为5的完全二叉树中，最少含有（ 16 ）个结点。 6、 2．有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时，（ C ）次比较后查找成功。 A． 11 B 5 C 4 D 8 7、在有n个叶结点的哈夫曼树中，总结点数（ 2n-1 ）。 8、若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用（递推）算法，因为（递推算法效率高）。 9、设一棵完全二叉树有700个结点，则共有（ 350 ）叶子结点。 10、设一棵完全二叉树具有1000个结点，该树有（500）个叶子结点，有（499 ）个度为2的结点，有（ 1 ）个结点只有非空左子树。 二、判断 1、( × )在哈夫曼树中，权值最小的结点离根结点最近。 2、( √ ) 完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。 3、( √ )二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 4、( × ) 若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上。 5、( √ )若以二叉链表作为树和二叉树的存储结构，则给定任一棵树都可以找到唯一的一棵二叉树与之对应。 6、( √ )若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小 二叉树的遍历 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为 空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。 二、算法流程图 C语言实现二叉树的前序遍历算法实现一： #include #include 数学与计算机学院计算机系实验报告 课程名称： 数据结构 年级：2010 实验成绩： 指导教师： 黄襄念 姓名： 实验教室：6A-413 实验名称：二叉树前序或中序或后序遍历 学号： 实验日期：2012/6/10 实验序号：实验3 实验时间：8:00—11:40 实验学时：4 一、实验目的 1. 熟悉的掌握树的创建，和树的前序、中序、后序遍历。 二、实验环境 1. 操作系统：Windows7 2. 开发软件：Microsoft Visual C++ 6.0 三、实验内容 ● 程序功能 本程序完成了以下功能： 1. 前序遍历 2. 中序遍历 3. 后序遍历 ● 数据结构 本程序中使用的数据结构（若有多个，逐个说明）： 1. 它的优缺点 1） 可以快速的查找数据。 2） 让数据层次更加清晰。 2. 逻辑结构图 3. 存储结构图 、、、、、、、、、、、、、、、、、、、、 4.存储结构的C/C++ 语言描述 typedef struct node { DataType data; struct node *lchild; struct node *rchild; } BiTNode, *BiTree; typedef BiTree type; ●算法描述 本程序中采用的算法 1.算法名称：递归 2.算法原理或思想 是通过访问结点的左右孩子来进行循环查找的方法，拿中序遍历来说明：先从头结点开始，再去访问头结点的右孩子如果为空就访问头结点的左孩子，依次进行访问当结点的左右孩子都为空时，就访问上一级，到了最后。 3.算法特点 它能将查找进行2分，体现出了更高效快捷的特点，并且层次很清晰。 ●程序说明 1. 2. 1）前序遍历模块：将树进行从头结点开始再左孩子再右孩子。 代码：void InOrder(BiTree root) { Stack S(100); initStack(S); BiTNode *p = root; do { while(p != NULL) { Push(S, p); #include <> #include <> #include <> #define MAX_TREE_SIZE 100 typedef struct { int data; int parent; ata,[i].parent); printf("\n"); } } /*用双亲表示法创建树*/ PTree CreatTree(PTree T) { int i=1; int fa,ch; PTNode p; for(i=1;ch!=-1;i++) { printf("输入第%d结点:\n",i); scanf("%d,%d",&fa,&ch); printf("\n"); =ch; =fa; ++; [].data = ; [].parent = ; } printf("\n"); printf("创建的树具体情况如下:\n"); print_ptree(T); return T; } /*一般树转换成二叉树*/ BTNode *change(PTree T) { int i,j=0; BTNode p[MAX_TREE_SIZE]; BTNode *ip,*is,*ir,*Tree; ip=(BTNode *)malloc(sizeof(BTNode)); is=(BTNode *)malloc(sizeof(BTNode)); ir=(BTNode *)malloc(sizeof(BTNode)); Tree=(BTNode *)malloc(sizeof(BTNode)); for(i=0;i<;i++) { p[i]=GetTreeNode[i].data); } for(i=1;i<;i++) { ip=&p[i]; is=&p[j]; while[i].parent!=is->data) { j++; is=&p[j]; } if(!(is->firstchild)) { is->firstchild=ip; ir=ip; } else { ir->rightsib=ip; ir=ip; } } Tree=&p[0]; return Tree; } /*主菜单*/ void Menu() { printf("=================主菜单=======================\n"); printf("***输入-以双亲法创建一棵一般树***\n"); printf("***输入2-------------树的前序遍历(递归)*******\n"); printf("***输入3-------------树的后序遍历(递归)*******\n"); printf("***输入4-------------树的前序遍历(非递归)*****\n"); printf("***输入5-------------树的后序遍历(非递归)*****\n"); printf("***输入6-------------层次序的非递归遍历*******\n"); printf("***输入0-------------退出程序*****************\n"); printf("==============================================\n"); 实践三：树的应用 1.实验目的要求 通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。认识哈夫曼树、哈夫曼编码的作用和意义。 实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树，正确调试本程序。 能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。写出实验报告。 2.实验主要内容 2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。 2.2 根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码。 3．实验步骤 2.1实验步骤 ●输入p127二叉链表的定义 ●录入调试p131算法6.4，实现二叉树的构造函数 ●编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的 形式，以方便观察树的结构。 ●参考算法6.1，实现二叉树的前序、中序和后序的递归遍历算法。 为简化编程，可以将visit函数直接使用printf函数输出结点内容来 代替。 #include typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; // 构造栈的结构体 typedef BiTree SElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(SqStack &S){ //构造一个空栈 S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base)exit(-2); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S){ //若栈S为空栈，则返回TRUE,否则返回FALSE if(S.top==S.base) return 1; else return 0; } #include 数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号： 目录 一、设计思想 (01) 二、算法流程图 (02) 三、源代码 (04) 四、运行结果 (11) 五、遇到的问题及解决 (11) 六、心得体会 (12) 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status 为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。 #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //*************************************************** 先序遍历的非递归算法 #include printf("二叉树广义表字符串有错!\n"); exit(1); } top--;break; case ',' : k=2;break; default : if((a[i]>='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z')) { p=malloc(sizeof(struct BTreeNode)); p->data=a[i];p->left=p->right=NULL; if(* BT==NULL) * BT=p; else { if(k==1) s[top]->left=p; else s[top]->right=p; } } else {printf("二叉树广义表字符串有错!\n");exit(1);} } i++; } } void Preorder(struct BTreeNode * BT) { struct BTreeNode * s[10]; int top=-1; struct BTreeNode * p=BT; printf("先序遍历结点的访问序列为:\n"); while(top!=-1||p!=NULL) { while(p!=NULL) { top++; s[top]=p; printf("%c",p->data); p=p->left; } if(top!=-1) { #include 二叉树前序、中序、后序遍历相互求法今天来总结下二叉树前序、中序、后序遍历相互求法，即如果知道两个的遍历，如何求第三种遍历方法，比较笨的方法是画出来二叉树，然后根据各种遍历不同的特性来求，也可以编程求出，下面我们分别说明。 首先，我们看看前序、中序、后序遍历的特性： 前序遍历： 1.访问根节点 2.前序遍历左子树 3.前序遍历右子树 中序遍历： 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树 后序遍历： 1.后序遍历左子树 2.后序遍历右子树 3.访问根节点 一、已知前序、中序遍历，求后序遍历 例： 前序遍历: GDAFEMHZ 中序遍历: ADEFGHMZ 画树求法： 第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。 第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。 第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下： 1 确定根,确定左子树，确定右子树。 2 在左子树中递归。 //非递归方式建树，并按任一种非递归遍历次序输出二叉树中的所有结点； #include 数据结构（双语） ——项目文档报告 用递归、非递归两种方法遍历二叉树 专业：计算机科学与技术 班级： 指导教师： 姓名： 学号： 目录 一、设计思想 (03) 二、算法流程图 (04) 三、源代码 (06) 四、运行结果 (12) 五、遇到的问题及解决 (14) 六、心得体会 (15) 一、设计思想 1．递归： （1）主函数main（）主程序要包括：定义的二叉树T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。 （2）建树函数定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用,依次循环下去，直到ch遇到空时，结束。最后要返回建立的二叉树T。 （3）先序遍历函数根据先序遍历规则，当T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进行下去。 (4) 中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。 (5）后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。 2.非递归： （1）跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。 （2）然后是中序，先序，后序非递归遍历二叉树。 （3）中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。 (4)先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。 (5）后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。 第六章树二叉树 后序遍历的非递归算法。在对二叉树进行后序遍历的过程中，当指针p 指向某一个结点时，不能马上对它进行访问，而要先遍历它的左子树，因而要将此结点的地址进栈保存。当其左子树遍历完毕之后，再次搜索到该结点时(该结点的地址通过退栈得到) ，还不能对它进行访问，还需要遍历它的右子树，所以，再一次将此结点的地址进栈保存。为了区别同一结点的两次进栈，引入一个标志变量nae,有0 表示该结点暂不访问 1 表示该结点可以访问标志flag 的值随同进栈结点的地址一起进栈和出栈。因此，算法中设置两个空间足够的堆栈,其中, STACKlCM] 存放进栈结点的地址, STACK2[M] 存放相应的标志n 昭的值, 两个堆栈使用同一栈顶指针top , top 的初值为— 1 。 具体算法如下： #defineH 100 /?定义二叉树中结点最大数目。/ voidPOSTOiRDER(BTREET) { / *T 为二叉树根结点所在链结点的地址。/ BTREESTACKl[H] , p=T ；intSTACK2[M] , flag,top= —1；if(T!=NULL) d0{ while(p!=NULL){ STACK/[++top]=p ; /?当前p所指结点的地址进栈?/ STACK2[top]= 0 ; /,标志0 进栈?/ p=p->lchild ；/?将p 移到其左孩子结点x/ } p=STACKl[top) ；flag=STACK2[top--] ；if(flag==0){ STACKl[++top]=p ; /,当前p所指结点的地址进栈。/ STACK2[toP]=1 ; /?标志1 进栈?/ p=p->rchild ; /x将p移到其右孩子结点o/ } else{ VISIT(p) ; /x访问当前p所指的结点x/ p=NULL ； } }while(p!=NULLtttop!=-1) ； } 不难分析,上述算法的时间复杂度同样为O(n) 7．6．3 二叉树的线索化算法 对--X 树的线索化,就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程, 因此, 二叉树的线索化过程只能 在对二叉树的遍历过程中进行。 下面给出二叉树的中序线索化的递归算法。算法中设有指针pre,用来指向中序遍历过 程中当前访问的结点的直接前驱结点，pre的初值为头结点的指针；T初始时指向头结点， 但在算法执行过程中，T总是指向当前访问的结点。voldlNTHREAD(TBTREET) { TBTREE pre ； if(T!=Null){ INTHREAD(T —>lchild)； if(T —>rchild==NULL) ○A ○C ○D ○B ○E○F G 《数据结构与算法》实验报告三 ——二叉树的操作与应用 一.实验目的 熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用 二. 实验要求（题目） 说明：以下题目中（一）为全体必做，（二）（三）任选其一完成 （一）从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构；（二）分别用递归和非递归算法实现二叉树的三种遍历； （三）模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合) 三. 分工说明 一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。 四. 概要设计 实现算法，需要链表的抽象数据类型： ADT Binarytree { 数据对象：D是具有相同特性的数据元素的集合 数据关系R： 若D为空集，则R为空集，称binarytree为空二叉树； 若D不为空集，则R为{H}，H是如下二元关系； （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root}不为空，则存在D－{root}＝{D1，Dr}，且D1∩Dr为空集； （3）若D1不为空，则D1中存在唯一的元素x1， 【题目】 假设一棵二叉树的后序遍历序列为DGJHEBIFCA ，中序遍历序列为DBGEHJACIF ，则其前序 遍历序列为( ) 。 A. ABCDEFGHIJ B. ABDEGHJCFI C. ABDEGHJFIC D. ABDEGJHCFI 由题，后序遍历的最后一个值为A，说明本二叉树以节点A为根节点（当然，答案中第一个节点都是A，也证明了这一点） 下面给出整个分析过程 【第一步】 由后序遍历的最后一个节点可知本树根节点为【A】 加上中序遍历的结果，得知以【A】为根节点时，中序遍历结果被【A】分为两部分【DBGEHJ】【A】【CIF】 于是作出第一幅图如下 【第二步】 将已经确定了的节点从后序遍历结果中分割出去 即【DGJHEBIFC】---【A】 此时，位于后序遍历结果中的最后一个值为【C】 说明节点【C】是某棵子树的根节点 又由于【第一步】中【C】处于右子树，因此得到，【C】是右子树的根节点 于是回到中序遍历结果【DBGEHJ】【A】【CIF】中来，在【CIF】中，由于【C】是根节点，所以【IF】都是这棵子树的右子树，【CIF】子树没有左子树，于是得到下图 【第三步】 将已经确定了的节点从后序遍历中分割出去 即【DGJHEBIF】---【CA】 此时，位于后序遍历结果中的最后一个值为【F】 说明节点【F】是某棵子树的根节点 又由于【第二步】中【F】处于右子树，因此得到，【F】是该右子树的根节点 于是回到中序遍历结果【DBGEHJ】【A】【C】【IF】中来，在【IF】中，由于【F】是根节点，所以【I】是【IF】这棵子树的左子树，于是得到下图 【第四步】 将已经确定了的节点从后序遍历中分割出去 即【DGJHEB】---【IFCA】 此时，位于后序遍历结果中的最后一个值为【B】 说明节点【B】是某棵子树的根节点 又由于【第一步】中【B】处于【A】的左子树，因此得到，【B】是该左子树的根节点 于是回到中序遍历结果【DBGEHJ】【A】【C】【F】【I】中来，根据【B】为根节点，可以将中序遍历再次划分为【D】【B】【GEHJ】【A】【C】【F】【I】，于是得到下图已知某二叉树的先序遍历和中序遍历的结果是先序遍历ABDEGCF
树的遍历(递归和非递归)
C语言实现二叉树的前序遍历(递归)
二叉树前序或中序或后序遍历
树转换成二叉树-树的前序、后序的递归、非递归和层次序的非递归
二叉树的遍历(先序、中序、后序)
C++二叉树的前序,中序,后序,层序遍历的递归算法55555
二叉树遍历C语言(递归,非递归)六种算法
二叉树的建立及几种简单的遍历方法
先序遍历的非递归算法 C语言
遍历二叉树老师的程序(绝对正确,实现先序、中序、后序遍历)
二叉树前序、中序、后序遍历相互求法
非递归方式建树并按任一种非递归遍历次序输出二叉树中
用递归非递归两种方法遍历二叉树
后序遍历的非递归算法.doc
用递归和非递归算法实现二叉树的三种遍历
根据二叉树的后序遍历和中序遍历还原二叉树解题方法
- 用递归非递归两种方法遍历二叉树
- 遍历二叉树(递归+非递归)实验报告
- 二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法
- C语言实现二叉树的前序、中序、后续遍历(非递归法)
- 非递归后序遍历二叉树共41页文档
- 遍历二叉树(递归+非递归)实验资料报告材料
- 二叉树中序遍历的非递归算法实现
- 二叉树遍历C语言递归非递归六种算法
- 二叉树非递归遍历代码
- 二叉树前序、中序、后序三种遍历的非递归算法
- 数据结构试验报告用先序中序建立二叉树后序遍历非递归
- 二叉树的非递归遍历
- 二叉树非递归遍历代码(前、中序)
- 用递归和非递归算法实现二叉树的三种遍历
- 用递归,非递归两种方法遍历二叉树
- 有序二叉树,遍历(递归,非递归)
- 二叉树非递归遍历
- 二叉树的建立及几种简单的遍历方法
- 二叉树后序遍历的非递归算法
- 二叉树后序遍历的非递归算法。