标题:帮帮忙啊,线索二叉树的中序线索化及其遍历,为什么不能正常运行?(运行环 ...
只看楼主
xichong
Rank: 7Rank: 7Rank: 7
来 自:四川南充
等 级:黑侠
威 望:2
帖 子:146
专家分:582
注 册:2009-6-10
结帖率:100%
已结贴  问题点数:40 回复次数:2 
帮帮忙啊,线索二叉树的中序线索化及其遍历,为什么不能正常运行?(运行环境VC++6.0)
#include <stdio.h>//测试值:abc@@de@g@@f@@@
#include <stdlib.h>
#define Link 0
#define Thread 1
typedef char TElemType;
typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    int LTag,RTag;
}BiThrNode,*BiThrTree;
////////
BiThrTree pre;//全局变量
////////
BiThrTree CreatBiThrTree()//先序创建二叉树
{
    TElemType ch;
    BiThrTree T;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!T)
            exit(0);
        T->data=ch;
        T->lchild=CreatBiThrTree();
        T->rchild=CreatBiThrTree();
    }
    return T;
}

void InThreading(BiThrTree p)//中序遍历二叉树
{
    if(p)
    {
        InThreading(p->lchild);//左子树线索化
        if(!p->lchild)//前驱线索
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if(!pre->rchild)//后继线索
        {
            pre->RTag=Thread;
            pre->rchild=p;
        }
        pre=p;//保持pre指向p的前驱
        InThreading(p->rchild);//右子树线索化
    }
}
void InOrderThreading(BiThrTree Thrt,BiThrTree T)//中序线索化二叉树
{
    if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))));
    exit(0);
    Thrt->LTag=Link;
    Thrt->RTag=Thread;
    Thrt->rchild=Thrt;
    if(!T)
        Thrt->lchild=Thrt;
    else
    {
        Thrt->lchild=T;
        pre=Thrt;
        InThreading(T);//中序遍历进行中序线索化
        pre->rchild=Thrt;//最后一个结点线索化
        pre->RTag=Thread;
        Thrt->rchild=pre;
    }
}
void Visit(char c)
{
    printf("%c",c);
}
void InorderTraverse_Thr(BiThrTree T)//中序遍历二叉树
{
    BiThrTree p;
    p=T->lchild;
    while(p!=T)//空树或遍历结束时,p=T
    {
        while(p->LTag==Link)
            p=p->lchild;
        Visit(p->data);//访问左子树为空的结点
        while(p->RTag==Thread&&p->lchild!=T)//访问后继结点
        {
            p=p->rchild;
            Visit(p->data);
        }
        p=p->rchild;
    }
}
void main()
{
    BiThrTree t;
    BiThrNode thrtnode;
    printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n");
    printf("<说明:例如参考数据为:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n");
    t=CreatBiThrTree();
    printf("中序线索化二叉树:\n");
    InOrderThreading(&thrtnode,t);
    printf("线索化工作已经完成!\n");
    printf("中序遍历线索二叉树:\n");
    InorderTraverse_Thr(&thrtnode);
}
搜索更多相关主题的帖子: 二叉树 遍历 线索 环境 运行 
2010-05-06 09:46
hzh512
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:6
帖 子:234
专家分:1333
注 册:2009-6-5
得分:40 
有4个错误,有两个非常低级的错误。非常不应该发生!
1. if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))));
    exit(0);   
2. while(p->RTag==Thread&&p->lchild!=T)//访问后继结点  抄书都抄错了,太不应该了!
3. 线索初始化。T->LTag=Link; T->RTag=Link;
4. 指针错误。你要注意,书上的是引用,而你用C,所以要使用二级指针。

下面是已改错的源码:
程序代码:
#include <stdio.h>//测试值:abc@@de@g@@f@@@
#include <stdlib.h>
#define Link 0
#define Thread 1
typedef char TElemType;
typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    int LTag,RTag;
}BiThrNode,*BiThrTree;
////////
BiThrTree pre;//全局变量
////////
BiThrTree CreatBiThrTree();//先序创建二叉树
void InThreading(BiThrTree p);//中序遍历二叉树
void InOrderThreading(BiThrTree *Thrt,BiThrTree T);//中序线索化二叉树
void Visit(char c);
void InorderTraverse_Thr(BiThrTree T);//中序遍历二叉树
void main()
{
    BiThrTree t;
    BiThrTree thrtnode=NULL;
    printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n");
    printf("<说明:例如参考数据为:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n");
    t=CreatBiThrTree();
    printf("中序线索化二叉树:\n");
    InOrderThreading(&thrtnode,t);
    printf("线索化工作已经完成!\n");
    printf("中序遍历线索二叉树:\n");
    InorderTraverse_Thr(thrtnode);
}

BiThrTree CreatBiThrTree()//先序创建二叉树
{
    TElemType ch;
    BiThrTree T;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!T)
            exit(0);
        T->data=ch;
        T->LTag=Link;
        T->RTag=Link;
        T->lchild=CreatBiThrTree();
        T->rchild=CreatBiThrTree();
    }
    return T;
}
void InThreading(BiThrTree p)//中序遍历二叉树
{
    if(p)
    {
        InThreading(p->lchild);//左子树线索化
        if(!p->lchild)//前驱线索
        {
            p->LTag=Thread;
            p->lchild=pre;
        }
        if(!pre->rchild)//后继线索
        {
            pre->RTag=Thread;
            pre->rchild=p;
        }
        pre=p;//保持pre指向p的前驱
        InThreading(p->rchild);//右子树线索化
    }
}
void InOrderThreading(BiThrTree *Thrt,BiThrTree T)//中序线索化二叉树
{
    if(!((*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode))))
  exit(0);
    (*Thrt)->LTag=Link;
    (*Thrt)->RTag=Thread;
    (*Thrt)->rchild=(*Thrt);
    if(!T)
        (*Thrt)->lchild=(*Thrt);
    else
    {
        (*Thrt)->lchild=T;
        pre=(*Thrt);
        InThreading(T);//中序遍历进行中序线索化
        pre->rchild=(*Thrt);//最后一个结点线索化
        pre->RTag=Thread;
        (*Thrt)->rchild=pre;
    }
}
void Visit(char c)
{
    printf(" %c ",c);
}
void InorderTraverse_Thr(BiThrTree T)//中序遍历二叉树
{
    BiThrTree p;
    p=T->lchild;
    while(p!=T)//空树或遍历结束时,p=T
    {
        while(p->LTag==Link)
            p=p->lchild;
        Visit(p->data);//访问左子树为空的结点
        while(p->RTag==Thread&&p->rchild!=T)//访问后继结点
        {
            p=p->rchild;
            Visit(p->data);
        }
        p=p->rchild;
    }
}


编程=用几种语言在某个或几个平台上通过抽象思维运用一系列算法来解决现实中问题的手段
2010-05-06 15:04
xichong
Rank: 7Rank: 7Rank: 7
来 自:四川南充
等 级:黑侠
威 望:2
帖 子:146
专家分:582
注 册:2009-6-10
得分:0 
谢谢了!
2010-05-06 20:38



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-305558-1-1.html




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

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