#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1 #define STACK_INIT_SIZE 100
#define STACKINCREMENT 10 typedef int Status;
typedef char ElemType;
typedef struct BTNode{//定义树节点结构体
ElemType data;
struct BTNode *l;
struct BTNode *r;
}BTNode,*BinTree;
typedef BinTree SElemType;
typedef struct{//非递归遍历要使用的栈操作定义
SElemType *base;
SElemType *top;
int stacksize;//当前的栈空间容量
}SqStack;
//定义二叉树的基本操作
BinTree CreateBinTree(BinTree T);//创建二叉树并且返回一个指针
Status Visit(ElemType e);
Status Depth(BinTree T);
Status PreOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));
Status LevelOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));
//定义栈的基本操作
Status InitStack(SqStack *S);
Status Destroy(SqStack *S);
Status StackEmpty(SqStack S);
Status GetTop(SqStack *s,SElemType *e);
Status Pop(SqStack *S,SElemType *e);
Status Push(SqStack *S,SElemType e);
Status StackTraverse(const SqStack *S);//常量？ Status PreOrderNoneRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));//非递归先序遍历 int main(){
//int depth;
BinTree Tree=NULL;
Status(*Visit)(ElemType e)=Visit;//使用函数指针，用指针调用函数
printf("请按先序遍历输入二叉树元素（空节点为=）:\n");
Tree=CreateBinTree(Tree);
printf("\n先序遍历：\n");
PreOrderRecursionTraverse(Tree,Visit);
printf("\n层序遍历：\n");
LevelOrderRecursionTraverse(Tree,Visit);
}
BinTree CreateBinTree(BinTree T){
char ch;
scanf("%c",&ch);
if(ch=='='){
T=NULL;
}else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))){
exit(OVERFLOW);
}
T->data=ch;
T->l=CreateBinTree(T->l);
T->r=CreateBinTree(T->r);
}
return T;//返回的T为最后一个结点
}
Status Visit(ElemType e){
if(e=='\0'){
return ERROR;
}else{
printf("%c",e);
}
return OK;
}
Status PreOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e))
{
if(T){//判空
if(!Visit(T->data)){//访问不成功，visit返回的是error
return ERROR;
}
PreOrderRecursionTraverse(T->l,Visit);
PreOrderRecursionTraverse(T->r,Visit);
}
return OK;
}
//层遍历
Status LevelOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e))
{
if(T){
int front=-;//每一次循环中表示从左到右的父节点的增加
int rear=-;//每一次循环当中用来表示front下一层该父节点左右子节点的变化增加
BTNode *Q[];//用来存储呢每一层从左到右的每一个树节点
Q[++rear]=T;
printf("根节点的数据：%d ",T->data);
while(front!=rear){
BTNode *p;
if(!(p=(BTNode *)malloc(sizeof(BTNode)))){
exit(OVERFLOW);
}
p=Q[++front];
if(p->l){
Q[++rear]=p->l;
printf("节点%d 的数据：%d",rear,p->l->data);
}
if(p->r){
Q[++rear]=p->r;
printf("节点%d 的数据：%d",rear,p->r->data);
}
} } }
/*
Status Depth(BinTree T){
int a,b;
if(!T){
return ERROR;
}else{
a=Depth(T->l)+1;
b=Depth(T->r)+1;
return a>b?a:b;
}
}
Status PreOrderNoneRecursionTraverse(BinTree T,Status(*Visit)(ElemType e)){
SqStack S;
SElemType p;
InitStack(&S);
Push(&S,T);//将T入栈作为第一个操作结点
while(S.base!=S.top){//栈不为空就一直循环，从上到下从左到右的取出
Pop(&S,&p);
if(!Visit(p->data)){//判断是否访问成功
return ERROR;
}
if(p->l){
Push(&S,p->r);//右结点先入栈为了后出栈
}
if(p->r){
Push(&S,p->l);
}
}
DestroyStack(&S);//释放栈
return OK;
}*/