哪位高手再帮我看一下怎么改?
程序代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 20 typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; int findposition(char ch,char b[],int l,int h) //在b[l]~b[h]的范围内寻找字符ch是否存在,若存在则返回其所在位置的下标 { int k; k=l; while(ch!=b[k]&&k<=h) k++; if(k>h)//对数据进行合法性检查 { printf("error\n"); exit(0); } else return(k);//返回其所在位置的下标 } //已知先序序列和中序序列构建二叉树 BiTree Create(char a[],int l1,int h1,char b[],int l2,int h2) { int k; BiTree t; if(l1>h1)//序列区间中没有元素,是一棵空树 return NULL; else if(l1==h1)//区间长度为1,则该结点就是根结点 { t=(BiTree)malloc(sizeof(BiTNode)); t->data=a[l1]; t->lchild=NULL;//不要忘了初始化 t->rchild=NULL; } else { k=findposition(a[l1],b,l2,h2);//在中序序列中找子树的根节点的位置k t=(BiTree)malloc(sizeof(BiTNode)); t->data=a[l1];//先序序列的第一个元素为根结点 t->lchild=Create(a,l1+1,l1+k-l2,b,l2,k-1);//递归构建左子树l1+(k-l2) t->rchild=Create(a,k+l1-l2+1,h1,b,k+1,h2);//递归构建右子树 } return(t);//返回结点的指针 } //已知中序序列和后序序列构建二叉树 BiTree Create2(char a[],int l1,int h1,char b[],int l2,int h2) { int k; BiTree t; if(l2>h2) return NULL; else if(l2==h2) { t=(BiTree)malloc(sizeof(BiTNode)); t->data=b[h2]; t->lchild=NULL; t->rchild=NULL; } else { k=findposition(b[h2],a,l1,h1); t=(BiTree)malloc(sizeof(BiTNode)); t->data=b[h2];//后序序列的最后一个元素为根结点 t->lchild=Create2(a,l1,k-1,b,l2,l2+k-l1-1);//递归构建左子树l2+k-l1-1 t->rchild=Create2(a,k+1,h1,b,l2+k-l1,h2-1);//递归构建右子树 } return(t); } void PostTraverse(BiTree t) /*后序遍历二叉树*/ { if(t) { PostTraverse(t->lchild); PostTraverse(t->rchild); printf("%c",t->data); } } void PreTraverse(BiTree t) /*先序遍历二叉树*/ { if(t) { printf("%c",t->data); PreTraverse(t->lchild); PreTraverse(t->rchild); } } void main( ) { BiTree t; int n,m,l; char a[MAX],b[MAX],c[MAX]; printf("参考数据:\nabdce bdaec dbeca\n"); printf(" a \n"); printf(" b c \n"); printf(" * d e * \n"); printf("---------------------------------\n"); printf("请输入先序遍历序列:\n"); scanf("%s",a); printf("请输入中序遍历序列:\n"); scanf("%s",b); printf("请输入后序遍历序列:\n"); scanf("%s",c); n=strlen(a); m=strlen(b); l=strlen(c); t=Create(a,0,n-1,b,0,m-1); printf("<------------------------------->\n"); printf("已知先序和中序求得的后序遍历结果:\n"); PostTraverse(t); printf("\n"); printf("<------------------------------->\n"); printf("已知中序和后序求得的先序遍历结果:\n"); t=Create2(b,0,m-1,c,0,l-1); PreTraverse(t); printf("\n"); }
实现的功能:
1.已知前序和中序序列构建的二叉树
2.已知中序和后序序列构建的二叉树
已在VC++6.0环境下运行通过,供大家参考!