www.pudn.com > datastructor.rar > ThreadingTree.c

/*------------- 二叉树的二叉线索存储表示------------*/ 
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); 
    } 
}