如何在linux系统中用C语言编程实现以非递归的方式查询指定目录下所有子目录的全部文件并保存文件名？
把迭代得到的非文件文件夹项，即子目录保存到一个stack中。
随后逐个弹出栈顶元素并迭代之，就实现了以非递归方式遍历文件夹。
C语言前序遍历输入后序非递归遍历输出算法
//输入先序扩展序列: 6 5 0 0 7 0 0
//后序遍历序列: 5 7 6
// 6
// / \
// 5 7
// / \ / \
// 0 0 0 0
//输入先序扩展序列: 4 2 1 0 0 3 0 0 5 0 6 0 0
//后序遍历序列: 1 3 2 6 5 4
//
// 4
// / \
// 2 5
// / \ / \
// 1 3 0 6
// / \ / \ / \
// 0 0 0 0 0 0
#includestdio.h
#includestdlib.h
#define max 100 //20 //栈的大小
struct bitree //二叉树的结构体
{
int data;
struct bitree *llink; //左分支
struct bitree *rlink; //右分支
};
struct stack_post //栈的结构体 [用于后序遍历]
{
struct bitree *bt; //指向二叉树
int leftOrRight; //当前节点是哪个分支,1=左分支 0=右分支
};
struct stack_post sk[max]; //全局变量:栈(用于后序遍历)
//void build(struct bitree *n)
//创建二叉树: 先序扩展序列 + 递归法
void build(struct bitree **n)
{
//注:struct bitree **n 是指针的指针
int ch;
scanf(“%d”,ch);
if(ch==0)
{
*n=NULL;
}
else
{
*n=(struct bitree *)malloc(sizeof(struct bitree));
if(*n == NULL)
{
printf(“\nMemory overflow!\n”);
exit(1);
}
(*n)-data=ch;
build(((*n)-llink));
build(((*n)-rlink));
}
//原代码
/*
n=(struct bitree *)malloc(sizeof(struct bitree));
scanf(“%d”,ch);
if(ch==0)
n=NULL;
else
{
if(!(n=(struct bitree *)malloc(sizeof(struct bitree))))
{
return;
}
n-data=ch;
build(n-llink);
build(n-rlink);
}
*/
}
//后序遍历序列(非递归)
void Post_Order(struct bitree *n)
{
struct bitree *p=NULL;
////struct stack_post sk[max]; //全局变量:栈(用于后序遍历)
int top=0; //栈顶为0, top=1用于存放第1个数据
int leftOrRight; //当前节点是哪个分支,1=左分支 0=右分支
struct bitree *tmpTree;
if(n == NULL) return;
p = n; //当前二叉树的节点
leftOrRight = 1; //1=左分支(默认从左分支开始遍历)
while(p != NULL)
{
if(p-llink != NULL) //有左分支,当前节点入栈
{
top++;
sk[top].bt=p;
sk[top].leftOrRight=leftOrRight;
p = p-llink;
leftOrRight = 1;
}
else if(p-rlink != NULL) //有右分支,当前节点入栈
{
top++;
sk[top].bt=p;
sk[top].leftOrRight=leftOrRight;
p = p-rlink;
leftOrRight = 0;
}
else //该节点是”叶子”
{
printf(“%d “,p-data);
while(1) //处于”回溯”状态
{
tmpTree=sk[top].bt; //看[栈顶]
if(tmpTree==NULL) //[栈]已经没有数据
{
p=NULL; //整个遍历过程结束,退出循环
break;
}
if(leftOrRight == 1) //处于”左分支”回溯
{
if(tmpTree-rlink == NULL)//[栈顶]的节点没有右分支,出栈,打印
{
p=sk[top].bt;
leftOrRight=sk[top].leftOrRight;
top–;
printf(“%d “,p-data);
//仍然处于”回溯”状态
}
else //[栈顶]的节点有右分支,不出栈,右分支成为当前节点
{
p=tmpTree-rlink;
leftOrRight=0; //设置当前处于右分支
break; //退出”回溯”状态
}
}
else //处于”右分支”回溯
{
//[栈]有节点,出栈,打印
p=sk[top].bt;
leftOrRight=sk[top].leftOrRight;
top–;
printf(“%d “,p-data);
//仍然处于”回溯”状态
}
} //while(1)结束
} //if(p-llink != NULL)else结束
} //while(p != NULL)结束
//栈顶top=0,说明[栈]已经没有数据
printf(“\n核对,栈顶 top = %d\n”,top);
}
//有错误
//原代码,后序遍历序列(非递归)
/*
void postorder(struct bitree *n)
{
struct bitree *p,*q;
int i;
p=(struct bitree *)malloc(sizeof(struct bitree));
p=n;
q=(struct bitree *)malloc(sizeof(struct bitree));
struct bitree *s[max];
for(i=0;imax;i++)
{
s[i]=(struct bitree *)malloc(sizeof(struct bitree));
}
int top=-1;
do
{
while(p!=NULL)
{
if(p-rlink!=NULL)
{
top++;
s[top]=p-rlink;
}
p=p-llink;;
}
p=s[top];
top–;
if(p-rlink==NULL||p-rlink==q)
{
printf(“%d “,p-data);
q=p;
p=NULL;
}
else
p=p-rlink;
}while(p!=NULL||top!=-1);
}
*/
//后序遍历序列(递归) [用于对比测试]
void postTest(struct bitree *n)
{
if(n!=NULL)
{
postTest(n-llink);
postTest(n-rlink);
printf(“%d “,n-data);
}
}
int main()
{
struct bitree *n;
//原代码n=(struct bitree *)malloc(sizeof(struct bitree));
printf(“Input the preorder-numbers of the tree(‘0’ for NULL):\n”);
//原代码build(n);
build(n);
printf(“\nPostorder is below: “);
//原代码postorder(n); //后序遍历序列(非递归)
Post_Order(n); //后序遍历序列(非递归)
printf(“\n后序遍历序列(递归): “);
postTest(n); //用于对比测试
printf(“\n”);
return 0;
}
二叉树先序非递归遍历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-rchildh-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”);
}
二叉树中序遍历非递归算法(c语言实现）
#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)
{
struct node *p;
struct node *stack[20];
int top=0;
p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p-lchild ;
}
p=stack[–top];
printf(“%c “,p-data );
p=p-rchild ;
}
}
//主函数
int main()
{
struct node * head;
char pre[30],ord[30];
int n;
gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf(“\n”);
inorder1(head);
printf(“\n”);
}
//测试事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
几个月前自己编写，原版
vc++ 6.0实验通过
怎么样，老板，第一次上百度知道，好激动
给点面子
给分！给分啊
先序遍历的非递归算法。用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
层次序的非递归遍历算法的实现代码(C语言)..
是二叉链表的层次遍历吧？
#include stdlib.h
//定义动态分配空间的二叉链表类型
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//层次遍历输出二叉链表的所有结点的值
void LevelOrderTraverse(BiTree T){
typedef struct PNode{
BiTNode *ptr;struct PNode *next;
}PNode;//定义链表结点类型，链表的数据域存放二叉链表结点的指针
PNode *R,*L,*p;
if(T){
R=(PNode*)malloc(sizeof(PNode));//建立第一个链表结点
if(!R){
printf(“\nLevelOrderTraverse Error: Failed To MALLOC Memory!”);
return;
}
R-ptr=T;R-next=NULL;//R指向尾结点，尾结点指针域必须为空
L=R;p=L;//L指向链表头结点
while(p){//p结点的数据域指向当前处理的二叉链表结点
printf(“%c”,p-ptr-data);
if(p-ptr-lchild){//如果有左孩子，添加一个结点
R-next=(PNode*)malloc(sizeof(PNode));
if(!(R-next)){
printf(“\nLevelOrderTraverse Error: Failed To MALLOC Memory!”);
return;
}
R=R-next;R-ptr=p-ptr-lchild;R-next=NULL;//R重新指向尾结点，尾结点的数据域为当前处理的二叉链表结点的左孩子指针
}
if(p-ptr-rchild){//如果有右孩子，添加一个结点
R-next=(PNode*)malloc(sizeof(PNode));
if(!(R-next)){
printf(“\nLevelOrderTraverse Error: Failed To MALLOC Memory!”);
return;
}
R=R-next;R-ptr=p-ptr-rchild;R-next=NULL;
}
L=p-next;//L指向下一个链表结点，准备释放p结点
free(p);//释放p结点
p=L;//p重新指向链表头结点
}
}
}
这里使用了队列结构来存储某个结点的孩子结点。
微信扫一扫 
支付宝扫一扫 
