| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1348 人关注过本帖
标题:二叉树建立问题,帮忙看看错误在哪里?
只看楼主 加入收藏
xichong
Rank: 7Rank: 7Rank: 7
来 自:四川南充
等 级:黑侠
威 望:2
帖 子:146
专家分:582
注 册:2009-6-10
收藏
得分:0 
哪位高手再帮我看一下怎么改?
2010-06-07 16:30
xichong
Rank: 7Rank: 7Rank: 7
来 自:四川南充
等 级:黑侠
威 望:2
帖 子:146
专家分:582
注 册:2009-6-10
收藏
得分:0 
程序代码:
#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环境下运行通过,供大家参考!

2010-07-02 22:39
快速回复:二叉树建立问题,帮忙看看错误在哪里?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021439 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved