#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=-1;//每一次循环中表示从左到右的父节点的增加 int rear=-1;//每一次循环当中用来表示front下一层该父节点左右子节点的变化增加 BTNode *Q[100];//用来存储呢每一层从左到右的每一个树节点 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; }*/