递归遍历文件夹
// 递归遍历文件夹
// file.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
#include
//#include "string.h"
//#include "string.cpp"
using namespace std;
#if 1
//typedef __int64 _int64;
#define _int64 __int64
_int64 getfilelen(char * filename3)
{
ifstream input_file;
input_file.open(filename3,ios::binary);
if(!input_file){
return -1;
}
input_file.seekg(0,ios::end);
int len=input_file.tellg();
input_file.close();
return len;
}
_int64 getfilesize(char * filename2)
{
if(getfilelen(filename2)!=-1)
{
return getfilelen(filename2);
}else if(strcmp(filename2,"..")!=0&&strcmp(filename2,".")!=0) {
::SetCurrentDirectory(filename2);
_int64 fileC2=0;
WIN32_FIND_DA TA fd2;
HANDLE hFind2 = ::FindFirstFile("*.*", &fd2);
if (hFind2!=INV ALID_HANDLE_V ALUE)
{
do{
if (strcmp(fd2.cFileName,".")!=0)
{
char * filename4=fd2.cFileName;
// cout<<"-----"< fileC2 +=getfilesize(filename4); } }while (::FindNextFile(hFind2, &fd2)); } ::FindClose(hFind2); ::SetCurrentDirectory(".."); return fileC2; }else{ return 0; } } int showfile() { _int64 fileC=0; int filenum=0; cout<<"------------------------------------------------------------------"< cout.width(5); cout<<"序号"; cout.width(10); cout<<"类型"; cout.width(40); cout<<"文件名"; cout.width(10); cout<<"文件大小"< WIN32_FIND_DA TA fd; HANDLE hFind = ::FindFirstFile("*.*", &fd); char p[1000][256]; if ( hFind != INV ALID_HANDLE_V ALUE ) { do{ if (strcmp(fd.cFileName,".")!=0) {//获取文件夹信息 filenum++; if(filenum==1000) { cout<<"未显示1000以后的文件"< break; } if(strcmp(fd.cFileName,"..")==0) strcpy(p[filenum],".."); cout.width(5); cout< cout.width(10); cout<<"上级目录"; cout< } else { char * filename=fd.cFileName; // cout<<"****"< fileC +=getfilesize(filename); strcpy(p[filenum],filename); cout.width(5); cout< if(fd.dwFileAttributes&FILE_ATTRIBUTE_DIRECTORY) { cout.width(10); cout<<"文件夹"; } else { cout.width(10); //cout< } cout.width(40); cout< cout.width(10); _int64 num_=getfilesize(filename); if(num_>(1024*1024*1024)) { cout<<(float)num_/(1024*1024*1024)<<" GB"< }else if(num_>(1024*1024)) { cout<<(float)num_/(1024*1024)<<" MB"< }else if(num_>1024) { cout<<(float)num_/1024<<" KB"< }else { cout<<(float)num_<<" B"< } } }while (::FindNextFile(hFind, &fd)); }else{ cout<<"没有文件"< } ::FindClose(hFind); cout< if(fileC>(1024*1024*1024)) { cout<<(float)fileC/(1024*1024*1024)<<" GB"< }else if(fileC>(1024*1024)) { cout<<(float)fileC/(1024*1024)<<" MB"< }else if(fileC>1024) { cout<<(float)fileC/1024<<" KB"< }else { cout<<(float)fileC<<" B"< } cout< cout<<" 请输入你要浏览的文件夹序号(0为退出):"; int file_num; cin>>file_num; if(file_num==0){return 0;} else { ::SetCurrentDirectory(p[file_num]); } return 1; } int main() { //::SetCurrentDirectory("E:/c++zl/"); ::SetCurrentDirectory("E:\\Visual Studio 2005\\Projects\\__int128"); int flag=1; while(flag==1) { flag=showfile(); } return 0; } #endif //int main() //{ // FILE *pfile; // pfile = fopen("LoginTime_15_31.txt", "rb"); // if (!pfile) // { // return 0; // } // char buf[1000]; // fread(buf, 1, 50, pfile); // fclose(pfile); // return 0; //} 二叉树的遍历 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 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，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。 二、算法流程图 数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号： 目录 一、设计思想 (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 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 数据结构（双语） ——项目文档报告 用递归、非递归两种方法遍历二叉树 专业：计算机科学与技术 班级： 指导教师： 姓名： 学号： 目录 一、设计思想 (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， 实验报告 运行结果： 递归算法：非递归算法： 实验总结（结论或问题分析）： 通过实验，加深了对C语言尤其是函数调用部分的认识和掌握。 没有找到在实验运行结果上明确区分递归算法实现的遍历和非递归算法实现的遍历的方法。 实验成绩任课教师签名红霞 附：源程序： 递归算法程序 #include /*扩展先序序列创建二叉链表*/ void cteatebitree(bitree *bt) { char ch; ch=getchar(); if(ch=='.')*bt=NULL; else { *bt=(bitree)malloc(sizeof(bitnode)); (*bt)->data=ch; cteatebitree(&((*bt)->lchild)); cteatebitree(&((*bt)->rchild)); } } /*先序递归遍历*/ void preorder(bitree root) { if(root!=NULL) { printf("%c ",root->data); preorder(root->lchild); preorder(root->rchild); } } /*中序递归遍历*/ void inorder(bitree root) { if(root!=NULL) { 数据结构 1、先序遍历的非递归算法。用c语言写。 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 ///////////////////////////////// #include "stdio.h" #include "stdlib.h" #include "string.h" #define null 0 struct node { char data; struct node *lchild; struct node *rchild; }; //先序，中序建树 struct node *create(char *pre,char *ord,int n) { struct node * head; int ordsit; head=null; if(n<=0) { return null; } else { head=(struct node *)malloc(sizeof(struct node)); head->data=*pre; head->lchild=head->rchild=null; ordsit=0; while(ord[ordsit]!=*pre) { ordsit++; } head->lchild=create(pre+1,ord,ordsit); head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1); return head; } } //中序递归遍历 void inorder(struct node *head) { if(!head) return; else { inorder(head->lchild ); printf("%c",head->data ); inorder(head->rchild ); } } //中序非递归遍历 void inorder1(struct node *head) { . 一、设计思想 1. 用递归算法遍历 设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历 前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。 中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。 后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。 2. 用非递归算法遍历 设计思想：主要是通过栈的存取，判空，从而实现树的遍历 前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。 中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。 后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。 一、设计思想 递归实现二叉树遍历的思想: 1.要遍历二叉树首先的问题是创建二叉树。二叉树的创建可以采用很多的方法。例如：先序，中序，后序，还可以采用层次的方法创建二叉树。本程序采用的是先序递归的方式创建的二叉树。 2.然后是中序，先序，后序递归遍历二叉树。递归的思想是一直调用方法本身。 3.中序递归遍历二叉树的思想是先访问左子树，然后访问根节点，最后访问右子树。当访问左子树或是右子树的时候，实际上调用的是函数本身。在这里就体现了递归的思想，当函数的返回值是0的时候，则返回上一次的程序，继续执行下面的语句。 4.先序递归遍历二叉树的思想是先访问根节点，然后访问左子树，最后访问右子树。同样如步骤3的方式相同，当访问左子树或者是右子树的收，实际上调用的是函数本身，直到返回值是0的时候，返回上一层的程序继续执行。 5.后序递归遍历二叉树的思想是先访问左子树，然后访问右子树，最后访问根节点。 同样跟步骤3的方式相同，当访问左子树或者右子树的时候实际上是调用的是方法本直到有返回值的时候才返回上一层的程序，继续执行. 非递归实现二叉树遍历的思想: 1.跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。 2.然后是中序，先序，后序非递归遍历二叉树。 3.中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。 4.先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。 5.后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。 二、算法流程图 递归方法遍历二叉树的流程图如图1 试验五 课程名称实验室名称 实验名称二叉树中序遍历的非递归算法实现 指导教师成绩 1、实验目的 二叉树中序遍历的非递归算法实现 2、实验原理和内容 二叉树中序遍历的非递归算法实现 3、实验步骤 1.链式存储结构的定义和栈结构的定义 2.编写进栈函数push和出栈函数pop实现中序遍历过程中需存储的数的进栈和出栈过程 3.创建一棵二叉树 4.对该二叉树进行中序遍历，采用非递归算法实现 4、程序及运行结果（或实验数据记录及分析）#include 如何用栈实现递归与非递归的转换 (一)三种遍历树的算法 递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。 一.为什么要学习递归与非递归的转换的实现方法? 1)并不是每一门语言都支持递归的. 2)有助于理解递归的本质. 3)有助于理解栈,树等数据结构. 二.三种遍历树的递归和非递归算法 递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。 1)前序遍历 a)递归方式: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } b)非递归方式 void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法*/ { initstack(S); push(S,T); /* 根指针进栈*/ while(!stackempty(S)) { while(gettop(S,p)&&p) { /* 向左走到尽头*/ visit(p); /* 每向前走一步都访问当前结点*/ push(S,p->lchild); } pop(S,p); if(!stackempty(S)) { /* 向右走一步*/ pop(S,p); push(S,p->rchild); } 运行结果： 递归算法：非递归算法： 实验总结（结论或问题分析）： 通过实验，加深了对C语言尤其是函数调用部分的认识和掌握。 没有找到在实验运行结果上明确区分递归算法实现的遍历和非递归算法实现的遍历的方法。 实验成绩任课教师签名张红霞 附：源程序： 递归算法程序 #include /*扩展先序序列创建二叉链表*/ void cteatebitree(bitree *bt) { char ch; ch=getchar(); if(ch=='.')*bt=NULL; else { *bt=(bitree)malloc(sizeof(bitnode)); (*bt)->data=ch; cteatebitree(&((*bt)->lchild)); cteatebitree(&((*bt)->rchild)); } } /*先序递归遍历*/ void preorder(bitree root) { if(root!=NULL) { printf("%c ",root->data); preorder(root->lchild); preorder(root->rchild); } } /*中序递归遍历*/ void inorder(bitree root) { if(root!=NULL) { 后序遍历非递归算法 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 后序算法之二 void BT_PostOrderNoRec(pTreeT root) { stack 数据结构课程设计报告 题目：二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法。 学生姓名：* * * 学号：*************** 专业班级：计算机科学与技术专业 ***班 同组姓名：***** 指导教师：*****老师 设计时间：年下学期第周 指导老师意见： 目录 一、课题简介 (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); } 本贴给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。 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);树的遍历(递归和非递归)
二叉树遍历C语言(递归,非递归)六种算法
先序遍历的非递归算法 C语言
非递归方式建树并按任一种非递归遍历次序输出二叉树中
用递归非递归两种方法遍历二叉树
后序遍历的非递归算法.doc
用递归和非递归算法实现二叉树的三种遍历
遍历二叉树(递归+非递归)实验报告
先序遍历的非递归算法
递归非递归两种算法遍历二叉树
用递归,非递归两种方法遍历二叉树
二叉树中序遍历的非递归算法实现
如何用栈实现递归与非递归的转换
遍历二叉树(递归+非递归)实验报告
后序遍历的非递归算法
二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法
树的各种非递归算法
- 二叉树先序、中序、后序遍历非递归算法
- 先序遍历的非递归算法 C语言
- 遍历二叉树(递归+非递归)实验报告
- 二叉树后序遍历的非递归算法。
- 用递归、非递归两种方法遍历二叉树.
- 用递归非递归两种方法遍历二叉树
- 用递归,非递归两种方法遍历二叉树
- 非递归后序遍历二叉树
- 二叉树非递归遍历代码
- 二叉树遍历C语言(递归,非递归)六种算法
- 二叉树后序遍历的非递归算法
- 遍历二叉树(递归+非递归)实验报告
- C语言实现二叉树的前序、中序、后续遍历(非递归法)
- 二叉树前序、中序、后序三种遍历的非递归算法
- 递归非递归两种算法遍历二叉树
- 二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法
- 遍历二叉树递归非递归实验报告
- 中序遍历非递归算法演示
- 用递归和非递归算法实现二叉树的三种遍历
- 如何用栈实现递归与非递归的转换