threadingtree.c

来自「这是我的一些数据结构(C语言)源代码 比如LinkList」· C语言 代码 · 共 53 行

/*------------- 二叉树的二叉线索存储表示------------*/
typedef enum PointerTag{ Link, Thread };
typedef int TElemType;
typedef struct BiThrNode{
    TElemType   data;
    struct BiThrNode *lchild, *rchild;  /*左右孩子*/ 
    PointerTag     LTag, RTag;    /*左右标志*/ 
}BiThrNode, *BiThrTree;

/*------------------基本操作的实现-----------------*/   
void InOrder_Thr(BiThrTree T, void (* Visit)(TElemType e) ){
    BiThrTree p = T->lchild;
    while(p != T){
        while(p->LTag == Link)  p = p->lchild;
        Visit(p->data);
        while(p->RTag == Thread && p->rchild != T){
            p = p->rchild;
            Visit(p->data);
        }
        p = p->rchild;
    }
}

void InOrderThreading(BiThrTree *Thrt, BiThrTree T){
    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->rchild = Thrt; pre->RTag = Thread;
        Thrt->rchild = pre;
    }
}
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;
        InThreading(p->rchild);
    }
}