Question

二叉树的遍历c++代码，要求同时使用递归和非递归

要求在一个主函数里面同时运用递归和非递归

各位大虾帮忙啊，在线等哦~！符合要求，能够运行的都一定给分，在顺便给些相关的注释，谢谢咯~！

Answer 1

递归的：
#include <stdlib.h>
#include <stdio.h>

#define STACK_INIT_SIZE 50 /*MAXSIZE 存储空间初始分配量*/
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW 0

typedef int Status;
typedef char TElemType;

typedef struct s_BiTNode /*定义二叉树结构*/
{
TElemType data;
struct s_BiTNode *lchild,*rchild;
} BiTNode, *BiTree;

Status CreateBiTree(BiTree *T);
Status PreOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status Visit(TElemType e);

void main() /*main() 函数*/
{
BiTree Tr=NULL;

printf("下面以'根左右'的先序扩展顺序构造二叉树:\n");
printf("\n请输入二叉树元素,(/表示空),如 ABDG///EH//IK///C/F/J//\n");

if(CreateBiTree(&Tr)) /*调用 CreateBiTree()*/
printf("构造二叉树成功!\n");
else
printf("构造二叉树失败!\n");

printf("\n先序遍历序列为: ");
PreOrderTraverse(Tr,Visit);

printf("\n中序遍历序列为: ");
InOrderTraverse(Tr,Visit);

printf("\n后序遍历序列为: ");
PostOrderTraverse(Tr,Visit);

printf("\n");
getch();
}

Status CreateBiTree(BiTree *Tree)
{
TElemType ch;
scanf("%c",&ch);
if(ch == '/')
(*Tree) = NULL;
else
{
if(!((*Tree) = (BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
(*Tree)->data = ch;
CreateBiTree(&((*Tree)->lchild));
CreateBiTree(&((*Tree)->rchild));
}
return (OK);
}/*CreateBiTree*/

Status PreOrderTraverse(BiTree T,Status (*Fun) (TElemType e))//*Fun是指向函数Visit的指针
//他的参数是(TElemType e) 他的返回类型是int
{
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Fun))
if(PreOrderTraverse(T->rchild,Fun))
return OK;
return ERROR;
}
else
return OK;
}
Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e))
{
if(T)
{
if(InOrderTraverse(T->lchild,Fun))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Fun))
return OK;
return ERROR;
}
else
return OK;
}/*InOrderTraverse*/

Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e))
{
if(T)
{
if(PostOrderTraverse(T->lchild,Fun))
if(PostOrderTraverse(T->rchild,Fun))
{
Visit(T->data);
return OK;
}
return ERROR;
}
else
return OK;
}

Status Visit(TElemType e)
{
printf("%c",e);
return OK;
}

非递归的：
#include <stdlib.h>
#include <stdio.h>

#define STACK_INIT_SIZE 50 /*MAXSIZE 存储空间初始分配量*/
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW 0

typedef int Status;
typedef char TElemType;

typedef struct s_BiTNode /*定义二叉树结构*/
{
TElemType data;
struct s_BiTNode *lchild,*rchild;
} BiTNode, *BiTree;

Status CreateBiTree(BiTree *T);
Status PreOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e));
Status Visit(TElemType e);

void main() /*main() 函数*/
{
BiTree Tr=NULL;

printf("下面以'根左右'的先序扩展顺序构造二叉树:\n");
printf("\n请输入二叉树元素,(/表示空),如 ABDG///EH//IK///C/F/J//\n");

if(CreateBiTree(&Tr)) /*调用 CreateBiTree()*/
printf("构造二叉树成功!\n");
else
printf("构造二叉树失败!\n");

printf("\n先序遍历序列为: ");
PreOrderTraverse(Tr,Visit);

printf("\n中序遍历序列为: ");
InOrderTraverse(Tr,Visit);

printf("\n后序遍历序列为: ");
PostOrderTraverse(Tr,Visit);

printf("\n");
getchar();
}

Status CreateBiTree(BiTree *Tree)
{
TElemType ch;
scanf("%c",&ch);
if(ch == '/')
(*Tree) = NULL;
else
{
if(!((*Tree) = (BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
(*Tree)->data = ch;
CreateBiTree(&((*Tree)->lchild));
CreateBiTree(&((*Tree)->rchild));
}
return (OK);
}/*CreateBiTree*/
Status PreOrderTraverse(BiTree T,Status (*Fun)(TElemType e))
{
BiTNode *St[STACK_INIT_SIZE],*p;
int top=-1;
if(T)
{
top++;
St[top]=T;
while(top>-1)
{
p=St[top];
top--;
Visit(p->data);
if(p->rchild)
{
top++;
St[top]=p->rchild;
}
if(p->lchild)
{
top++;
St[top]=p->lchild;
}
}
return OK;
}
else
return OK;
}
Status InOrderTraverse(BiTree T,Status (*Fun) (TElemType e))
{
BiTNode *St[STACK_INIT_SIZE],*p;
int top=-1;
if(T)
{
p=T;
while(top>-1||p)
{
while(p)
{
top++;
St[top]=p;
p=p->lchild;
}

if(top>-1)
{
p=St[top];
top--;
Visit(p->data);
p=p->rchild;
}
}
return OK;
}
else
return OK;
}/*InOrderTraverse*/

Status PostOrderTraverse(BiTree T,Status (*Fun) (TElemType e))
{
BiTNode *St[STACK_INIT_SIZE];
BiTNode *p;
int flag,top=-1;
if(T)
{
do
{
while(T)
{
top++;
St[top]=T;
T=T->lchild;
}
p=NULL;
flag=1;
while(top!=-1&&flag)
{
T=St[top];
if(T->rchild==p)
{
Visit(T->data);
top--;
p=T;
}
else
{
T=T->rchild;
flag=0;
}
}
}while(top!=-1);
}
else
return OK;
}

Status Visit(TElemType e)
{
printf("%c",e);
return OK;
}

Answer 2

你给我发个邮件吧。在这里写费劲，如果急需，半小时内就给你，我回寝室用我电脑给你写，可否，我要到点了。如果认可分可要给我哦~！~
lijianlong1314@vip.qq.com
我的是按C语言写的算法（本人C++实力还不足），如果不行那也没有办法了，
我以中归遍历为例，并把思路给你。
Void Intravse(BiTree T)
//系统在运行时自动在内存中生成一个栈
{
if(t==Null)
return;
InTravse(T->lchild);
//输出左子树，如果有把它压栈，一直到没有左子树
visit(T->data);
//传出T的值
InTravse(T->rchild);
//与左子树相同
}//这是按照“左-根-右”的思路编的

下面是没有递归方法的中归遍历，先把思路给你
1.建栈
2.根结点入栈
3.循环（当栈不为空时）
1）循环进行：读取栈顶元素，当栈顶元素不为空时 ，压左子树入栈；
2）弹出栈顶元素（Null）；
3）若栈不为空，从栈顶弹出元素，访问该元素，并 压右子树入栈。
Void Inravse(BiTree T)
{
Initstack(s);
Push(s,T);
while(!Elmptystack(s))
{
while(GetTop(s,p)&&p)
//先根遍历把visit(p->data);放这
Push(s,p->lchild);
Pop(s,p);
if(!Elmptystack(s))
{
Pop(s,p);
visit(p->data);
Push(s,p->rchild);
//后根遍历把visit(p->data);放这
}
}
}
ps:C++内包含C语言的全部语法