各位高手帮忙改错。。 - 数据结构与算法

已结贴√ 问题点数：20 回复次数：9

各位高手帮忙改错。。

这个代码好像有问题。。执行一半会退出。。请问怎么改。。。。。

#include <iostream>

using namespace std;

enum PointerTag {Link, Thread};

typedef struct BiThrNode
{
    char data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;
BiThrTree T, pre = NULL;

void CreateBiTree(BiThrTree &T)
{
    //先序建立二叉树
    char ch;
    scanf("%c", &ch);
    if (ch == '*')
        T = NULL;
    else
    {
        if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode))))
            exit(-1);
        T->data = ch;
        T->LTag = Link;
        T->RTag = Link;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void PreThreading(BiThrTree P)
{
    //先序遍历线索化二叉树
    if (P)
    {
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
        if (P->LTag == Link)
            PreThreading(P->lchild);
        if (P->RTag == Link)
            PreThreading(P->rchild);
    }
}

void preOrderThr(BiThrTree T)
{
    //遍历先序线索二叉树
    BiThrTree p = T;
    printf("%c ", p->data);
    while (p->rchild)
    {
        if (p->LTag == Link)
            p = p->lchild;
        else
            p = p->rchild;
        printf("%c ", p->data);
    }
}

void InThreading(BiThrTree P)
{
    //中序遍历线索化二叉树
    if (P)
    {
        InThreading(P->lchild);
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
        InThreading(P->rchild);
    }
}

void inOrderThr(BiThrTree T)
{
    //遍历中序线索二叉树
    BiThrTree p = T;
    while (p->LTag == Link)
        p = p->lchild;
    printf("%c ", p->data);
    while (p->rchild)
    {
        if (p->RTag == Link)
        {
            p = p->rchild;
            while (p->LTag == Link)
                p = p->lchild;
        }
        else
            p = p->rchild;
        printf("%c ", p->data);
    }
}

void PostThreading(BiThrTree P)
{
    //后序遍历线索化二叉树
    if (P)
    {
        PostThreading(P->lchild);
        PostThreading(P->rchild);
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
    }
}

int main()
{
    //建立二叉树
    cout << "请按先序输入二叉树各元素值,"
         << "其中*代表空:\n";
    CreateBiTree(T);

    //先序遍历线索化二叉树
    cout << "先序遍历线索化二叉树:\n";
    PreThreading(T);
    cout << endl;

    //遍历先序线索二叉树
    cout << "遍历先序线索二叉树:\n";
    preOrderThr(T);
    cout << endl;

    //中序遍历线索化二叉树
    cout << "中序遍历线索化二叉树:\n";
    InThreading(T);
    cout << endl;

    //遍历中序线索二叉树
    cout << "遍历中序线索二叉树:\n";
    inOrderThr(T);
    cout << endl;

    //后序遍历线索化二叉树
    cout << "后序遍历线索化二叉树:\n";
    pre = NULL;
    PostThreading(T);
    cout << endl;

    return 0;
}

[ 本帖最后由 Vi_No 于 2010-4-27 22:02 编辑 ]

搜索更多相关主题的帖子: 改错　

第 2 楼

得分:0

弱弱地问一句。。为什么此贴被无视了。。。

第 3 楼

得分:0

提示: 作者被禁止或删除内容自动屏蔽

第 4 楼

得分:0

回复 3楼 LegendofMine

看出结果了么。

第 5 楼

得分:0

程序没有语法错误
但是要注意  BiThrTree T, pre = NULL 这是全局变量
  pre的值在每次用的时候要记得初始化为 0
  不要把T 声明成全局变量
因为后面的操作把它的值改变了因为是直接P = T 的   这样操作P 就等同于T

第 6 楼

得分:0

    char ch[5];
    scanf("%s", ch);
    //getchar();
    if (ch[0] == '*')
        T = NULL;
    else
    {
        if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode))))
            exit(-1);
        T->data = ch[0];
        T->LTag = Link;
        T->RTag = Link;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }

两种处理输入方法

第 7 楼

得分:0

回复 6楼寒风中的细雨

内个啥。。你5楼说的T不要设置成全局变量发贴之前我就试过的。而且pre的值每次都有改为NULL。输入处理应该没问题吧。

第 8 楼

得分:10

图片附件: 游客没有浏览图片的权限，请登录或注册

一次遍历没有问题
但是要进行后面就不行  因为 T 变了
指针型的设不设一样
#include <iostream>

using namespace std;

enum PointerTag {Link, Thread};

typedef struct BiThrNode
{
    char data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;

BiThrTree pre = NULL;

void CreateBiTree(BiThrTree &T)
{
    //先序建立二叉树
    char ch[5];
    scanf("%s", ch);
    //getchar();
    if (ch[0] == '*')
        T = NULL;
    else
    {
        if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode))))
            exit(-1);
        T->data = ch[0];
        T->LTag = Link;
        T->RTag = Link;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void copy(BiThrTree T, BiThrTree &temp)
{
    if(!T)
        temp = NULL;
    else
    {
        if(!(temp = (BiThrTree) malloc(sizeof(BiThrNode))) )
            exit(1);
        temp->data = T->data;
        temp->LTag = Link;
        temp->RTag = Link;
        copy(T->lchild, temp->lchild);
        copy(T->rchild, temp->rchild);
    }
}

void PreThreading(BiThrTree P)
{
    //先序遍历线索化二叉树
    if (P)
    {
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
        if (P->LTag == Link)
            PreThreading(P->lchild);
        if (P->RTag == Link)
            PreThreading(P->rchild);
    }
}

void preOrderThr(BiThrTree T)
{
    //遍历先序线索二叉树
    BiThrTree p = T;
    printf("%c ", p->data);
    while (p->rchild)
    {
        if (p->LTag == Link)
            p = p->lchild;
        else
            p = p->rchild;
        printf("%c ", p->data);
    }
}

void InThreading(BiThrTree P)
{
    //中序遍历线索化二叉树
    if (P)
    {
        InThreading(P->lchild);
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
        InThreading(P->rchild);
    }
}

void inOrderThr(BiThrTree T)
{
    //遍历中序线索二叉树
    BiThrTree p = T;
    while (p->LTag == Link)
        p = p->lchild;
    printf("%c ", p->data);
    while (p->rchild)
    {
        if (p->RTag == Link)
        {
            p = p->rchild;
            while (p->LTag == Link)
                p = p->lchild;
        }
        else
            p = p->rchild;
        printf("%c ", p->data);
    }
}

void PostThreading(BiThrTree P)
{
    //后序遍历线索化二叉树
    if (P)
    {
        PostThreading(P->lchild);
        PostThreading(P->rchild);
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
    }
}

int main()
{
    BiThrTree T=NULL, temp=NULL;

    //建立二叉树
    cout << "请按先序输入二叉树各元素值,"
         << "其中*代表空:\n";
    CreateBiTree(T);
    copy(T, temp);

    //先序遍历线索化二叉树
    cout << "先序遍历线索化二叉树:\n";
    PreThreading(temp);
    cout << endl;

    //遍历先序线索二叉树
    cout << "遍历先序线索二叉树:\n";
    preOrderThr(temp);
    cout << endl;

    free( temp );
    temp = NULL;
    copy( T, temp);

    //中序遍历线索化二叉树
    cout << "中序遍历线索化二叉树:\n";
    InThreading(T);
    cout << endl;

    //遍历中序线索二叉树
    cout << "遍历中序线索二叉树:\n";
    inOrderThr(T);
    cout << endl;

    free( temp );
    temp = NULL;
    copy( T, temp);

    //后序遍历线索化二叉树
    cout << "后序遍历线索化二叉树:\n";
    pre = NULL;
    PostThreading(T);
    cout << endl;

    return 0;
}

图片附件: 游客没有浏览图片的权限，请登录或注册

第 9 楼

得分:10

#include <iostream>

using namespace std;

enum PointerTag {Link, Thread};

typedef struct BiThrNode
{
    char data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;

BiThrTree pre = NULL;

void CreateBiTree(BiThrTree &T)
{
    //先序建立二叉树
    char ch[5];
    scanf("%s", ch);
    //getchar();
    if (ch[0] == '*')
        T = NULL;
    else
    {
        if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode))))
            exit(-1);
        T->data = ch[0];
        T->LTag = Link;
        T->RTag = Link;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void copy(BiThrTree T, BiThrTree &temp)
{
    if(!T)
        temp = NULL;
    else
    {
        if(!(temp = (BiThrTree) malloc(sizeof(BiThrNode))) )
            exit(1);
        temp->data = T->data;
        temp->LTag = Link;
        temp->RTag = Link;
        copy(T->lchild, temp->lchild);
        copy(T->rchild, temp->rchild);
    }
}

void PreThreading(BiThrTree P)
{
    //先序遍历线索化二叉树
    if (P)
    {
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
        if (P->LTag == Link)
            PreThreading(P->lchild);
        if (P->RTag == Link)
            PreThreading(P->rchild);
    }
}

void preOrderThr(BiThrTree T)
{
    //遍历先序线索二叉树
    BiThrTree p = T;
    printf("%c ", p->data);
    while (p->rchild)
    {
        if (p->LTag == Link)
            p = p->lchild;
        else
            p = p->rchild;
        printf("%c ", p->data);
    }
}

void InThreading(BiThrTree P)
{
    //中序遍历线索化二叉树
    if (P)
    {
        InThreading(P->lchild);
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
        InThreading(P->rchild);
    }
}

void inOrderThr(BiThrTree T)
{
    //遍历中序线索二叉树
    BiThrTree p = T;
    while (p->LTag == Link)
        p = p->lchild;
    printf("%c ", p->data);
    while (p->rchild)
    {
        if (p->RTag == Link)
        {
            p = p->rchild;
            while (p->LTag == Link)
                p = p->lchild;
        }
        else
            p = p->rchild;
        printf("%c ", p->data);
    }
}

void PostThreading(BiThrTree P)
{
    //后序遍历线索化二叉树
    if (P)
    {
        PostThreading(P->lchild);
        PostThreading(P->rchild);
        printf("%c ", P->data);
        if (!P->lchild)
        {
            P->LTag = Thread;
            P->lchild = pre;
        }
        if (!P->rchild)
            P->RTag = Thread;
        if (pre && pre->RTag == Thread)
            pre->rchild = P;
        pre = P;
    }
}

int main()
{
    BiThrTree T=NULL, temp=NULL;

    //建立二叉树
    cout << "请按先序输入二叉树各元素值,"
         << "其中*代表空:\n";
    CreateBiTree(T);
    copy(T, temp);

    //先序遍历线索化二叉树
    cout << "先序遍历线索化二叉树:\n";
    PreThreading(temp);
    cout << endl;

    //遍历先序线索二叉树
    cout << "遍历先序线索二叉树:\n";
    preOrderThr(temp);
    cout << endl;

    free( temp );
    temp = NULL;
    copy( T, temp);

    //中序遍历线索化二叉树
    cout << "中序遍历线索化二叉树:\n";
    InThreading(temp);
    cout << endl;

    //遍历中序线索二叉树
    cout << "遍历中序线索二叉树:\n";
    inOrderThr(temp);
    cout << endl;

    free( temp );
    temp = NULL;
    copy( T, temp);


    free( temp );
    temp = NULL;
    copy( T, temp);

    //后序遍历线索化二叉树
    cout << "后序遍历线索化二叉树:\n";
    //pre = NULL;
    PostThreading(temp);
    cout << endl;

    return 0;
}

图片附件: 游客没有浏览图片的权限，请登录或注册

第 10 楼

得分:0

回复 8楼寒风中的细雨

悲剧。其实出错的原因是知道的。当初急着交作业就把两个单纯的遍历函数改成遍历销毁二叉树了。完全没想到复制。还是版主的方法好。谢谢。