【概述】

在线索二叉树前驱结点与后继结点的查找中，介绍了在线索二叉树中前驱结点与后继结点的查找

下面首先对查找过程进行总结：

当给定结点 p 时，若 p->ltag = 1 或 p->rtag = 1，说明进行了线索化，可以通过 p->lchild 来访问 p 的前驱，通过 p->rchild 来访问 p 的后驱

而当 p->ltag = 1 或 p->rtag = 1，说明未进行线索化，查找前驱、后继结点过程可以总结为下表：

	前序线索二叉树	中序线索二叉树	后序线索二叉树
找前驱	需要三叉链表线索化	寻找最右下结点	依据右孩子是否存在判断
找后继	依据左孩子是否存在判断	寻找最左下结点	需要三叉链表线索化

在对线索二叉树进行遍历时，执行前/中/后序线索二叉树的遍历就相当于对二叉树进行前/中/后序遍历，只是正向遍历是通过寻找后继结点的方式来实现的，逆向遍历是通过寻找前驱结点的方式实现的

因此，在执行遍历前，需要先构建线索二叉树，然后再进行线索二叉树的遍历

此外，由于前序线索二叉树的找前驱与后序线索二叉树的找后继要由三叉链表来实现，因此不再给出前序线索二叉树的逆向前序遍历和后序线索二叉树的后序正向遍历

【访问函数】

在对线索二叉树遍历时，每访问一个结点可能要对该结点进行某些操作，为此，封装一访问函数 visit()，在实际问题中，根据需要来更改该函数即可

void visit(ThNode *p) { //访问函数
    if (p == NULL)
        printf("Null\n");
    else
        printf("%d\n", p->data);
}

【中序线索二叉树】

中序线索二叉树的正向遍历

前序线索二叉树的正向遍历即对二叉树进行正向中序遍历，从整棵二叉树的最左下方的结点开始，不断寻找后继结点进行输出即可

要求在遍历前先进行中序线索二叉树的构建，即调用 createInThreadTree() 函数，然后寻找到最左下方的结点，之后进行遍历

void inOrder(ThNode *p) { //中序线索二叉树的遍历
    while (p != NULL) {
        visit(p);
        p = findPostByInThreadTree(p); //寻找后继
    }
}
int main() {
    ThTree root;
    //build tree
    
    createInThreadTree(root); //创建中序线索二叉树
    ThNode *p = root;
    while (p->ltag == 0) //寻找以p为根的子树中，最左下结点
        p = p->lchild;
    inOrder(p); //中序遍历
    
    system("pause");
    return 0;
}

中序线索二叉树的逆向遍历

中序线索二叉树的逆向遍历即对二叉树进行逆向中序遍历，从整棵二叉树的最右下方的结点开始，不断寻找前驱结点进行输出即可

要求在遍历前先进行中序线索二叉树的构建，即调用 createInThreadTree() 函数，然后寻找到最右下方的结点，之后进行遍历

void revInOrder(ThNode *p) { //中序线索二叉树的逆向遍历
    while (p != NULL) {
        visit(p);
        p = findPreByInThreadTree(p); //寻找前驱
    }
}
int main() {
    ThTree root;
    //build tree
    
    createInThreadTree(root); //创建中序线索二叉树
    ThNode *p = root;
    while (p->rtag == 0) //寻找以p为根的子树中，最右下结点
        p = p->rchild;
    revInOrder(p); //逆向中序遍历
    
    system("pause");
    return 0;
}

【前序线索二叉树的正向遍历】

前序线索二叉树的正向遍历即对二叉树进行正向前序遍历，从根结点开始，不断寻找后继结点进行输出即可

要求在遍历前先进行前序线索二叉树的构建，即调用 createPreThreadTree() 函数，之后从根结点开始进行遍历

void preOrder(ThNode *p) { //前序线索二叉树的正向遍历
    while (p != NULL) {
        visit(p);
        p = findPostByPreThreadTree(p); //寻找后继
    }
}
int main() {
    ThTree root;
    //build tree
    
    createPreThreadTree(root); //创建前序线索二叉树
    preOrder(root); //前序遍历
    
    system("pause");
    return 0;
}

【后序线索二叉树的逆向遍历】

后序线索二叉树的逆向遍历即对二叉树进行逆向后序遍历，从根结点开始，不断寻找前驱结点进行输出即可

要求在遍历前先进行后序线索二叉树的构建，即调用 createPostThreadTree() 函数，之后从根结点开始进行遍历

void revPostOrder(ThNode *p) { //后序线索二叉树的逆向遍历
    ThNode *p = root;
    while (p != NULL) {
        visit(p);
        p = findPreByPostThreadTree(p); //寻找前驱
    }
}
int main() {
    ThTree root;
    //build tree
    
    createPostThreadTree(root); //创建后序线索二叉树
    revPostOrder(root); //逆向后序遍历
    
    system("pause");
    return 0;
}