二叉树的先序扩展创建，先序、中序、后序遍历的递归、非递归算法，求树的深度

/* Case： #abdg e c f # #abdg h e e f # */ #include<stdio.h> #include<stdlib.h> #define MAX 20 struct node{ char ele; bool isleft; bool isright; struct node* lch; struct node* rch; }; typedef struct { struct node *e[MAX]; int top; }Stack; void InitStack(Stack &S,int dim) { int i; for(i=0;i<dim;i++){ S.e[i]=NULL; } S.top=-1; } void InitArray(char s[],int dim) { int i; for(i=0;i<dim;i++){ s[i]=NULL; } } void InitNode(struct node *p,char c){ p->ele=c; p->isleft=false; p->isright=false; p->lch=NULL; p->rch=NULL; } void Pop(Stack &S){ S.top--; } //先序扩展序列创建二叉树 struct node* PreCreatBinTree(char s[]) { int i=0; struct node *p; struct node *head; Stack S; InitStack(S,MAX); while(s[i]) { p=(struct node*)malloc(sizeof(struct node)); InitNode(p,s[i]); if(S.top==-1) { head=p; S.e[++S.top]=p; } else { if(s[i]!=' ') { if(!(S.e[S.top]->isleft)){ S.e[S.top]->lch=p; S.e[S.top]->isleft=true; } else{ S.e[S.top]->rch=p; S.e[S.top]->isright=true; } S.e[++S.top]=p; } else { if(!(S.e[S.top]->isleft)){ S.e[S.top]->isleft=true; } else { S.e[S.top]->isright=true; while((S.e[S.top]->isright)&&(S.top>-1)) { Pop(S); } } } } i++; } return head; } //先序遍历的递归算法 void PreTr_recursive(Stack &S) { struct node *p; if(S.top<=-1) return; if(S.e[S.top]->isleft) { printf("%c",S.e[S.top]->ele); S.e[S.top]->isleft=false; if(S.e[S.top]->lch) { p=S.e[S.top]->lch; S.e[++S.top]=p; } PreTr_recursive(S); } else if(S.e[S.top]->isright) { S.e[S.top]->isright=false; if(S.e[S.top]->rch) { p=S.e[S.top]->rch; S.e[++S.top]=p; PreTr_recursive(S); } else { Pop(S); PreTr_recursive(S); } } else { Pop(S); PreTr_recursive(S); } } //中序遍历的递归算法 void InTr_recursive(Stack &S) { struct node *p; if(S.top<=-1) return; if(!(S.e[S.top]->isleft)) { S.e[S.top]->isleft=true; if(S.e[S.top]->lch) { p=S.e[S.top]->lch; S.e[++S.top]=p; } InTr_recursive(S); } else if(!(S.e[S.top]->isright)) { S.e[S.top]->isright=true; printf("%c",S.e[S.top]->ele); if(S.e[S.top]->rch) { p=S.e[S.top]->rch; S.e[S.top]=p; InTr_recursive(S); } else { Pop(S); InTr_recursive(S); } } } //后序遍历的递归算法 void PostTr_recursive(Stack &S) { struct node *p; if(S.top<=-1) return; if(S.e[S.top]->isleft) { S.e[S.top]->isleft=false; if(S.e[S.top]->lch) { p=S.e[S.top]->lch; S.e[++S.top]=p; } PostTr_recursive(S); } else if(S.e[S.top]->isright) { S.e[S.top]->isright=false; if(S.e[S.top]->rch) { p=S.e[S.top]->rch; S.e[++S.top]=p; PostTr_recursive(S); } else { printf("%c",S.e[S.top]->ele); Pop(S); PostTr_recursive(S); } } else { printf("%c",S.e[S.top]->ele); Pop(S); PostTr_recursive(S); } } //先序遍历的非递归算法 void PreTr_nonrecursive(Stack &S) { struct node *p; while(S.top>-1) { if(!(S.e[S.top]->isleft)) { printf("%c",S.e[S.top]->ele); S.e[S.top]->isleft=true; if(S.e[S.top]->lch) { p=S.e[S.top]->lch; S.e[++S.top]=p; } } else if(!(S.e[S.top]->isright)) { S.e[S.top]->isright=true; if(S.e[S.top]->rch) { p=S.e[S.top]->rch; S.e[++S.top]=p; } else { Pop(S); } } else { Pop(S); } } } //中序遍历的非递归算法 void InTr_nonrecursive(Stack &S) { struct node *p; while(S.top>-1) { if(S.e[S.top]->isleft) { S.e[S.top]->isleft=false; if(S.e[S.top]->lch) { p=S.e[S.top]->lch; S.e[++S.top]=p; } } else if(S.e[S.top]->isright) { S.e[S.top]->isright=false; printf("%c",S.e[S.top]->ele); if(S.e[S.top]->rch) { p=S.e[S.top]->rch; S.e[S.top]=p; } else { Pop(S); } } } } //后序遍历的非递归算法 void PostTr_nonrecursive(Stack &S) { struct node *p; while(S.top>-1) { if(!(S.e[S.top]->isleft)) { S.e[S.top]->isleft=true; if(S.e[S.top]->lch) { p=S.e[S.top]->lch; S.e[++S.top]=p; } } else if(!(S.e[S.top]->isright)) { S.e[S.top]->isright=true; if(S.e[S.top]->rch) { p=S.e[S.top]->rch; S.e[++S.top]=p; } else { printf("%c",S.e[S.top]->ele); Pop(S); } } else { printf("%c",S.e[S.top]->ele); Pop(S); } } } //深度 后序遍历 void PostTr_degree(Stack &S) { struct node *p; int flag=0; int max; max=flag; while(S.top>-1) { if(S.e[S.top]->isleft) { S.e[S.top]->isleft=false; if(S.e[S.top]->lch) { p=S.e[S.top]->lch; S.e[++S.top]=p; flag++; } } else if(S.e[S.top]->isright) { S.e[S.top]->isright=false; if(S.e[S.top]->rch) { p=S.e[S.top]->rch; S.e[++S.top]=p; flag++; } else { Pop(S); if(max<flag) max=flag; flag--; } } else { Pop(S); if(max<flag) max=flag; flag--; } } printf("%d\n",max); } int main() { //先序扩展序列创建二叉树 printf("请输入先序序列，叶子节点用空格代替：\n"); char s[MAX]; InitArray(s,MAX); gets(s); struct node *head; head=PreCreatBinTree(s); //实现算法 Stack S; //先序遍历的递归算法 printf("\n先序遍历（递归）："); InitStack(S,MAX); S.e[++S.top]=head; PreTr_recursive(S); //实现算法 //中序遍历的递归算法 printf("\n中序遍历（递归）："); In