线索二叉树

/* ******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 树
/* 文件名      : biThrTree.cpp
/* 功能描述    : 线索二叉树的表示与实现
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : 输入示例与输出结果
/* 
/* e.g. input  : ABD###CE#F###
/* bi-tree     :
/*                 A
/*                / \
/*               B   C
/*              /   /
/*             D   E
/*                  \
/*                   F
/* 
/* inorder thread traverse: D B A E F C
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
****************************************************************************** */
#include  < stdio.h >
#include  < stdlib.h >

/* *****************************************************************************
/* 数据类型和常量定义
/***************************************************************************** */
#define  OK           1
#define  ERROR        0
#define  OVERFLOW    -2

typedef  int  Status;
typedef  int  TElemType;

/*  二叉树的二叉线索存储表示  */
typedef  enum  PointerTag { Link, Thread };  /*  Link==0: 指针, Thread==1: 线索  */


/* *****************************************************************************
/* 数据结构定义
/***************************************************************************** */
typedef  struct  BiThrNode {
    TElemType data;
     struct  BiThrNode  * lchild,  * rchild;  /*  左右孩子指针  */
    PointerTag LTag, RTag;              /*  左右标志  */
} BiThrNode,  * BiThrTree;


/* *****************************************************************************
/* 全局变量声明
/***************************************************************************** */
static  BiThrNode  * pre  =  NULL;  // 保存线索化过程中的前驱结点


/* *****************************************************************************
/* 函数原型声明
/***************************************************************************** */
void  InThreading(BiThrTree p);


/* ******************************************************************************
/* <FUNC>
/* 函数名   : Visit
/* 功能     : 打印节点数据
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Visit(TElemType e)
{
    printf( " %c " , e);
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : InOrderTraverse_Thr
/* 功能     : 中序遍历二叉线索树
/* 参数     : -
/* 返回值   : -
/* 备注     : 中序遍历二叉线索树T的非递归算法, T指向头结点, 头结点的左链lchild指向根结点
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status InOrderTraverse_Thr(BiThrTree T, Status ( * Visit)(TElemType e)) {
    BiThrNode  * p  =  T -> lchild;           // p指向根结点
     while  (p  !=  T) {                    // 空树或遍历结束时, p==T
         while  (p -> LTag  ==  Link) p  =  p -> lchild;
         if  ( ! Visit(p -> data))  return  ERROR;  // 访问其左子树为空的结点
         while  (p -> RTag  ==  Thread  &&  p -> rchild  !=  T) {
            p  =  p -> rchild; Visit(p -> data);   // 访问后续结点
        }
        p  =  p -> rchild;
    }
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : InOrderThreading
/* 功能     : 中序线索化二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 中序遍历二叉树T, 并将其中序线索化, Thrt指向头结点
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status InOrderThreading(BiThrTree  & Thrt, BiThrTree T) {
     if  ( ! (Thrt  =  (BiThrTree)malloc( sizeof (BiThrNode)))) 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;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : InThreading
/* 功能     : 中序线索化
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
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);   // 右子树线索化
    }
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : CreateBiTree
/* 功能     : 创建二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 前序方式创建
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status CreateBiTree(BiThrTree  & T)
{
     char  ch  =  getchar();
     if ( ' # '   ==  ch) T  =  NULL;
     else  {
         if ( ! (T  =  (BiThrNode  * )malloc( sizeof (BiThrNode)))) exit(OVERFLOW);
        T -> data  =  ch;              // 生成根结点
        T -> LTag  =  Link;
        T -> RTag  =  Link;
        CreateBiTree(T -> lchild);   // 构造左子树
        CreateBiTree(T -> rchild);   // 构造右子树
    }
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : main
/* 功能     : 测试函数
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
void  main()
{
    BiThrTree ThrT  =  NULL;    BiThrTree T  =  NULL;
    CreateBiTree(T);

     // 中序遍历二叉树并线索化
     if  (OK  ==  InOrderThreading(ThrT, T)) printf( " InOrder Threading Finished!\n " );

     // 中序遍历线索二叉树
    printf( " InOrder Thread Traverse:  " );
    InOrderTraverse_Thr(ThrT, Visit);

    printf( " \n " );
}