Python中如何遍历一个目录 输出所有的文件名

Python中如何遍历一个目录输出所有的文件名

如今想要学习Python的小伙伴越来越多，不论是参加Python培训还是自学Python开发的小伙伴都有。本篇文章给喜欢Python开发的小伙伴分享一下Python中如何遍历一个目录输出所有的文件名，希望能帮到对Python开发感兴趣的小伙伴们。

python 获取一个文件夹内(包括子文件夹)所有文件的名字和路径

import os

dir = "e:\\"

for root, dirs, files in os.walk(dir):

for file in files:

print os.path.join(root,file)

或：

import os

path = r'e:\case'

fns = [os.path.join(root,fn) for root, dirs, files in os.walk(path) for fn in files]

for f in fns:

print(f)

print(len(fns))

#coding=utf-8

import os

def GetFileList(dir, fileList):

newDir = dir

if os.path.isfile(dir):

fileList.append(dir.decode('gbk'))

elif os.path.isdir(dir):

for s in os.listdir(dir):

#如果需要忽略某些文件夹，使用以下代码

#if s == "xxx":

#continue

newDir=os.path.join(dir,s)

GetFileList(newDir, fileList)

return fileList

list = GetFileList('D:\\workspace\\PyDemo\\fas', [])

for e in list:

print e

好了，关于Python中如何遍历一个目录及输出所有的文件名就先给大家分享这些，想要学习Python的小伙伴快到扣丁学堂Python在线学习报名学习吧。扣丁学堂不仅有专业的老师和与时俱进的课程体系，还有大量的Python在线视频供学员观看学习，想要学好Python 高薪就业的小伙伴快快行动吧。

树与图的简单遍历算法

树与图的简单遍历算法 发表时间：2019-01-14T09:56:22.797Z 来源：《科技新时代》2018年11期作者：闵俊齐 [导读] 树与图是两种重要的数据结构，而树可以说是一种特殊的图，它的两两结点之间存在唯一简单路径。 重庆第二外国语学校重庆 400065 摘要：树与图是两种重要的数据结构，而树可以说是一种特殊的图，它的两两结点之间存在唯一简单路径。利用其特殊性质，人们创造了许多算法来处理数据结构问题和程序调用问题。而树与图的遍历算法也是数据结构中重要的算法之一。本文从树与图的概念出发，简单的介绍了树与图的主要存储方式，并重点对二叉树的简单遍历算法、哈夫曼树的生成和图的深度优先遍历及广度优先遍历做出了介绍。 关键词：数据结构；二叉树；图；遍历算法 1.树与图的概念 树是一种数据结构，是由n（n≥0）个结点构成的具有明显层次关系的有限集合。一棵树一般由一个根节点和若干个子结点构成。结点与结点之间具有明显的并列或层次关系，这种层次关系称为父子关系。在一棵树中，没有父结点的结点被称为根结点。树有几个重要的概念，以下做出简单的介绍——树的度：某个结点拥有的子树的数量称为这个结点的度，度为零的结点也叫做叶结点，而度不为零的结点叫做分支结点。树的深度：一棵树的根结点的层次为1，其他结点的层次是其父结点的层次加1。一棵树里最大的层次的值被称为这棵树的深度。树有无序树，有序树，二叉树等。其中二叉树是每个结点最多有两个子结点的树，每个结点的子树通常被称为“左子树”和“右子树”，故二叉树中每个结点的度的最大值为2，而又有左右之分，二叉树中结点的次序不能任意颠倒。除最后一层的叶结点没有子结点外，其余每一层的每个结点都具有两个子结点的二叉树称为满二叉树。如果存在一个深度为h的二叉树，它的除h层外其余各层（1~h-1）的结点数都达到了最大值，并且它的第h层的结点全部集中在树的左边，这种二叉树就被称为完全二叉树。完全二叉树是由满二叉树引申出来的，它是一种效率很高的数据结构。本文后部分将会介绍二叉树的简单遍历算法。 图由若干个顶点组成的有限非空集合和各个顶点的边构成，通常表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。图数据结构主要研究形状和图形数据元素之间的关系。它必须反映数据所对应的元素之间的几何关系和拓扑关系。图依照边的方向可分为有向图和无向图。有向图由顶点和弧构成。弧有弧尾和弧头，带箭头的一边称为弧头。图结构与树结构相比较，图中的任意两个元素都有可能相关。而对某个结点而言，树下层可能有多个元素，上层只有能一个元素，复杂度比树大[1]。 2二叉树与图的储存方式 2.1二叉树的储存方式 二叉树有两种储存方式：顺序存储和链式存储。 顺序储存就是按照完全二叉树的结点层次顺序存储的一种只适用于完全二叉树的储存方式，且在最坏的情况下，k个结点的单支数却只需要长度的 -1的一维数据。这种储存需要一个完全连续地址，所以会占用许多的储存空间。 在二叉树中，每个结点信息一般都由一下几个部分构成：该结点的数据元素（Data）、指向左子树的指针（L child）和指向右子树的指针（R child）。利用指针，我们可以很好的存储二叉树。若使用二叉链表，每个结点的结构如图1（a）所示。一般可以（L,D,R）来表示。在三叉链表中，可表示每个结点的父结点，结构如图1（b）所示。一般可以（L,D,P,R）来表示[5]。链式储存不需要完全连续地址，节约储存空间[2]。 图2 3.二叉树的遍历算法及哈夫曼树的生成 3.1二叉树的遍历算法 遍历，是指用某种方法沿着某条路对每一个元素做一且仅一次访问，它是二叉树的重要运算之一。二叉树的主要有三种访问方式：先序遍历、中序遍历、后序遍历。具体实现过程如下：

树的遍历(递归和非递归)

二叉树的遍历 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 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语言(递归,非递归)六种算法

数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号：

目录 一、设计思想 (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，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。

数据结构 树的三种遍历

学号：E30814013 姓名：张芸； 专业：网络工程 题目::实现二叉树的前序,中序,后序遍历 #include #include #include typedef struct Btnode{ char data; struct Btnode *lchild; struct Btnode *rchild; }Btnode; void main() { void xianxu(Btnode *BT); void zhongxu(Btnode *BT); void houxu(Btnode *BT); Btnode *CreatBiTree(Btnode *BT); Btnode *BT; Btnode *B; BT=(Btnode*)malloc(sizeof(Btnode)); printf("先序输入二叉树中节点的值（一个字符,先序输入），空格表示空树\n"); B=BT=CreatBiTree(BT); printf("输出二叉树（二叉树的遍历）\n"); printf("先序\n"); xianxu(BT); printf("\n"); printf("中序\n"); zhongxu(BT); printf("\n"); printf("后序\n"); houxu(BT); printf("\n"); } Btnode *CreatBiTree(Btnode *BT) {char ch; scanf("%c",&ch); if(ch==' ')BT=NULL; else{

BT=(Btnode*)malloc(sizeof(Btnode)); BT->data=ch; BT->lchild=CreatBiTree(BT->lchild); BT->rchild=CreatBiTree(BT->rchild); } return BT; } void xianxu(Btnode *BT) { if(BT){ printf("%c",BT->data); xianxu(BT->lchild); xianxu(BT->rchild); } } void zhongxu(Btnode *BT) { if(BT){ zhongxu(BT->lchild); printf("%c",BT->data); zhongxu(BT->rchild); } } void houxu(Btnode *BT) { if(BT){ houxu(BT->lchild); houxu(BT->rchild); printf("%c",BT->data); }

c语言构造树及树的三种遍历

#include<> #include<> #include <> #define error 0 #define ok 1 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; int CreateBiTree(BiTree &T) { char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(error); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return ok; } void PreOrderBiTree(BiTree T) { if(T) { printf("%c",T->data); PreOrderBiTree(T->lchild); PreOrderBiTree(T->rchild); } } void InOrderBiTree(BiTree T) { if(T) { InOrderBiTree(T->lchild); //中序遍历左子树 printf("%c",T->data); //访问结点 InOrderBiTree(T->rchild); //中序遍历右子树} } void PostOrderBiTree(BiTree T)

{ if(T) { PostOrderBiTree(T->lchild); PostOrderBiTree(T->rchild); printf("%c",T->data); } } main() { int i; BiTree T; printf("\t请输入树的各元素：\n\t"); CreateBiTree(T); do { printf(" /*****************************/\n"); printf("\t1键：先序输出; \n\t2键：中序输出；\n\t3键：后序输出！\n\t0键：退出程序！\n"); printf("\t请输入你的选择：\n\t"); scanf("%d",&i); switch(i) { case 1:printf("\n\t你选择的是先序输出！！ \n"); printf("\n\t输出结果为：\n"); printf("\t"); PreOrderBiTree(T);break; case 2:printf("\n\t你选择的是中序输出！！ \n"); printf("\n\t输出结果为：\n"); printf("\t"); InOrderBiTree(T);break; case 3:printf("\n\t你选择的是后序输出！！ \n"); printf("\n\t输出结果为：\n"); printf("\t"); PostOrderBiTree(T);break; } printf("\n"); }while(i!=0); }

二叉树的建立及几种简单的遍历方法

#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 #include typedef struct bnode { int data; struct bnode *lchild, *rchild; } Bnode, *BTree; void Visite(BTree t) { printf("%d ",t->data); } BTree Init_Node() { BTree btree; btree=(BTree)malloc(sizeof(Bnode));//分配空间 if(btree) { btree->lchild=NULL; btree->rchild=NULL; } return btree; } //递归创建树 void createTree(BTree t,int nodes[],int i) { BTree left,right; if(2*i<=nodes[0])// 生成左孩子结点 { left=Init_Node(); left->data=nodes[2*i]; t->lchild=left; createTree(left,nodes,2*i);//以此结点为根结点，递归继续生成孩子结点} if(2*i+1<=nodes[0])//生成右孩子结点 { right=Init_Node(); right->data=nodes[2*i+1]; t->rchild=right; createTree(right,nodes,2*i+1);//以此结点为根结点，递归继续生成孩子结点}

} //先序遍历 void PreOrder(BTree t) { if(t) { printf("%d",t->data); PreOrder(t->lchild); PreOrder(t->rchild); } } //中序遍历 void InOrder(BTree t) { if(t) { InOrder(t->lchild); printf("%d",t->data); InOrder(t->rchild); } } //后序遍历 void PostOrder(BTree t) { if(t) { PostOrder(t->lchild); PostOrder(t->rchild); printf("%d",t->data); } } //递归销毁树 void Destroy_Tree(BTree *Node) { if(*Node) { Destroy_Tree(&((*Node)->lchild)); Destroy_Tree(&((*Node)->rchild)); free(*Node);

彻底解决二叉树的遍历问题

彻底解决二叉树遍历的画法 对于二叉树的基本概念，一般学生都知道，但对于二叉树的遍历，在实际运用中可以发现很多问题，这里提供一次性彻底解决这个问题的方法。 二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。 由于二叉树是一种非线性结构，因此，对二叉树的遍历要比遍历线性表复杂得多。在遍历二叉树的过程中，当访问到某个结点时，再往下访问可能有两个分支，那么先访问哪一个分支呢? 对于二叉树来说，需要访问根结点、左子树上的所有结点、右子树上的所有结点，在这三者中，究竟先访问哪一个?也就是说，遍历二叉树的方法实际上是要确定访问各结点的顺序，以便不重不漏地访问到二叉树中的所有结点。 在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。这三种说法实际是指对根结点的访问顺序决定的，下面分别介绍这三种遍历的方法。 1．前序遍历(DLR) 所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。

下面是二叉树前序遍历的简单描述： 若二叉树为空，则结束返回。 否则：(1)访问根结点； (2)前序遍历左子树； (3)前序遍历右子树。 在此特别要注意的是，在遍历左右子树时仍然采用前序遍历的方法。如图所示： 二叉树进行前序遍历，则遍历的结果为F，C，A，D，B，E，G，H，P(称为该二叉树的前序序列)。 2．中序遍历(LDR) 所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。 下面是二叉树中序遍历的简单描述： 若二叉树为空，则结束返回。 否则：(1)中序遍历左子树；

树的遍历

#include #include #include //二叉树节点信息 struct binarytreenode { int data; struct binarytreenode *lchild;//左子树 struct binarytreenode *rchild;//右子树}; typedef struct binarytreenode BiTNode; void print( int e) { printf(" %2d", e); } //二叉树创建 BiTNode *CreatTree( int *a) {

int i; BiTNode *pNode[11] = {0}; for ( i = 0; i < 10; i++) { pNode[i] = (BiTNode *) malloc(sizeof(BiTNode)); if ( NULL == pNode[i]) { printf("malloc error!\n"); exit(1); } pNode[i]->lchild = NULL; pNode[i]->rchild = NULL; pNode[i]->data = a[i]; } for ( i = 0; i < 10/2; i++) {

pNode[i]->lchild = pNode[ 2 * (i + 1) - 1]; pNode[i]->rchild = pNode[ 2 * (i + 1) + 1 - 1]; } return pNode[0]; } //先序遍历 int PreOrderTraverse( BiTNode *root, void (*visit)(int) ) { if ( NULL == root) { return 1; } (*visit)(root->data); if ( PreOrderTraverse(root->lchild, visit) ) { if ( PreOrderTraverse(root->rchild, visit) ) {

创建一个二叉树并输出三种遍历结果

实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别___ _计算机学院 _ ______ 专业___ ___ 班级/学号___________ 学生姓名 _________ 实验日期_ 成绩_______________________ 指导教师

实验题目：实验三------创建一个二叉树并输出三种遍历结果 一、实验目的 1)掌握二叉树存储结构； 2)掌握并实现二叉树遍历的递归算法和非递归算法； 3)理解树及森林对二叉树的转换； 4)理解二叉树的应用—哈夫曼编码及WPL计算。 二、实验内容 1)以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2)输出先序、中序、后序遍历序列； 3)二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。（应用型 题目可替换上述前两项实验内容） 三、设计与编码 1)程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、框图等来表示） 2)本实验用到的理论知识 遍历二叉树，递归和非递归的方法

（提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法） 3)具体算法设计 （1）首先，定义二叉树的存储结构为二叉链表存储，每个元素的数据类型Elemtype，定义一棵二叉树，只需定义其根指针。 （2）然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输入字符时要注意，当节点的左孩子或者右孩子为空的时候，应 当输入一个特殊的字符（本算法为“#”），表示左孩子或者右孩子为 空。 （3）下一步，创建利用递归方法先序遍历二叉树的函数，函数为PreOrderTree()，创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后， 从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依 次类推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二 叉树的函数，函数为LaOrderTree()。 （提示：该部分主要是利用C、C++等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述） 4)编码 #include #include #include typedef char DataType; #define MaxSize 100 typedef struct Node { DataType data; struct Node *lchild; struct Node *rchild; } *BiTree,BitNode; void InitBitTree(BiTree *T); /*树的初始化*/ void CreateBitTree(BiTree *T); /*按照先序输入字符序列递归创建二叉树*/ void PreOrderTraverse(BiTree T); /*二叉树的先序遍历的递归函数声明*/ void InOrderTraverse(BiTree T); /*二叉树的中序遍历的递归函数声明*/ void PostOrderTraverse(BiTree T); /*二叉树的后序遍历的递归函数声明*/ void PreOrderTraverse2(BiTree T); /*二叉树的先序遍历的非递归函数声明*/ void InOrderTraverse2(BiTree T); /*二叉树的中序遍历的非递归函数声明*/ void PostOrderTraverse2(BiTree T); /*二叉树的后序遍历的非递归函数声明*/

树的遍历

实验题目与要求： 实验6: 树的遍历 题目：采用递归方式建立二叉树，并分别采用先序，中序，后序遍历算法遍历之。 要求：建立树时采用先序建立的方法，能对给定的树，写出其先序创建的顺序（含结束符），并输入创建树。 源程序及结果： #include #include #include typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;//定义结点类型 BiTree CreateBiTree()//创建树 { char p; BiTree T; scanf("%c",&p); if(p==' ') T=NULL; else { T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间 T->data=p; T->lchild=CreateBiTree(); T->rchild=CreateBiTree(); } return (T); } void PreOrder(BiTree T)//pre { if(T!=NULL) { printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } }

void InOrder(BiTree T)//in { if(T!=NULL) { InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); } } void PostOrder(BiTree T)//post { if(T!=NULL) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); } } void main() { BiTree Tree; printf("请输入以空格为空结点的树：\n"); Tree=CreateBiTree(); printf("先序遍历树:"); printf("\n"); PreOrder(Tree); printf("\n"); printf("中序遍历树:"); printf("\n"); InOrder(Tree); printf("\n"); printf("后序遍历树:"); printf("\n"); PostOrder(Tree); printf("\n"); }

程序二叉树的四种遍历方法和两种求深度的方法

二叉树的四种遍历方法和两种求深度的方法 用到了以前学的栈和队列的知识，也算是一种复习。不过用到栈来求深度的时候，改变了二叉树，不知道如何去避免？ // 二叉树.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include "stdio.h" #include "stdlib.h" typedef struct BiTNode{ //二叉树结构 int data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; #define STACK_INIT_SIZE 100 #define STACKINGMENT 10 int CreateBiTree( BiTNode **T ) //用先序顺序建立二叉树 { char c; if( (c = getchar()) == '#') *T = NULL; else { if(!(*T = (BiTree)malloc(sizeof(BiTNode)))) { printf("ERROR!"); return 0; } (*T)->data = c; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } return 0; } int PrintfElement( int e ) { printf("%c",e); return 1;

} int PreOrderTraverse(BiTree T,int (* PrintfElement)(int e)) //先序遍历二叉树的递归方法 { if(T) //访问根结点 { if(PrintfElement(T->data)) if(PreOrderTraverse(T->lchild,PrintfElement)) //先序遍历左子树 if(PreOrderTraverse(T->rchild,PrintfElement)) //先序遍历右子树 return 1; return 0; } else return 1; } int InOrderTraverse(BiTree T,int (*PrintfElement)(int)) //中序遍历二叉树的递归方法 { if(T) { if(InOrderTraverse(T->lchild, PrintfElement)) if(PrintfElement(T->data)) if(InOrderTraverse(T->rchild, PrintfElement)) return 1; return 0; } else return 1; } int PostOrderTraverse(BiTree T, int (*PrintfElement)(int) ) //后序遍历二叉树的递归方法 { if(T) { if(PostOrderTraverse(T->lchild, PrintfElement)) if(PostOrderTraverse(T->rchild, PrintfElement)) if(PrintfElement(T->data)) return 1; return 0; } else

二叉树的三种遍历算法

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;

二叉树的遍历有三种方式

二叉树的遍历有三种方式，如下： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。 （2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。 （3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。 例1：如上图所示的二叉树，若按前序遍历，则其输出序列为。若按中序遍历，则其输出序列为。若按后序遍历，则其输出序列为。 前序：根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH 中序：先访问根的左子树,B没有左子树，其有右子树D，D无左子树，下面访问树的根A，连起来是BDA。 再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无右子树，结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC 后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA 例2:有下列二叉树，对此二叉树前序遍历的结果为（）。 A）ACBEDGFH B）ABDGCEHF C）HGFEDCBA D）ABCDEFGH 解析：先根A，左子树先根B，B无左子树，其右子树，先根D，在左子树G，连起来是ABDG。A的右子树，先根C，C左子树E，E无左子树，有右子树为H，C的右子树只有F，连起来是CEHF。整个连起来是B答案ABDGCEHF。 例3：已知二叉树后序遍历是DABEC，中序遍历序列是DEBAC，它的前序遍历序列是( ) 。 A）CEDBA B）ACBED C）DECAB D）DEABC 解析：由后序遍历可知，C为根结点，由中序遍历可知，C左边的是左子树含DEBA，C右边无结点，知

图解数据结构6-树及树的遍历

八、树（Tree） 树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。不说那么多了，图一看就懂： 当然了，引入了树之后，就不得不引入树的一些概念，这些概念我照样尽量用图，谁会记那么多文字？ 树这种结构还可以表示成下面这种方式，可见树用来描述包含关系是很不错的，但这种包含关系不得出现交叉重叠区域，否则就不能用树描述了，看图：

面试的时候我们经常被考到的是一种叫“二叉树”的结构，二叉树当然也是树的一种了，它的特点是除了叶以外的节点都有两个子，图： 由此我们还可以推出“三叉树”： 当然还有“四叉树”，“五叉树”，“六叉树”……但太难画了，节点太多，略过。 九、树的遍历（Traversal）

值得再提一下的是二叉树，因为它确实比较特别，节点有两个子，这两个子是有左右之分的，颠倒一下左右，就是不一样的二叉树了，所以左右是不能随便颠倒的。 在第三篇讲到“队”的时候，提及到了广度优先遍历（Breadth-first traversal），除了广度优先遍历之外，还有深度优先遍历（Depth-first Traversal），深度优先遍历又可分为：前序遍历（Preorder Traversal），后序遍历（Postorder Traversal）和中序遍历（Inorder Traversal），其中中序遍历只有对二叉树才有意义，下图解释这几种遍历： 好了，又到代码阶段，写点代码。我看过许多数据结构的教材，二叉树遍历都是必不可少的内容，而且我知道的全部都是用递归实现的，现在，我要求你不用递归，实现对二叉树的中序遍历。怎么办？我给个提示：广度优先遍历时候我们用了队，中序遍历，我们使用*栈*。看看能不能写出来，我也来写： #include // TreeNode //////////////////////////////////////////////////////////////////////////

树的遍历问题

树的遍历问题 【问题的提出】 给定一棵树，则可以得到它的DFS 和BFS 序列。 比如： BFS 序列为：1,2,3,4,5,6,9,7,8。 DFS 序列为：1,2,4,5,3,6,9,7,8。 所谓BFS ，就是从根节点开始扩展，深度小的优先。对于同一个节点若干个儿子，编号小的优先扩展。 所谓DFS ，就是从根节点开始扩展，深度大的优先。对于同一个节点若干个儿子，编号小的优先扩展。 请特别注意：同一个节点的若干儿子，编号小的优先扩展。这就是说对于一棵树，存在唯一的BFS 和DFS 遍历序列。 但是对于给定的BFS 和DFS 序列，是不是存在唯一的树和他们对应呢？ 比如一棵树的BFS 序列是(1,2,3,4)，DFS 序列是(1,2,3,4)，那么这棵树可以是： 有四棵不同的树可以与给定的BFS, DFS 序列对应。 根据这个模型，可以设计出一些问题。 【构造可行解】 构造性问题 给定BFS 和DFS 序列，求任意一棵原树。（或者判断无解） 我们按照DFS 序列的顺序来构造。 很显然DFS[1]=BFS[1]=根，DFS[2]=BFS[2]=根的最小编号儿子。 以DFS[1]作为根，DFS[2]作为根的儿子，就构成了一棵规模为2的树。 8 2 3 4

现在假设DFS 的前k-1个节点已经建好了树T k-1。下面考虑把第k 个节点（DFS[k]）插入到树T k-1中构成T k 。（k>=3） 因为DFS[1], DFS[2],…,DFS[k]这些点中，DFS[k]是在深度遍历中最后访问到的点，所以DFS[k]在T k 中的位置必然是“极右路径”上最末段的点。也就是说T k 是通过在T k-1的极右路径上插入DFS[k]而得到的。 可以设T k-1的极右路径是a 1, a 2, …, a t (t>=2)。设DFS[k]在BFS 序列中的前驱是v 。 显然a 1=根=BFS[1]。因为k>=3，所以DFS[k]≠DFS[2]同时DFS[2]=BFS[2]，于是就有DFS[k]≠BFS[2]。也就是说DFS[k]在BFS 序列中的位置不可能是2，所以v ≠BFS[1]，即v ≠a 1。下面分三种情况讨论。 第一种情况：存在i (2<=iDFS[k]。 从理论上说，可以有两种插入DFS[k]的方式。但是第二种方案必须满足DFS[k]>a t 。这显然和我们的条件矛盾。因此在第二种情况下，插入方式也是唯一的。 第三种情况：a t =v ，且a t