#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100 typedef struct Node{ int data; struct Node *lchild,*rchild; }BiTNode,*BiTree; void buildTree(BiTree *T){ char ch; scanf("%c",&ch); // printf("%c\n",ch); if(ch=='#') *T=NULL; else{ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=ch; buildTree(&(*T)->lchild); buildTree(&(*T)->rchild); } } void pre_order(BiTNode *p){ if(p){ printf("%c ",p->data); pre_order(p->lchild); pre_order(p->rchild); } } void pre_tranvese(BiTNode *T){ BiTree stack[MAX]; int top=-1; BiTree p=T; if(p==NULL) return; while(p||top>=0){ while(p){ printf("%c ",p->data); stack[++top]=p; p=p->lchild; } p=stack[top--]; p=p->rchild; } printf("\n"); } //中序遍历 void in_order(BiTree T){ if(T){ in_order(T->lchild); printf("%c ",T->data); in_order(T->rchild); } } void in_tranvese(BiTree T){ BiTree stack[MAX]; int top=-1; BiTree p=T; if(p==NULL) return; while(p||top>=0){ while(p){ stack[++top]=p; p=p->lchild; } p=stack[top--]; printf("%c ",p->data); p=p->rchild; } printf("\n"); } //后序遍历 void post_order(BiTree T){ if(T){ post_order(T->lchild); post_order(T->rchild); printf("%c ",T->data); } } void post_tranvese(BiTree T){ BiTree stack[MAX]; int top=-1; BiTree p=T,pre=NULL; while(p||top>=0){ while(p){ stack[++top]=p; p=p->lchild; } p=stack[top]; //p没有右孩子或者右孩子已经访问过直接访问p if(p->rchild==NULL||p->rchild==pre){ printf("%c ",p->data); pre=p; p=NULL;//p要设置为空 top--; }else{ p=p->rchild; } } printf("\n"); } int height(BiTree T){ int left,right; if(!T) return 0; left=height(T->lchild)+1; right=height(T->rchild)+1; return left>right ? left : right; } int leaf_count(BiTree T){ if(T==NULL) return 0; if(T->lchild==NULL&&T->rchild==NULL) return 1; return leaf_count(T->lchild)+leaf_count(T->rchild); } int nonleaf_count(BiTree T){ if(T==NULL) return 0; if(T->lchild==NULL&&T->rchild==NULL) return 0; //if(T->lchild!=NULL||T->rchild!=NULL) return 1; return nonleaf_count(T->lchild)+nonleaf_count(T->rchild)+1; } //先序 中序 创建树 void build_pre_in(BiTree *T,char *pre,char *in,int len){ char *temp; int k; if(len<=0) { *T=NULL; return; } for(temp=in;temp<in+len;temp++){ if(*temp==*pre){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=*temp; k=temp-in; break; } } build_pre_in(&((*T)->lchild),pre+1,in,k); build_pre_in(&((*T)->rchild),pre+k+1,temp+1,len-k-1); } //中序 后序 创建树 void build_in_post(BiTree *T,char *in,char *post,int len){ char *temp; int k; if(len<=0){ *T=NULL; return; } for(temp=in;temp<in+len;temp++){ if(*temp==*(post+len-1)){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=*temp; k=temp-in; //printf("%c \n",*temp); break; } } build_in_post(&((*T)->lchild),in,post,k); build_in_post(&((*T)->rchild),temp+1,post+k,len-k-1); } //中序 后序 -->先序 void in_post_pre(char *in,char *post,int len){ char *temp; int k; if(len<=0) return; for(temp=in;temp<in+len;temp++){ if(*temp==*(post+len-1)){ printf("%c ",*temp); k=temp-in; break; } } in_post_pre(in,post,k); in_post_pre(temp+1,post+k,len-k-1); } void main(){ char *pre= "ABDGEHICFJ"; char *in= "DGBHEIAFJC"; char *post= "GDHIEBJFCA"; BiTree T; //freopen("1.txt","r",stdin); //buildTree(&T); //build_pre_in(&T,pre,in,strlen(in)); build_in_post(&T,in,post,strlen(in)); printf("Pre Order:\n"); pre_order(T); printf("\n"); pre_tranvese(T); printf("In Order:\n"); in_order(T); printf("\n"); in_tranvese(T); printf("Post Order:\n"); post_order(T); printf("\n"); post_tranvese(T); printf("height of tree: %d\n",height(T)); printf("leaf count of tree:%d\n",leaf_count(T)); printf("non leaf count of tree:%d\n",nonleaf_count(T)); printf("in post-->pre\n"); in_post_pre(in,post,strlen(in)); printf("\n"); }