树-线索二叉树-白红宇

树-线索二叉树

阅读量：5025 次

发布时间：2019-06-12

本文共 3315 字，大约阅读时间需要 11 分钟。

/*树-线索二叉树LJK 2017-07-05*/#include
     
      #include
      
       #include
       
        #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef char TElemType;typedef int Status;/*Link  == 0 表示指向左右孩子的指针Thread == 1 表示指向前驱或后继的线索*/typedef enum {Link,Thread} PointerTag;// 二叉线索存储节点结构typedef struct biThrNode{    TElemType data;                            // 节点数据    struct  biThrNode *lchild, *rchild;     // 左右孩子指针    PointerTag LTag, RTag;                    // 左右标志}BiThrNode;int index = 0;char String[] = "ABDH##I##EJ###CF##G##";Status visit(TElemType e){    printf("%c", e);    return OK;}// 按前序输入二叉线索树中节点的值，构造二叉线索树Status CreateBiThrTree(BiThrNode **T){    TElemType ch;    ch = String[index++];    if (ch == '#')        *T = NULL;    else    {        *T = (BiThrNode*)malloc(sizeof(BiThrNode));        if (!(*T)) exit(OVERFLOW);        (*T)->data = ch;                // 生成根节点（前序）        CreateBiThrTree(&(*T)->lchild); // 构造左子树        if ((*T)->lchild)(*T)->LTag = Link;        CreateBiThrTree(&(*T)->rchild); // 构造右子树        if ((*T)->rchild) (*T)->RTag = Link;    }    return OK;}BiThrNode *pre;                         // 全局变量，始终指向刚刚访问过的节点/* 中序遍历进行中序线索化 */void InThreading(BiThrNode *p){    if (p)    {        InThreading(p->lchild);     // 递归左子树线索化        if (!p->lchild)                // 没有左孩子        {            p->LTag = Thread;        // 前驱线索            p->lchild = pre;        // 左孩子指针指向前驱        }        if (!p->rchild)                // 前驱没有右孩子        {            pre->RTag = Thread;        // 后继线索            pre->rchild = p;        // 前驱右孩子指针指向后继（当前节点p）        }        pre = p;                    // 保持pre指向p的前驱        InThreading(p->rchild);        // 递归右子树线索化    }}// 中序遍历二叉树T，并将其中序线索化，Thrt指向头节点Status InOrderThreading(BiThrNode **Thrt, BiThrNode *T){    *Thrt = (BiThrNode *)malloc(sizeof(BiThrNode)); // 建头节点    if (!(Thrt)) exit(OVERFLOW);    (*Thrt)->LTag = Link;    (*Thrt)->RTag = Thread;    (*Thrt)->rchild = *Thrt;                        // 右指针回指    if (!(T)) (*Thrt)->lchild = *Thrt;                // 若二叉树空，则左指针回指    else    {        (*Thrt)->lchild = T;        // 头节点左孩子指向根节点        pre = (*Thrt);                // pre指向头节点        InThreading(T);                // 中序遍历进行中序线索化        pre->RTag = Thread;        pre->rchild = *Thrt;        // 最后一个节点线索化，指向头节点        (*Thrt)->rchild = pre;        // 头节点线索化，指向最后一个节点    }    return OK;}// 中序遍历二叉线索树T(头节点)的非递归算法Status InOrderTraverse_Thr(biThrNode *T){    BiThrNode *p;    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;}int main(){    BiThrNode *t, *h;     PointerTag P;    printf("按前序输入二叉树（如：'ABDH##I##EJ###CF##G##'）\n");    CreateBiThrTree(&t);    // 中序遍历，并中序线索化二叉树    InOrderThreading(&h, t);    // 中序遍历（输出），二叉线索树    InOrderTraverse_Thr(h);    printf("\n");    getchar();    return 0;}