| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2726 人关注过本帖
标题:非递归遍历输出二叉树
只看楼主 加入收藏
haroldi
Rank: 1
等 级:新手上路
帖 子:158
专家分:0
注 册:2006-7-22
收藏
 问题点数:0 回复次数:7 
非递归遍历输出二叉树
请多多指教!
http://blog.bc-cn.net/user15/82588/archives/2006/1864.shtml
搜索更多相关主题的帖子: 二叉树 遍历 递归 输出 
2006-10-10 00:21
haroldi
Rank: 1
等 级:新手上路
帖 子:158
专家分:0
注 册:2006-7-22
收藏
得分:0 
//非递归方式建树,并按任一种非递归遍历次序输出二叉树中的所有结点;
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType;
typedef struct TNode{
ElemType data;
struct TNode *lchild,*rchild;
}BTree;
//------------------------------------------------------------------------------
ElemType str[]="A(B(C(D,E(F,G(,H))),I(J,K(L))),M)"; //"A(B(D,E(G,H(I))),C(F))";
//------------------------------------------------------------------------------
void CreateBTree(BTree **T,ElemType *Str); //非递归建树;
void TraverseBTree(BTree *T); //选择非递归算法的遍历方式;
void PreOrderUnrec(BTree *T); //先序遍历非递归算法;
void InOrderUnrec(BTree *T); //中序遍历非递归算法;
void PostOrderUnrec(BTree *T); //后序遍历非递归算法;
void LevelOrderUnrec(BTree *T); //层次遍历非递归算法;
//------------------------------------------------------------------------------
int main(void)
{
BTree *T = NULL; printf("\n二叉树的广义表格式为:\n\t"); puts(str);
CreateBTree(&T,str);
TraverseBTree(T);
system("pause"); return 0;
}
//------------------------------------------------------------------------------
void CreateBTree(BTree **T,ElemType *Str)
{ //按二叉树广义表建立对应的二叉树存储结构;
BTree *p = NULL,*Stack[MaxSize];//数组为存储树根结点指针的栈,p为指向树结点的指针;
int top = -1; //top为Stack栈的栈顶指针;
char flag; //flag为处理结点的左子树(L)和右子树(R)的标记;
*T = NULL;
while(*Str)
{
if (*Str == '(') {Stack[++top] = p;flag = 'L';} //入栈;
else if(*Str == ')') --top; //出栈;
else if(*Str == ',') flag = 'R';
else
{
if(!(p = (BTree *)malloc(sizeof(BTree)))) exit (1);
p->data = *Str;
p->lchild = p->rchild = NULL; //初始化新结点;
if(*T == NULL) *T = p; //根结点;
else
{
if(flag == 'L') Stack[top]->lchild = p;
if(flag == 'R') Stack[top]->rchild = p;
}
}
++Str;
}
}
//------------------------------------------------------------------------------
void TraverseBTree(BTree *T) //选择非递归算法的遍历方式;
{
int mark;
printf("\n非递归算法遍历方式:\n\t1 --- 前序遍历\n\t2 --- 中序遍历");
printf("\n\t3 --- 后序遍历\n\t4 --- 按层遍历\n\tq --- 退 出\n请选择:\n");
if(T == NULL) printf("该树为空!\n");
while(T != NULL && scanf("%d",&mark)==1)
{
if(mark==1) {printf("先序遍历:\t");PreOrderUnrec(T);}
else if(mark==2) {printf("中序遍历:\t");InOrderUnrec(T);}
else if(mark==3) {printf("后序遍历:\t");PostOrderUnrec(T);}
else if(mark==4) {printf("层次遍历:\t");LevelOrderUnrec(T);}
else
{
system("cls"); printf("\n二叉树的广义表格式为:\n\t"); puts(str);
printf("\n非递归算法遍历方式:\n\t1 --- 前序遍历\n\t2 --- 中序遍历");
printf("\n\t3 --- 后序遍历\n\t4 --- 按层遍历\n\tq --- 退 出\n请选择:\n");
printf("数据非法,重新输入!\n");
}
printf("\n");
}
printf("\n请多多指教! by Haroldi.");
}
//------------------------------------------------------------------------------
void PreOrderUnrec(BTree *T) //先序遍历非递归算法;
{
BTree *p = T,*Stack[MaxSize];
int top = -1;
while (p != NULL || top != -1)
{
while (p!=NULL) //遍历左子树;
{
printf("%c ",p->data);
Stack[++top] = p;
p=p->lchild;
}
if (top != -1) //下次while内循环中实现右子树遍历;
{
p = Stack[top--];
p=p->rchild;
}
}
}
//------------------------------------------------------------------------------
void InOrderUnrec(BTree *T) //中序遍历非递归算法;
{
BTree *p = T,*Stack[MaxSize];
int top = -1;
while (p != NULL || top != -1)
{
while (p!=NULL)
{
Stack[++top] = p;
p=p->lchild;
}
if (top != -1)
{
p = Stack[top--];
printf("%c ",p->data);
p=p->rchild;
}
}
}
//------------------------------------------------------------------------------
void PostOrderUnrec(BTree *T) //后序遍历非递归算法;
{
BTree *p = T,*Stack[MaxSize];
int top = -1;
char flag[MaxSize];//标识,若为'R'则说明左右孩子均已遍历,防止再次走过,形成死循环;
while(p != NULL || top != -1)
{
while(p != NULL)
{
Stack[++top] = p;
flag[top] = 'L';
p = p->lchild;
}
while(top != -1 && flag[top] == 'R')
{
printf("%c ",Stack[top--]->data); //flag='R',在此退栈;
}
if(top != -1) {flag[top] = 'R'; p = Stack[top]->rchild;}
}
}
//------------------------------------------------------------------------------
void LevelOrderUnrec(BTree *T) //层次遍历非递归算法;
{
BTree *p,*Queue[MaxSize]; //定义队列,存储树结点指针;
int front,rear; //定义队首和队尾指针;
front = rear = 0; //初始化置0,空队列;
if(T != NULL)
{
rear = (rear+1)%MaxSize; //队尾指针后移;
Queue[rear] = T; //树根结点入队;
}
while (front != rear) //队列非空时;
{
front = (front+1)%MaxSize; //队首指针后移;
p = Queue[front]; //删除队首结点;
printf("%c ",p->data); //输出队首结点的值;
if(p->lchild != NULL) //若存在左孩子,则左孩子指针入队;
{
rear = (rear+1)%MaxSize;
Queue[rear] = p->lchild;
}
if(p->rchild != NULL) //若存在右孩子,则右孩子指针入队;
{
rear = (rear+1)%MaxSize;
Queue[rear] = p->rchild;
}
}
}
//------------------------------------------------------------------------------

Do people want thick road ...
2006-10-10 00:40
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 

#include"stdio.h"
#include"string.h"
typedef char datatype;
typedef struct node{ /*树的定义*/
datatype data;
struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;

typedef struct stack{ /*栈定义*/
bintree opst[100];
int tag[100];
int top;
}seqstack;

void push(seqstack *s,bintree t) /*进栈*/
{ s->opst[++s->top]=t;
}

bintree pop(seqstack *s)/*出栈*/
{ if(s->top!=-1)
{ s->top--;
return(s->opst[s->top+1]);
}
else return NULL;
}

void createbintree(bintree *t)/*按照前序遍历顺序建立一棵给定的二叉树*/
{ char ch;
if((ch=getchar())==' ')
*t=NULL;
else{
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}

void prebintree(bintree t) /*前序遍历的递归实现*/
{ if(t)
{ printf("%c",t->data);
prebintree(t->lchild);
prebintree(t->rchild);
}
}

void inbintree(bintree t)/*中序遍历的递归实现*/
{ if(t)
{ inbintree(t->lchild);
printf("%c",t->data);
inbintree(t->rchild);
}
}


void posbintree(bintree t) /*后序遍历的递归实现*/
{ if(t)
{ posbintree(t->lchild);
posbintree(t->rchild);
printf("%c",t->data);
}
}

void fprebintree(bintree t) /*前序遍历的非递归实现*/
{ seqstack s;
s.top=-1;
while(t||(s.top!=-1))
if(t)/*将当前根结点先打印后进栈*/
{ printf("%c",t->data);
s.opst[++s.top]=t;
t=t->lchild;
}
else /*当前左子树已经建好,将栈顶元素出栈建右子树*/
{ t=pop(&s);
t=t->rchild;
}
}

void finbintree(bintree t) /*中序遍历的非递归实现*/
{ seqstack s;
s.top=-1;
while(t||(s.top!=-1))
if(t)/*将当前根结点进栈*/
{
push(&s,t);
t=t->lchild;
}
else
{ t=pop(&s);
printf("%c",t->data);
t=t->rchild;
}
}

void fposbintree(bintree t)/*后序遍历的非递归实现*/
{ seqstack s;
s.top=-1;
while(t||(s.top!=-1))
{ if(t)
{
s.opst[++s.top]=t;
s.tag[s.top]=0;
t=t->lchild;
}
else
{ while((s.top!=-1)&&(s.tag[s.top]==1))
{ t=s.opst[s.top];
printf("%c",t->data);
s.top--;
}
if(s.top!=-1)
{ t=s.opst[s.top];
s.tag[s.top]=1;
t=t->rchild;
}
else t=NULL;
}
}
}


倚天照海花无数,流水高山心自知。
2006-10-10 13:52
sunnvya
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:1094
专家分:0
注 册:2005-11-23
收藏
得分:0 
漂亮

http://www. 第二站>>>提供源码下载
2006-10-10 14:01
lylyxt
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2006-11-27
收藏
得分:0 
不错!!!

2006-11-27 09:13
海天飞鸿
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2006-11-20
收藏
得分:0 
如果要产生随机数再生成二叉树,
及其遍历,该怎么改???用数组吗?
2006-12-16 14:32
左手无名指
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2007-5-16
收藏
得分:0 

谢谢版主
2007-05-17 06:59
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
回复:(海天飞鸿)如果要产生随机数再生成二叉树,及其...
和建立二叉排序树一样.可以不用数组保存.

倚天照海花无数,流水高山心自知。
2007-05-17 10:29
快速回复:非递归遍历输出二叉树
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024032 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved