中序线索二叉树的构建与遍历

Question

设二叉树的结点的数据域的类型为char，请完成：

(1) 根据带空的先缀串建立一棵二叉树T

(2) 构建T的中序线索二叉树Thrt

(3) 基于Thrt实现T的中序遍历，并输出遍历结果

(4) 输出Thrt中一度结点的数量

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int sum=0;
typedef struct Bitree
{
    char data;
    struct Bitree *lchild,*rchild;
    int LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre=NULL;

void CreatBitree(BiThrTree &T)//生成二叉树
{
    char ch;
    scanf("%c",&ch);
    if(ch!='#')
    {
        T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!T)
            exit(1);
        T->data=ch;
        T->lchild=NULL;
        T->rchild=NULL;
        T->LTag=0;
        T->RTag=0;
        CreatBitree(T->lchild);
        CreatBitree(T->rchild);
    }else
    {
        T=NULL;
    }
}
void InThreaning(BiThrTree p)//中序线索化对每个节点的处理
{
    if(p!=NULL)
    {
        InThreaning(p->lchild);
        if(p->lchild==NULL)
        {
            p->LTag=1;
            p->lchild=pre;
        }
        if(!pre!=NULL&&pre->rchild==NULL)
        {
            pre->RTag=1;
            pre->rchild=p;
        }
        pre=p;
        InThreaning(p->rchild);
        return ;
    }
}
int InOrderThreading(BiThrTree &Thrt, BiThrTree T)//中序线索化二叉树
{
    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt)
        exit(1);
    Thrt->LTag=0;
    Thrt->RTag=1;
    T->rchild=Thrt;
    if(T==NULL)
        Thrt->lchild=Thrt;
    else{
        Thrt->lchild=T;
        pre=Thrt;
        InThreaning(T);
        pre->rchild=Thrt;
        pre->RTag=1;
        Thrt->rchild=pre;
    }
    return 0;
}

int InOrderTraverse_Thr(BiThrTree T)//中序遍历线索二叉树
{
    BiThrTree p=T->lchild;
    while(p!=T)
    {
        while(p->LTag==0)
            p=p->lchild;
        if((!p->lchild)&&(p->rchild))
            sum++;
        if((p->lchild)&&(!p->rchild))
            sum++;
        printf("%c",p->data);
        while(p->RTag==1&&p->rchild!=T)
        {
            p=p->rchild;
            printf("%c",p->data);
            if((!p->lchild)&&(p->rchild))
                sum++;
            if((p->lchild)&&(!p->rchild))
                sum++;
        }
        p=p->rchild;
    }
    return 0;
}

int main()
{
    BiThrTree T;
    CreatBitree(T);
    BiThrTree Thrt;
    InOrderThreading(Thrt,T);
    InOrderTraverse_Thr(Thrt);
    printf("\n");
    printf("%d",sum);
}

程序总是崩溃，OJ上面显示runtime error

Answer 1

【以下回答由 GPT 生成】

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int sum = 0;

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

BiThrTree pre = NULL;

void CreatBitree(BiThrTree &T) // 创建二叉树
{
    char ch;
    scanf("%c", &ch);

    if (ch != '#')
    {
        T = (BiThrNode*)malloc(sizeof(BiThrNode));
        if (!T)
            exit(1);
        T->data = ch;
        T->lchild = NULL;
        T->rchild = NULL;
        T->LTag = 0;
        T->RTag = 0;
        CreatBitree(T->lchild);
        CreatBitree(T->rchild);
    }
    else
    {
        T = NULL;
    }
}

void InThreaning(BiThrTree p) // 中序线索化
{
    if (p != NULL)
    {
        InThreaning(p->lchild);

        if (p->lchild == NULL)
        {
            p->LTag = 1;
            p->lchild = pre;
        }

        if (!pre != NULL && pre->rchild == NULL)
        {
            pre->RTag = 1;
            pre->rchild = p;
        }

        pre = p;
        InThreaning(p->rchild);

        return;
    }
}

int InOrderThreading(BiThrTree &Thrt, BiThrTree T) // 构建中序线索二叉树
{
    Thrt = (BiThrTree)malloc(sizeof(BiThrNode));
    if (!Thrt)
        exit(1);

    Thrt->LTag = 0;
    Thrt->RTag = 1;
    T->rchild = Thrt;

    if (T == NULL)
        T->lchild = Thrt;
    else
    {
        T->lchild = T;
        pre = Thrt;
        InThreaning(T);
        pre->rchild = Thrt;
        pre->RTag = 1;
    }

    return 0;
}

void InOrderTraversal(BiThrTree Thrt) // 中序遍历线索二叉树
{
    BiThrTree p = Thrt->lchild;

    while (p != Thrt)
    {
        while (p->LTag == 0)
        {
            p = p->lchild;
        }
        printf("%c ", p->data);

        while (p->RTag == 1 && p->rchild != Thrt)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        p = p->rchild;
    }
}

int CountOneDegreeNodes(BiThrTree Thrt) // 统计一度结点数量
{
    BiThrTree p = Thrt->lchild;
    int count = 0;

    while (p != Thrt)
    {
        if ((p->LTag == 1 && p->lchild == NULL) || (p->RTag == 1 && p->rchild == NULL))
            count++;
        p = p->rchild;
    }

    return count;
}

int main()
{
    BiThrTree T, Thrt;
    printf("请输入先序串创建二叉树（用#表示空节点）：\n");
    CreatBitree(T);
    printf("先序串创建的二叉树已创建完成！\n");

    printf("开始构建中序线索二叉树...\n");
    InOrderThreading(Thrt, T);
    printf("中序线索二叉树构建已完成！\n");

    printf("中序遍历结果为：\n");
    InOrderTraversal(Thrt);

    int count = CountOneDegreeNodes(Thrt);
    printf("一度结点的数量为：%d\n", count);

    return 0;
}

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^