|
发表于 2014-4-27 22:13:05
|
显示全部楼层
大致修改了下。主要还是老问题,你的递归没有返回,导致无限循环。 CreatBiTree_pmid_post这个函数我猜着给你写了个Base Case。PreOrderTraverse这个函数我不知道该怎么写所以你自己看看吧。具体修改都加了备注。我回答问题不是为了币。主要是兴趣爱好。顺便蹭点积分好早日到鱼油I。新鱼油限制太多了。。
像你这种经常语法错误的我建议用geany。虽然错误显示是英文的,但是我觉得这是最好用的了。问题描述比较具体。从你编写代码的用词来看,你的英文应该不差。所以用geany搓搓有余。- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 11
- char pmid[N] = {'A','C','B','G','E','A','H','F','I','J','K'}; //中序序列 //定义char就不用typedef elemtype了吧。。
- char post[N] = {'A','C','E','G','B','F','H','K','J','I','A'}; //后序序列
- typedef struct BiTNode
- {
- char data;
- struct BiTNode *lchild, *rchild;
- } BiTNode, *BiTree;
- int FindPos(char x,char pmid[],int start) //从start处开始查找
- {
- int i;
- for(i = start;i >= 0;i--)
- {
- if(x == pmid[i])
- {
- printf("第%d次找到%s\n",11-i,pmid);
- return i; //返回中序根节点位置
- }
- else
- {
- printf("第%d次查找不到%c\n",11-i,x);
- }
- }
- return 0;
- }
- void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标,j为post[]中的尾字符下标,len为子树字符串长度
- {
- if (i<0||i>len)return; //递归最重要的是base case.就是如果某某为真,停止递归。否则程序会一直调用这个函数,直到爆炸。
- else if (j<0||j>len)return;//这是我猜的base case,对不对自己修改。
- int m;
- int leftlen,rightlen;
- if(len <= 0)
- {
- (*T) = NULL;
-
- }
- else
- {
- (*T) = (BiTree)malloc(sizeof(BiTree));
- (*T)->data = post[j];
- m = FindPos(post[j],pmid,j); // 小于m的是左孩子,大于m的是右孩子
- leftlen = m - i; //以m为根,左孩子的长度
- rightlen = len - leftlen -1;//以m为根,右孩子的长度
-
- CreatBiTree_pmid_post(&(*T)->lchild,i,j-1-rightlen,leftlen);
- CreatBiTree_pmid_post(&(*T)->rchild,m+1,j-1,len-leftlen-1);
- }
- }
- void visit(char c)
- {
- printf("%c", c);
- return;
- }
- void PreOrderTraverse(BiTree T)
- {
- if(!T)return;
- visit(T->data);
- PreOrderTraverse(T->lchild);
- PreOrderTraverse(T->rchild);
- }
- int main()
- {
- BiTree T;
- int s;
- printf("中序序列为:\n");
- for (int i=0;i<N;i++)printf("%c",pmid[i]);
-
- printf("\n");
- printf("后序序列为:\n");
- for (int i=0;i<N;i++)printf("%c",post[i]);
- printf("\n");
-
- s = strlen(pmid);
- CreatBiTree_pmid_post(&T,0,N-1,s);
- printf("创建后前序遍历为: ");
- // PreOrderTraverse(T); ///这个和你CreatBiTree_pmid_post函数一样,没有合适的Return条件,进入死循环。我不知道你的base case该是什么。
-
- return 0;
- }
复制代码 |
|