由中序序列和后序序列建立一颗二叉树，出了问题
//已知中序序列和后序序列，建立一颗二叉树#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 11
typedef char ElemType;
ElemType pmid = {'D','C','B','G','E','A','H','F','I','J','K'}; //中序序列
ElemType post = {'D','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,j;
for(i = start;i >= 0;i--)
{
if(x == pmid)
{
printf("第%d次找到%c,i = %d\n",11-i,pmid,i);
return i; //返回中序根节点位置
}
else
{
printf("第%d次查找不到%c,i = %d\n",11-i,x,i);
}
}
return 0;
}
void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标，j为post[]中的尾字符下标，len为子树字符串长度
{
int m;
int leftlen,rightlen;
if(len <= 0)
{
(*T) = NULL;
}
else
{
(*T) = (BiTree)malloc(sizeof(BiTree));
(*T)->data = post;
m = FindPos(post,pmid,j); // 小于m的是左孩子，大于m的是右孩子
leftlen = m - i; //以m为根，左孩子的长度
rightlen = len - leftlen -1;//以m为根，右孩子的长度
CreatBiTree_pmid_post(&(*T)->lchild,i,j-1-leftlen,leftlen);
CreatBiTree_pmid_post(&(*T)->rchild,m+1,j-1,len-leftlen-1);
}
}
void visit(char c)
{
printf("%c", c);
}
void PreOrderTraverse(BiTree T)
{
if( T )
{
visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
int main()
{
BiTree T = NULL;
inti,j,s;
printf("中序序列为:\n");
for(i = 0;i<N;i++)
{
printf("%c",pmid);
}
printf("\n");
printf("后序序列为：\n");
for(j = 0;j<N;j++)
{
printf("%c",post);
}
printf("\n");
s = strlen(pmid);
CreatBiTree_pmid_post(&T,0,N-1,s);
printf("创建后前序遍历为： ");
PreOrderTraverse(T);
return 0;
}
递归建立左子树时没错，因为我的是 i--查找根结点，从后往前找，但是建立右子树时，后序序列中的E要与中序序列的E相匹配，但是 i=2时，i--找不到中序序列中的E,我觉得是递归右子树时出了问题，但我有点想不明白，希望有人能帮我解释完善代码。中序序列为：DCBGEAHFIJK
后序序列为： DCEGBFHKJIA
鱼币少了望海涵- -。。
//已知中序序列和后序序列，建立一颗二叉树
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 11
typedef char ElemType;
ElemType pmid = {'D','C','B','G','E','A','H','F','I','J','K'}; //中序序列
ElemType post = {'D','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[]) //从start处开始查找
{
int i;
for(i = 11;i >= 0;i--)
{
if(x == pmid)
{
return i; //返回中序根节点位置
}
}
return 0;
}
void CreatBiTree_pmid_post(BiTree *T,int i,int j,int len) //i为mid[]中的首字符下标，j为post[]中的尾字符下标，len为子树字符串长度
{
int m;
int leftlen,rightlen;
if(len <= 0)
{
(*T) = NULL;
}
else
{
(*T) = (BiTree)malloc(sizeof(BiTree));
(*T)->data = post;
m = FindPos(post,pmid);// 小于m的是左孩子，大于m的是右孩子
printf("根节点位于第%d个字符，元素为%c\n",m+1,pmid);
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,rightlen);
}
}
void exchange(BiTree T)
{
BiTree p;
if(T)
{
p = T->lchild;
T->lchild = T->rchild;
T->rchild = p;
exchange(T->lchild);
exchange(T->rchild);
}
}
void visit(char c)
{
printf("%c", c);
}
void PreOrderTraverse(BiTree T)
{
if( T )
{
visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
int main()
{
BiTree T = NULL;
inti,j,s;
printf("中序序列为:\n");
for(i = 0;i<N;i++)
{
printf("%c",pmid);
}
printf("\n");
printf("后序序列为：\n");
for(j = 0;j<N;j++)
{
printf("%c",post);
}
printf("\n");
s = strlen(pmid);
CreatBiTree_pmid_post(&T,0,N-1,s);
printf("创建后前序遍历为:\n");
PreOrderTraverse(T);
printf("\n");
exchange(T);
printf("交换后前序遍历为:\n");
PreOrderTraverse(T);;
printf("\n");
return 0;
}
自己改出来了 表示小宝路过，看不大懂，呵呵
页:
[1]