Manchester- 数据结构-线索二叉树

解题思路:
第一次写线索二叉树，根据一般二叉树的知识，和题目提示代码，以及课本代码凑出来了这个程序，

接下来就讲一讲什么如何修改课本代码，需要添加什么，才能使程序运行

①：

void InOrderThreading(Bithrtree *Thrt,Bithrtree T);/*中序遍历二叉树，并将其线索化*/
/*这个函数中pre需要自己定义*/
/*其中的Link，与Thread相当于全局变量分别等于0,1*/
/*Thrt为指向头结点指针的指针*/
/*T是首结点*/

②

void InThreading(Bithrtree T,Bithrtree *pre);
/*这个函数得要自己编写，在课本135页，需要注意的是，pre指针在这个函数里面也要用，所以与书上相比
要多加一个Bithrtree *pre，（书上的pre应该是全局变量）其作用是记录前驱，然后在 InOrderThreading这个函数中使用*/

注意事项:
不可以照着题目以及课本抄下来，课本上为了方便不全；

参考代码:

#include <stdio.h>
#include <malloc.h>

#define Link    0
#define Thread    1
#define MAX    101

typedef struct BithrNode_ {
    char            data;
    struct BithrNode_    *Lchild, *Rchild;
    int            LTag, RTag;
}*Bithrtree, BithrNode;


void CreatBitree( Bithrtree *T );                       /*创建二叉树*/

void InOrderThreading( Bithrtree *Thrt, Bithrtree T );  /*中序遍历二叉树，并将其线索化*/

void InThreading( Bithrtree T, Bithrtree *pre );

void InorderTraverse_Thr( Bithrtree T );                /*中序遍历算法*/


/*-----------------------------------------------------------------*/
int main()
{
    Bithrtree T, Thrt;

    CreatBitree( &T );

    InOrderThreading( &Thrt, T );

    InorderTraverse_Thr( Thrt );

    return(0);
}


/*-----------------------操作定义------------------------------------*/
void CreatBitree( Bithrtree *T ) /*创建二叉树*/
{
    char ch;
    scanf( "%c", &ch );
    if ( ch == ' ' )
        (*T) = NULL;
    else{
        (*T)        = (Bithrtree) malloc( sizeof(BithrNode) );
        (*T)->data    = ch;

        CreatBitree( &(*T)->Lchild );
        CreatBitree( &(*T)->Rchild );
    }
    return;
}


/*------------------------------------------------------------*/
void InOrderThreading( Bithrtree *Thrt, Bithrtree T )   /*中序遍历二叉树，并将其线索化*/
{
    Bithrtree pre = NULL;                           /*定义前驱指针*/
    (*Thrt) = (Bithrtree) malloc( sizeof(BithrNode) );


    (*Thrt)->LTag    = Link;                         /*建立头结点*/
    (*Thrt)->RTag    = Thread;
    (*Thrt)->Rchild = (*Thrt);                      /*右指针回指*/

    if ( !T )                                       /*若二叉树空，左指针回指*/
        (*Thrt)->Lchild = (*Thrt);
    else{
        (*Thrt)->Lchild = T;
        pre        = (*Thrt);
        InThreading( T, &pre );                 /*中序遍历，进行中序线索化*/
        pre->Rchild    = *Thrt;
        pre->RTag    = Thread;               /*最后一个结点线索化*/
        (*Thrt)->Rchild = pre;
    }
}


/*------------------------------------------------------------*/
void InThreading( Bithrtree T, Bithrtree *pre )
{
    if ( T )
    {
        InThreading( T->Lchild, pre );  /*左子树线索化*/
        if ( !T->Lchild )
        {
            T->LTag = Thread; T->Lchild = (*pre);
        }                               /* 前驱线索 */

        if ( !(*pre)->Rchild )
        {
            (*pre)->RTag = Thread; (*pre)->Rchild = T;
        }

        (*pre) = T;

        InThreading( T->Rchild, pre );  /*右子树线索化*/
    }
}


/*------------------------------------------------------------*/
void InorderTraverse_Thr( Bithrtree T )         /*中序遍历算法*/
{
    Bithrtree 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;
}

别忘点赞哦-.-