c語言實作線索二叉樹的建立，線索化以及周遊

結構與函數

typedef struct ThreadNode{
    Elemtype data;
    struct ThreadNode * lchild, * rchild;
    int ltag, rtag;
}ThreadNode, * ThreadTree;

ThreadTree InitThreadTree();
void InThread(ThreadTree p,ThreadTree pre);  //通過中序周遊對二叉樹線索化
void CreateInThread(ThreadTree T);  //通過中序周遊建立中序二叉樹

ThreadTree FirstNode(ThreadTree p); //求中序周遊下的第一個節點
ThreadTree NextNode(ThreadTree p);  //求節點p在中序序列下的後一個節點
void Visit(ThreadTree T);
void InOrder(ThreadTree T); //中序周遊
           

線索二叉樹的初始化

ThreadTree InitThreadTree(){
    char ch;
    ThreadTree T;
    scanf("%c", &ch);
    if(ch == '#') T = NULL;
    else{
        T = (ThreadTree)malloc(sizeof(ThreadNode));
        T->data = ch;
        T->lchild = InitThreadTree();
        T->rchild = InitThreadTree();
    }
    return T;
}
           

線索二叉樹的線索化

void InThread(ThreadTree p,ThreadTree pre){
    if(p != NULL){                   //p是目前節點，pre是剛通路的節點
        InThread(p->lchild, pre);    //遞歸，優化左子樹
        if(p->lchild == NULL){       //左子樹為空，建立前驅線索
            p->lchild = pre;
            p->ltag = ;
        }
        if(pre != NULL && pre->rchild == NULL){
            pre->rchild = p;          //右子樹為空，就建立前驅節點的後及線索
            pre->rtag = ;
        }
        pre = p;                      //p剛剛通路過了，則pre = p
        InThread(p->rchild, pre);     //遞歸，優化右子樹
    }
}

void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T != NULL){
        InThread(T, pre);
        pre->rchild = NULL;           //處理周遊的最後一個節點
        pre->rtag = ;
    }
}
           

線索二叉樹的周遊

ThreadTree FirstNode(ThreadTree p){
    while(p->ltag == ) p = p->lchild;  
    return p;
}

ThreadTree NextNode(ThreadTree p){
    if(p->rtag == ) return FirstNode(p->rchild);
                                      //有右節點，通路以右節點為根的樹的第一個節點
    else return p->rchild;            //rtag為1時候，rchild總是指向下一個
}

void Visit(ThreadTree T){
    printf("%c ", T->data);
}

void InOrder(ThreadTree T){
    for(ThreadTree p = FirstNode(T); p != NULL; p = NextNode(p))
        Visit(p);
}
           

firstnode是中序周遊下面的第一個通路的節點

nextnode是這個結點在中序周遊下面通路的下一個節點

如果有右子樹的連結，則下一個節點就是rchild

如果沒有，表示存在右子樹，由中序周遊的遞歸思想，下一個節點就相當于以這個結點的右節點為根節點在中序周遊下面的首節點

nextNode = firstNode(p->rchild);