线索二叉树的线索化,为什么函数正确答案不正确求改正。

2025-05-21 10:50:01
推荐回答(1个)
回答1:

测试结果:

创建二叉树,输入先序扩展序列:ABC##DE#G##F###
中序(递归法):C B E G D F A [用于对比测试]
中序(线索化):C B E G D F A

          A
        /  \
       B    #
    /    \    
   C      D 
  / \   /   \
 #  #  E     F
      / \   / \
     #   G  #  #
        / \ 
       #   #

#include
#include
#define ERROR 0
#define OVERFLOW -2
#define OK 1
typedef char SElemType;
typedef enum PointerTag{Link,Thread};
typedef struct BiTNode
{
    SElemType data;
    struct BiTNode *lchild, *rchild;
    PointerTag LTag,RTag;
}BiTNode,*Bitree;

typedef int Status;
Bitree pre;

Status CreateBiTree(Bitree *T)
{
    char ch;
    scanf("%c",&ch);
    //原代码if(ch==' ') //也可以用空格表示空指针
    if(ch=='#')  //符号#表示空指针
    {
        (*T)=NULL;
    }
    else
    {
        if(!((*T)=(Bitree)malloc(sizeof(BiTNode))))
            exit(OVERFLOW);
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
    return OK;
}

void InThreading(Bitree 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;
        InThreading(p->rchild);
    }
}

Status InOrderThreading(Bitree & Thrt,Bitree T)
{
    if(!(Thrt=(Bitree)malloc(sizeof(BiTNode))))
        exit(OVERFLOW);
    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;
    }
    return OK;
}

Status InOrderTraverse_Thr(Bitree T)
{
    Bitree p;
    p=T->lchild;
    while(p!=T)
    {
        while(p->LTag==Link)
            p=p->lchild;
        printf("%c ", p->data);
        while(p->RTag==Thread&&p->rchild!=T)
        {
            p=p->rchild;
            printf("%c ", p->data);
        }
        p=p->rchild;
    }
    return OK;
}

void inOrder(Bitree T)
{
    if(T!=NULL)
    {
        inOrder(T->lchild);
        printf("%c ",T->data);
        inOrder(T->rchild);
    }
}

int main()
{
    Bitree T;
    Bitree temp;

    CreateBiTree(&T);

    printf("中序(递归法):");
    inOrder(T);
    printf("\n");

    InOrderThreading(temp,T);

    //原代码InOrderTraverse_Thr( T);

    printf("中序(线索化):");
    InOrderTraverse_Thr(temp); //将输入参数 T 改为 temp
    printf("\n");

    return 0;
}