[数据结构与算法]数据结构---线索二叉树

//
//   线索二叉树
//

# include<math.h>
# include<iostream>
# include<stdio.h>
using namespace std;

int num[30] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};
int i = 0;


typedef int Elemtype;

typedef struct ThreadTNode{     //链式存储结构
    Elemtype data;
    struct ThreadTNode *lchild,*rchild;
    int ltag = 0,rtag = 0;
}ThreadTNode,*ThreadTree;

ThreadTNode *pre = NULL;


void printNode(ThreadTNode *p){
    printf("%d   ",p->data);
}


//找中序前驱节点
ThreadTNode *find_LastInNode(ThreadTNode *p){    //找到以p为跟的子树中最后一个被中序遍历的点
    while (p->rtag==0)       //最后先被访问的节点没有右孩子，所以ltag=1
        p = p->rchild;        //这个不是正常的中序遍历，而是直接从右孩子那里去找
    return p;
}

ThreadTNode *find_PreInNode(ThreadTNode *p){    //找到p的前驱
    if(p->ltag == 0)    //如果p没有被线索化(即p有左孩子)
        return find_LastInNode(p->lchild);     //前驱就是左子树最后一个被访问的节点
    else if(p->ltag == 1)     //如果p被线索化，前驱就是左孩子
        return p->lchild;
}

void RevInOrder(ThreadTree T){    //这样就可以逆中序遍历二叉树
    for(ThreadTNode *p = find_LastInNode(T);p!=NULL;p=find_PreInNode(p)){
        printNode(p);
    }
}




//找中序后继节点
ThreadTNode *find_FirstInThread(ThreadTNode *p){
    while(p->ltag == 0)
        p = p->lchild;
    return p;
}

ThreadTNode *find_NextInNode(ThreadTNode *p){   //找p的后继节点
    if(p->rtag==0)
        return find_FirstInThread(p->rchild);     //如果p没有被线索化，那就是右子树第一个被访问的节点
    else if(p->rtag==1)
        return p->rchild;
}

void InOder(ThreadTree T){   //非递归中序遍历
    for(ThreadTNode *p = find_FirstInThread(T);p!=NULL;p = find_NextInNode(p))
        printNode(p);
}


//先序遍历找前驱困难，后序遍历找后继节点困难



void inThread(ThreadTree &p){      //一边遍历一边线索化
    if(p!=NULL){
        inThread(p->lchild);    //中间这一段相当于visit()

        if(p->lchild==NULL){     //左孩子为空，建立前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre!=NULL && pre->rchild==NULL){    //建立这个节点的前驱节点没有右孩子（该改方向了）(没有直接后继)
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;

        printf("%d  ",p->data);

        inThread(p->rchild);
    }
}

void preThread(ThreadTree &p){      //一边遍历一边线索化
    if(p!=NULL){
            //中间这一段相当于visit()

        if(p->lchild==NULL){     //左孩子为空，建立前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre!=NULL && pre->rchild==NULL){    //建立这个节点的前驱节点没有右孩子（该改方向了）
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;

        if(p->ltag==0)               //防止转圈
            preThread(p->lchild);

        preThread(p->rchild);
    }
}

void postThread(ThreadTree &p){      //一边遍历一边线索化
    if(p!=NULL){
        postThread(p->lchild);

        postThread(p->rchild);    //后序遍历不会出现这样的问题

        if(p->lchild==NULL){     //左孩子为空，建立前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre!=NULL && pre->rchild==NULL){    //建立这个节点的前驱节点没有右孩子（该改方向了）
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;


    }
}



void visit(ThreadTree &T){
    if(T->lchild==NULL){
        T->lchild = pre;
        T->ltag = 1;
    }

    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild = T;
        pre->rtag = 1;
    }

    pre = T;

    printf("%d  ",T->data);
}

void preOrder(ThreadTree &T){
    if(T!=NULL){
        visit(T);
        if(T->ltag==0)        //如果左孩子已经被线索化，那么它指向的就是前驱，遍历的时候又回去了
            preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

void inOrder(ThreadTree &T){
    if(T!=NULL){
        inOrder(T->lchild);
        visit(T);
        inOrder(T->rchild);
    }
}

void postOrder(ThreadTree &T){
    if(T!=NULL){
        postOrder(T->lchild);
        postOrder(T->rchild);
        visit(T);
    }
}

void buildTree(ThreadTree &T){
    int el;
    el = num[i];i++;
//    scanf("%d",&el);
    if(el==0)
        T=NULL;
    else{
        T = (ThreadTNode *)malloc(sizeof(ThreadTNode));
        T->data = el;
        T->ltag = 0;
        T->rtag = 0;
        buildTree(T->lchild);
        buildTree(T->rchild);
    }

}

void createinThread1(ThreadTree &T){     //一边遍历一边线索化
    pre = NULL;

    if(T!=NULL){
        inOrder(T);
//        inThread(T);
        if(pre->rchild == NULL)     //这里也不用判断，最后一个节点的右孩子肯定是NULL
            pre->rtag = 1;          //处理遍历的最后一个节点
    }
}

void createinThread2(ThreadTree &T){     //一边遍历一边线索化
    pre = NULL;

    if(T!=NULL){
//        inOrder(T);
        inThread(T);
        if(pre->rchild == NULL)     //这里也不用判断，最后一个节点的右孩子肯定是NULL
            pre->rtag = 1;          //处理遍历的最后一个节点
    }
}



int main(void){
    ThreadTree T1;
    T1 = NULL;

    buildTree(T1);
//    createinThread1(T1);     //方法一
    createinThread2(T1);    //方法二
    printf("\n\n\n");
    RevInOrder(T1);
    printf("\n\n\n");
    InOder(T1);


    return 0;
}

最后用逆序和非递归可以进行验证.