二叉树的非递归遍历

任务：建立一棵二叉树，要求分别用递归和非递归方法实现二叉树的先序、中序和后序遍历。求高手解答啊

哈，我们数据结构的实验：
typedef int Status;
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, * rchild;//左右孩子指针
}BiTNode, *BiTree;
typedef struct SqQueue
{
TElemType front ,rear ;
BiTree data[MAXQSIZE]; //循环队列元素类型为二叉链表结点指针
int count;
}SqQueue; //循环队列结构定义
int stack[MAX_TREE_SIZE],top=0;

Status CreateBiTree(BiTree *T)
{
//按先序输入二叉树中的结点的值（一个字符）,空格字符表示空树
//构造二叉链表表示的二叉树T
TElemType input;
if(!(*T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
fflush(stdin);
if(!fscanf(in,"%d",&input))
{
printf("Read Data Error!");
getch();
exit(0);
}
if(input==-1)
{
*T = NULL;
return FALSE;
}
else
{
(*T)->data=input;
//printf("%d",input);
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return OK;
}

Status PreOrderTraverse(BiTree T)
{
//先序遍历二叉树T的递归算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status PreOrder(BiTree T)
{
//先序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//后序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//后序遍历二叉树T的非递归算法
unsigned sign;//记录结点从栈中弹出的次数
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到结点T时压入其指针
push(1);//置标志为1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走过T的左子树
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子树都已走过
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}

序遍历有问题：改后如下 void InOrder(BTNode *b)//中序遍历 { BTNode *p,*stack[MaxNode]; int top=0; if(b==NULL) return; p=b; while(!(p == NULL

#include <stdio.h> #include <stdlib.h> struct tree { char data; struct tree *lchild; struct tree *rchild; }; typedef struct tree * treptr; treptr build(treptr t)//先序建树 { char c; c=getchar(); if(c=='#') { t=null; } else { t=(treptr)malloc(sizeof(struct tree)); t->data=c; t->lchild=build(t->lchild); t->rchild=build(t->rchild); } return t; } void postdorder(treptr root)//这是递归实现 { if (root!=null) { postdorder(root->lchild); postdorder(root->rchild); printf("%c",root->data); } } struct stack { treptr *top,*base; }; typedef struct stack *stackptr; void init (stackptr s)//初始化栈 { s->base=(treptr*)malloc(sizeof(treptr)*100); s->top=s->base; } void push(stackptr s,treptr t)//入栈 { *(s->top++)=t; } treptr pop(stackptr s)//弹出栈顶元素 { treptr t; t=*(--(s->top)); return t; } treptr gettop(stackptr s)//取栈顶元素 { treptr *l=s->top-1; return *(l); } void postorder(treptr t)//这是非递归后序实现 { stackptr s=(stackptr)malloc(sizeof(struct stack)); treptr temp=t; treptr p; treptr lastvist=null; init(s); p=t; while(p||s->top!=s->base) { while(p) { push(s,p); p=p->lchild; } temp=gettop(s); if(temp->rchild==null||temp->rchild==lastvist) { putchar(temp->data); lastvist=pop(s); } else p=temp->rchild; } } int main() { treptr t=null; t=build(t); postdorder(t); printf("非递归后序遍历\ "); postorder(t); printf("\ "); return 0; } 程序如上，可以运行。 我空间中有中序遍历的非递归实现。 不过给你写的是后序遍历的递归实现和非递归实现，它两个输出的结果是一致的。 输入 234##5#6##7##回车 就可以看到结果。 中序遍历及其对应树可以参考我空间中的文章 http://hi.baidu.com/huifeng00/blog/item/2ca470f56694f62e730eec39.html

#include #include #include #include typedef struct BiTNode { int data; BiTNode *lchild,*rchild; // 左右孩子指针 }BiTNode,*BiTree; void visit(int e) { printf("->%d",e); } void InitBiTree(BiTree &T)// 操作结果：构造空二叉树T { T=NULL; } void CreateBiTree(BiTree &T) //按先序次序输入二叉树中结点的值,构造二叉链表表示的二叉树T。变量Nil表示空(子)树。 { int number; scanf("%d",&number); // 输入结点的值 if(number==0) // 结点的值为空 T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点 if(!T) exit(OVERFLOW); T->data=number; // 将值赋给T所指结点 CreateBiTree(T->lchild); // 递归构造左子树 CreateBiTree(T->rchild); // 递归构造右子树 } } void DestroyBiTree(BiTree &T)// 初始条件：二叉树T存在。操作结果：销毁二叉树T { if(T) // 非空树 { DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作 DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作 free(T); // 释放根结点 T=NULL; // 空指针赋0 } } void PreOrderTraverse(BiTree T,void(*Visit)(int)) //二叉树T存在，Visit是对结点操作的应用函数,先序递归遍历T，对每个结点调用函数Visit一次且仅一次 { if(T) //T不为空时遍历 { Visit(T->data); // 先访问根结点 PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树 PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树 } } void InOrderTraverse(BiTree T,void(*Visit)(int)) //二叉树T存在，Visit是对结点操作的应用函数，中序递归遍历T，对每个结点调用函数Visit一次且仅一次 { if(T) { InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树 Visit(T->data); // 再访问根结点 InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树 } } void PostOrderTraverse(BiTree T,void(*Visit)(int)) // 二叉树T存在，Visit是对结点操作的应用函数，后序递归遍历T，对每个结点调用函数Visit一次且仅一次 { if(T) // T不空 { PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树 PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树 Visit(T->data); // 最后访问根结点 } } void main() { char m; BiTree T; InitBiTree(T); // 初始化二叉树T do{ printf("\n"); printf("##################二叉树的基本操作###########################\n"); printf("×××××××××1.二叉树的创建××××××××××××××\n"); printf("×××××××××2.先序递归遍历二叉树×××××××××××\n"); printf("×××××××××3.中序递归遍历二叉树×××××××××××\n"); printf("×××××××××4.后序递归遍历二叉树×××××××××××\n"); printf("×××××××××5.退出程序××××××××××××××××\n"); printf("#############################################################\n"); printf("请输入你的选择:"); scanf("%c",&m); switch(m) { case '1': printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，如：（1 2 3 0 0 4 5 0 6 0 0 7 0 0 0）\n"); printf("\n请按先序次序输入二叉树中结点的值："); CreateBiTree(T); // 建立二叉树T break; case '2': printf("先序递归遍历二叉树： "); PreOrderTraverse(T,visit); // 先序递归遍历二叉树T break; case '3': printf("\n中序递归遍历二叉树： "); InOrderTraverse(T,visit); // 中序递归遍历二叉树T break; case '4': printf(" \n后序递归遍历二叉树："); PostOrderTraverse(T,visit); // 后序递归遍历二叉树T break; case '5':break; default: printf("输入的字符不对，请重新输入!"); break; } getchar(); }while(m!='5'); }