部分线索二叉树

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define SZ_STRING 1024

typedef char STRING[SZ_STRING];

/************************************begin线索二叉树定义区****************************/
/*Link == 0:指针，Thread == 1:线索*/
typedef enum
{
    Link,
    Thread
}PointerTag;
/*二叉树的二叉线索存储表示*/
/*线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。只能得到部分线索的链表！: 但是它占用的空间小*/
typedef struct binarythrnode
{
    STRING name; /*结点名称*/
    STRING value;     /*结点值*/
    PointerTag LTag, RTag; /*左右指针标志*/
    struct binarythrnode * leftchild;     /*左指针*/
    struct binarythrnode * rightchild;     /*右指针*/
}BINARYTHRNODE;

typedef BINARYTHRNODE * BinaryThrNodePtr;

int GetLeftRightchildLenByPreAndMid(char * cur_pre, char * cur_mid, int * leftlen, int * rightlen);
int CreateBinaryThrTreeByPreAndMid(BinaryThrNodePtr * root, char * cur_pre, char * cur_mid);

void PreThreading(BinaryThrNodePtr binarythrnodeptr, BinaryThrNodePtr * prenode);
void MidThreading(BinaryThrNodePtr binarythrnodeptr, BinaryThrNodePtr * prenode);
void PosThreading(BinaryThrNodePtr binarythrnodeptr, BinaryThrNodePtr * prenode);
int CreateBinaryTreeThreading(BinaryThrNodePtr * threadhead, BinaryThrNodePtr binarythrnodeptr, int type);

void PreOrderTraverseThr(BinaryThrNodePtr threadhead, char * pre);
void MidOrderTraverseThr(BinaryThrNodePtr threadhead, char * mid);
void PosOrderTraverseThr(BinaryThrNodePtr threadhead, char * pos);
BinaryThrNodePtr GetBinaryThrTreeParent(BinaryThrNodePtr threadhead, BinaryThrNodePtr binarythrnodeptr);

void PrintBinaryTreeNodeByPre(BinaryThrNodePtr binarythrnodeptr);
void PrintBinaryTreeNodeByMid(BinaryThrNodePtr binarythrnodeptr);
void PrintBinaryTreeNodeByPos(BinaryThrNodePtr binarythrnodeptr);
void PrintBinaryThrTreeNodeByPre(BinaryThrNodePtr threadhead);
void PrintBinaryThrTreeNodeByMid(BinaryThrNodePtr threadhead);
void PrintBinaryThrTreeNodeByPos(BinaryThrNodePtr threadhead);

/************************************end线索二叉树定义区****************************/



STRING data[26];

int main(int argc, char * * argv)
{
    freopen("threadtree.txt", "w", stdout);
    PointerTag flag1 = Link;
    PointerTag flag2 = Thread;
    printf("flag1=[%d], flag2=[%d]\n", Link, Thread);

    printf("二叉树的二叉线索存储结构！(只能得到部分线索的链表！)\n");

    int i;
    for(i=0; i<26; i++) /*所有的数据域赋初值*/
    {
        /*特点：data数组的每个元素都是STRING*/
        memset(data[i], 0, sizeof(STRING));
    }
    for(i=0; i<26; i++) /*给所有的数据域赋值*/
    {
        /*data数据域中的数据，即为26个字母的大写(65是A)*/
        memset(data[i], 65+i, sizeof(char)*3);
    }

    char pre[128]; /*前序序列*/
    char mid[128]; /*中序序列*/
    char pos[128]; /*后序序列*/
    char lev[128]; /*层次序列*/

    printf("******************************************begin第1颗二叉树*******************************************\n");

    memset(pre, 0, sizeof(pre));
    strcpy(pre, "ABDHIEJCFG");
    printf("前序序列=[%s]\n", pre);
    memset(mid, 0, sizeof(mid));
    strcpy(mid, "HDIBJEAFCG");
    printf("中序序列=[%s]\n", mid);

    printf("创建二叉线索存储结构的二叉树：\n");
    BinaryThrNodePtr rootthrnodeptr1 = NULL;
    CreateBinaryThrTreeByPreAndMid(&rootthrnodeptr1, pre, mid);
    printf("按照中序遍历序列,打印出整颗二叉树:\n");
    PrintBinaryTreeNodeByMid(rootthrnodeptr1);

    BinaryThrNodePtr threadhead = NULL; /*线索链表的头节点*/
    printf("中序线索化二叉树:\n");
    CreateBinaryTreeThreading(&threadhead, rootthrnodeptr1, 0); /*中序线索化二叉树*/
    printf("按照中序遍历序列,打印出整颗中序线索化二叉树:\n");
    PrintBinaryThrTreeNodeByMid(threadhead);
    memset(mid, 0, sizeof(mid));
    MidOrderTraverseThr(threadhead, mid);
    printf("中序线索化二叉树:中序遍历序列(非递归)........=[%s]\n", mid);

    printf("******************************************end第1颗二叉树*******************************************\n");

    printf("\n\n******************************************begin第2颗二叉树*******************************************\n");

    memset(pre, 0, sizeof(pre));
    strcpy(pre, "ABDHIEJCFG");
    printf("前序序列=[%s]\n", pre);
    memset(mid, 0, sizeof(mid));
    strcpy(mid, "HDIBJEAFCG");
    printf("中序序列=[%s]\n", mid);

    printf("创建二叉线索存储结构的二叉树：\n");
    BinaryThrNodePtr rootthrnodeptr2 = NULL;
    CreateBinaryThrTreeByPreAndMid(&rootthrnodeptr2, pre, mid);
    printf("按照先序遍历序列,打印出整颗二叉树:\n");
    PrintBinaryTreeNodeByPre(rootthrnodeptr2);

    printf("先序线索化二叉树:\n");
    CreateBinaryTreeThreading(&threadhead, rootthrnodeptr2, -1); /*先序线索化二叉树*/
    printf("按照先序遍历序列,打印出整颗先序线索化二叉树:\n");
    PrintBinaryThrTreeNodeByPre(threadhead);
    memset(pre, 0, sizeof(pre));
    printf("====================================\n");
    PreOrderTraverseThr(threadhead, pre);
    printf("====================================\n");
    printf("先序线索化二叉树:先序遍历序列(非递归)........=[%s]\n", pre);

    printf("******************************************end第2颗二叉树*******************************************\n");

    printf("\n\n******************************************begin第3颗二叉树*******************************************\n");

    memset(pre, 0, sizeof(pre));
    strcpy(pre, "ABDHIEJCFG");
    printf("前序序列=[%s]\n", pre);
    memset(mid, 0, sizeof(mid));
    strcpy(mid, "HDIBJEAFCG");
    printf("中序序列=[%s]\n", mid);

    printf("创建二叉线索存储结构的二叉树：\n");
    BinaryThrNodePtr rootthrnodeptr3 = NULL;
    CreateBinaryThrTreeByPreAndMid(&rootthrnodeptr3, pre, mid);
    printf("按照后序遍历序列,打印出整颗二叉树:\n");
    PrintBinaryTreeNodeByPos(rootthrnodeptr3);

    printf("后序线索化二叉树:\n");
    CreateBinaryTreeThreading(&threadhead, rootthrnodeptr3, 1); /*后序线索化二叉树*/
    printf("按照后序遍历序列,打印出整颗后序线索化二叉树:\n");
    PrintBinaryThrTreeNodeByPos(threadhead);
    memset(pos, 0, sizeof(pos));
    printf("====================================\n");
    PosOrderTraverseThr(threadhead, pos);
    printf("====================================\n");
    printf("后序线索化二叉树:后序遍历序列(非递归)........=[%s]\n", pos);

    printf("******************************************end第3颗二叉树*******************************************\n");

    return 0;
}

/*功能：层次线索化二叉树*/
/*功能：层次遍历线索化二叉树*/

/*功能：如何去线索化??*/

/*功能：求一个二叉树结点的双亲元素*/
BinaryThrNodePtr GetBinaryThrTreeParent(BinaryThrNodePtr threadhead, BinaryThrNodePtr binarythrnodeptr)
{
    BinaryThrNodePtr tempptr = NULL;
    tempptr = threadhead;
    if(tempptr->leftchild == binarythrnodeptr)
        return tempptr; /*父节点是头结点*/
    else
    {
        tempptr = tempptr->leftchild; /*tempptr指向头结点*/
        while((tempptr->leftchild != binarythrnodeptr) && (tempptr->rightchild != binarythrnodeptr))
        {
            if(Link==tempptr->RTag)
                tempptr = tempptr->rightchild; /*如果节点有右节点，那么往右*/
            else
                tempptr = tempptr->leftchild; /*如果节点没有右孩子，那么去左孩子，没有左孩子，去前驱，也是走往左*/
        }
        return tempptr;
    }
}

/*************************************************************************
 *函数名：PosOrderTraverseThr()
 *功能：遍历后序线索化二叉树(非递归)
 *输入参数：
 * threadhead ：线索二叉树的头结点
 *输出参数：
 * pos : 后序序列
 *返回值：空
 *特点：非递归遍历时，如果有线索链表是可以方便的实现遍历，可以不用栈了。
 *编程思想：
 *      遍历后序线索化二叉树与遍历先序中序索化二叉树编程思想很相似，但是要复杂一些：
**************************************************************************/
void PosOrderTraverseThr(BinaryThrNodePtr threadhead, char * pos)
{
    BinaryThrNodePtr p = NULL;
    BinaryThrNodePtr parentptr = NULL;
    p = threadhead->leftchild; /*p指向根结点*/

    /*从根开始：一直向左，走到最左下方*/
    while(p->LTag == Link)
    {
        p = p->leftchild; /*p指向第一个被访问的节点*/
    }

    while(p != threadhead)
    {
        /*printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);*/
        strncat(pos, p->name, sizeof(char)*1); /*得到后序序列*/
        parentptr = GetBinaryThrTreeParent(threadhead, p); /*parentptr是p的双亲*/

        if(parentptr == threadhead) /*p是根节点，整颗树就一个结点,没有左右孩子*/
        {
            break;
        }

        if(parentptr->RTag == Thread) /*parentptr没有右孩子*/
        {
            p = parentptr; /*根据(后序:左,右,根)p是左孩子,右孩子为空,可以开始遍历根结点了*/
        }
        else if(p == parentptr->rightchild) /*p是parentptr的右孩子*/
        {
            p = parentptr; /*根据(后序:左,右,根)p是右孩子,已访问,可以开始遍历根结点了*/
        }
        else if(p == parentptr->leftchild) /*p是parentptr的左孩子*/
        {
            if(parentptr->RTag == Link) /*parentptr有右孩子*/
            {
                parentptr = parentptr->rightchild; /*再把这个根的右孩子,当做根结点*/
                while(parentptr->LTag == Link) /*从根开始：一直向左，走到最左下方*/
                {
                    parentptr = parentptr->leftchild;
                }
            }
            p = parentptr;
        }
    }
}

/*************************************************************************
 *函数名：PreOrderTraverseThr()
 *功能：遍历先序线索化二叉树(非递归)
 *输入参数：
 * threadhead ：线索二叉树的头结点
 *输出参数：
 * pre : 先序序列
 *返回值：空
 *特点：非递归遍历时，如果有线索链表是可以方便的实现遍历，可以不用栈了。
**************************************************************************/
void PreOrderTraverseThr(BinaryThrNodePtr threadhead, char * pre)
{
    BinaryThrNodePtr p = NULL;
    p = threadhead->leftchild; /*p指向根结点*/
    while(p != threadhead) /*p指向线索链表头threadhead时：表示遍历结束*/
    {
        while(p->LTag == Link)
        {
            /*p指向的结点：有左子树，就可以访问了*/
            /*printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);*/
            strncat(pre, p->name, sizeof(char)*1); /*得到先序序列*/
            p = p->leftchild;
        }

        while(p->RTag == Thread) /*有后继结点，就一直向后找*/
        {
            /*p指向的结点：有后继结点，是可以直接访问的*/
            /*printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);*/
            strncat(pre, p->name, sizeof(char)*1); /*得到先序序列*/
            p = p->rightchild;
            if(p == threadhead) /*p指向线索头结点了，就可以跳出循环了*/
            {
                break;
            }
        }
    }
}

/*************************************************************************
 *函数名：MidOrderTraverseThr()
 *功能：遍历中序线索化二叉树(非递归)
 *输入参数：
 * threadhead ：线索二叉树的头结点
 *输出参数：
 * mid : 中序序列
 *返回值：空
 *特点：非递归遍历时，如果有线索链表是可以方便的实现遍历，可以不用栈了。
**************************************************************************/
void MidOrderTraverseThr(BinaryThrNodePtr threadhead, char * mid)
{
    BinaryThrNodePtr p = NULL;
    p = threadhead->leftchild; /*p指向根结点*/
    while(p != threadhead) /*p指向threadhead时：表示遍历结束*/
    {
        while(p->LTag == Link) /*结点指针走到最左下结点,就可以访问了*/
        {
            p = p->leftchild;
        }
        /*printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);*/
        strncat(mid, p->name, sizeof(char)*1); /*得到中序序列*/

        while((p->RTag == Thread)&&(p->rightchild != threadhead)) /*有后继结点，就一直向后找*/
        {
            p = p->rightchild; /*后继线索指针指向后继结点，是可以直接访问的*/
            /*printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);*/
            strncat(mid, p->name, sizeof(char)*1); /*得到中序序列*/
        }
        p = p->rightchild; /*没有后继了,就找右孩子结点,做右子树根结点*/
    }
}

/*************************************************************
 *函数名：PreThreading()
 *功能：前序线索化(只能部分线索)
 *前序线索化:是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照前序遍历的方法访问结点时建立线索。
 *输入参数：
 * root ：二叉树的根结点
 * prenode : 刚刚访问过的结点 ：即为当前访问结点的前驱
 *输出参数：
 * prenode ：
 *返回值：空
 *注意：第一次递归调用时，prenode指向线索链表的空头结点
 *线索化的实质：将二叉链表中的空指针改为指向前驱或后继的线索
 *线索化的过程：在遍历的过程中修改空指针的过程
**************************************************************/
void PreThreading(BinaryThrNodePtr binarythrnodeptr, BinaryThrNodePtr * prenode)
{
    if(binarythrnodeptr == NULL) /*加了线索之后，起始没有空指针域了，递归不可能从这里返回了*/
    {
        return;
    }
    /*开始访问前序遍历的结点。*/
    if(binarythrnodeptr->leftchild == NULL) /*当前访问的结点：若其左孩子为空：则左孩子指针域加前驱线索*/
    {
        binarythrnodeptr->LTag = Thread;
        binarythrnodeptr->leftchild = (*prenode); /*加前驱线索*/
    }
    if((*prenode)->rightchild == NULL) /*刚刚访问过的结点：若其右孩子为空：则右孩子指针域加后继线索*/
    {
        (*prenode)->RTag = Thread;
        (*prenode)->rightchild = binarythrnodeptr; /*加后继线索*/
    }
    *prenode = binarythrnodeptr; /*保证*prenode指向刚刚访问过的结点*/

    if(binarythrnodeptr->LTag == Link) /*左子树存在，注意：这个判断一个要有*/
    {
        PreThreading(binarythrnodeptr->leftchild, prenode); /*左子树前序线索化*/
    }
    if(binarythrnodeptr->RTag == Link) /*右子树存在*/
    {
        PreThreading(binarythrnodeptr->rightchild, prenode); /*右子树前序线索化*/
    }
}

/*************************************************************
 *函数名：MidThreading()
 *功能：中序线索化(只能部分线索)
 *中序线索化:是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索。
 *输入参数：
 * binarythrnodeptr ：二叉树的根结点
 * prenode : 刚刚访问过的结点 ：即为当前访问结点的前驱(初始指向线索链表的空头结点)
 *输出参数：
 * prenode ：
 *返回值：空
 *注意：第一次递归调用时，prenode指向线索链表的空头结点
 *线索化的实质：将二叉链表中的空指针改为指向前驱或后继的线索
 *线索化的过程：在遍历的过程中修改空指针的过程
**************************************************************/
void MidThreading(BinaryThrNodePtr binarythrnodeptr, BinaryThrNodePtr * prenode)
{
    if(binarythrnodeptr == NULL)
    {
        return;
    }
    if(binarythrnodeptr->LTag == Link)
    {
        MidThreading(binarythrnodeptr->leftchild, prenode); /*左子树中序线索化*/
    }
    /*开始访问中序遍历的结点。*/
    if(binarythrnodeptr->leftchild == NULL) /*当前访问的结点：若其左孩子为空：则左孩子指针域加前驱线索*/
    {
        binarythrnodeptr->LTag = Thread;
        binarythrnodeptr->leftchild = (*prenode); /*加前驱线索*/
    }
    if((*prenode)->rightchild == NULL) /*刚刚访问过的结点：若其右孩子为空：则右孩子指针域加后继线索*/
    {
        (*prenode)->RTag = Thread;
        (*prenode)->rightchild = binarythrnodeptr; /*加后继线索*/
    }
    *prenode = binarythrnodeptr; /*保证*prenode指向刚刚访问过的结点*/

    if(binarythrnodeptr->RTag == Link)
    {
        MidThreading(binarythrnodeptr->rightchild, prenode); /*右子树中序线索化*/
    }
}

/*************************************************************
 *函数名：PosThreading()
 *功能：后序线索化(只能部分线索)
 *后序线索化:是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照后序遍历的方法访问结点时建立线索。
 *输入参数：
 * root ：二叉树的根结点
 * prenode : 刚刚访问过的结点 ：即为当前访问结点的前驱
 *输出参数：
 * prenode ：
 *返回值：空
 *注意：第一次递归调用时，prenode指向线索链表的空头结点
 *线索化的实质：将二叉链表中的空指针改为指向前驱或后继的线索
 *线索化的过程：在遍历的过程中修改空指针的过程
**************************************************************/
void PosThreading(BinaryThrNodePtr binarythrnodeptr, BinaryThrNodePtr * prenode)
{
    if(binarythrnodeptr == NULL)
    {
        return;
    }
    if(binarythrnodeptr->LTag == Link) /*左子树存在*/
    {
        PosThreading(binarythrnodeptr->leftchild, prenode); /*左子树后序线索化*/
    }
    if(binarythrnodeptr->RTag == Link) /*右子树存在*/
    {
        PosThreading(binarythrnodeptr->rightchild, prenode); /*右子树后序线索化*/
    }
    /*开始访问后序遍历的结点。*/
    if(binarythrnodeptr->leftchild == NULL) /*当前访问的结点：若其左孩子为空：则左孩子指针域加前驱线索*/
    {
        binarythrnodeptr->LTag = Thread;
        binarythrnodeptr->leftchild = (*prenode); /*加前驱线索*/
    }
    if((*prenode)->rightchild == NULL) /*刚刚访问过的结点：若其右孩子为空：则右孩子指针域加后继线索*/
    {
        (*prenode)->RTag = Thread;
        (*prenode)->rightchild = binarythrnodeptr; /*加后继线索*/
    }
    *prenode = binarythrnodeptr; /*保证*prenode指向刚刚访问过的结点*/
}

/*************************************************************
 *函数名：CreateBinaryTreeThreading()
 *功能：将二叉树线索化，得到二叉树线索链表
 *输入参数：
 * binarythrnodeptr ：待线索化的二叉树根节点
 * type : 线索方式(-1: 先序遍历， 0：中序遍历， 1：后序遍历)
 *输出参数：
 * threadhead ：线索链表的头结点
 *返回值：
 * 0：成功 -1：失败
 *线索化的实质：将二叉链表中的空指针改为指向前驱或后继的线索
 *线索化的过程：在遍历的过程中修改空指针的过程
**************************************************************/
int CreateBinaryTreeThreading(BinaryThrNodePtr * threadhead, BinaryThrNodePtr binarythrnodeptr, int type)
{
    BinaryThrNodePtr prenode = NULL; /*存放刚刚访问过的结点 ：即为当前访问结点的前驱*/
    *threadhead = (BINARYTHRNODE *)malloc(sizeof(BINARYTHRNODE)); /*建立头结点*/
    if(*threadhead == NULL)
    {
        printf("CreateThreading malloc err!\n");
        return -1;
    }
    (*threadhead)->LTag = Link; /*头结点左标志域为Link：左孩子指针*/
    (*threadhead)->RTag = Thread; /*头结点右标志域为Thread：后继指针*/
    (*threadhead)->rightchild = *threadhead; /*头结点后继指针暂时回指*/
    if(binarythrnodeptr == NULL) /*若二叉树为空*/
    {
        (*threadhead)->leftchild = *threadhead; /*为空，则前驱指针回指*/
    }
    else /*二叉树非空*/
    {
        (*threadhead)->leftchild = binarythrnodeptr; /*非空，则头结点的左孩子指向根结点*/
        prenode = (*threadhead); /*刚刚访问过的结点记录下来，初始指向线索链表的空头结点*/
        if(type == -1)
        {
            PreThreading(binarythrnodeptr, &prenode); /*前序线索化*/
        }
        else if(type == 0)
        {
            MidThreading(binarythrnodeptr, &prenode); /*中序线索化*/
        }
        else if(type == 1)
        {
            PosThreading(binarythrnodeptr, &prenode); /*后序线索化*/
        }
        else
        {
            printf("type 参数不对！\n");
        }
        /*prenode会指向遍历序列的最后一个结点 : 最后一个结点线索化*/
        if(prenode->rightchild == NULL)
        {
            prenode->RTag = Thread;
            prenode->rightchild = *threadhead;
        }
        (*threadhead)->rightchild = prenode; /*头结点后继指针指向最后一个结点*/
    }
}

/************************************
 *函数名：GetLeftRightchildLenByPreAndMid()
 *功能：根据二叉树的先序序列+中序序列，取得当前二叉树左右孩子的结点数
 *输入参数：
 * cur_pre: 当前二叉树的先序序列(其中：cur_pre中第一个元素，即是根元素结点)
 * cur_mid: 当前二叉树的中序序列
 *输出参数：
 * leftlen: 当前二叉树左孩子的长度
 * rightlen: 当前二叉树右孩子的长度
 *返回值：
 * 0：成功 -1：失败
 *
 *由二叉树的先序序列+中序序列，求当前二叉树的左右孩子的结点数方法：
 * 先序序列的第一个元素就是当前二叉树的根结点。
 *    在中序序列中对比根结点所在的位置，
 *    则中序序列中根结点的左边就是根结点的左孩子，即可求出左孩子的结点数，
 *    中序序列中根结点的右边就是根结点的右孩子，即可求出右孩子的结点数，
*************************************/
int GetLeftRightchildLenByPreAndMid(char * cur_pre, char * cur_mid, int * leftlen, int * rightlen)
{
    int left_len = 0;
    if((cur_pre != NULL)&&(cur_mid != NULL)) /*序列非空，则树存在*/
    {
        /* *cur_pre:就是该二叉树的根结点 */
        while(*(cur_mid+left_len) != *cur_pre) /*从中序序列的第一个元素开始与根元素比较*/
        {
            left_len++;
        }
        *leftlen = left_len;
        /*当前二叉树右孩子的结点数=全树长-左孩子的结点数-根结点数*/
        *rightlen = strlen(cur_pre) - left_len - 1;
    }
    else
    {
        *leftlen = 0;
        *rightlen = 0;
    }
    return 0;
}

/**********************************************************
 *函数名：CreateBinaryThrTreeByPreAndMid()
 *功能：创建二叉树(由前序序列+中序序列，创建一颗二叉树)
 *输入参数：
 * cur_pre：      当前二叉树的先序序列
 * cur_mid：      当前二叉树的中序序列
 *输出参数：
 * root: 二叉树的根结点
 *返回值：
 * 0-成功 -1-失败
 *示例遍历序列编号：
 *          先序序列=[A,B,D,H,I,E,J,C,F,G]
 * 中序序列=[H,D,I,B,J,E,A,F,C,G]
 * 后序序列=[H,I,D,J,E,B,F,G,C,A]
 * 层次序列=[A,B,C,D,E,F,G,H,I,J]
 *(由前序序列+中序序列，可唯一确定一颗二叉树)编程思路：
 *        从当前二叉树先序序列cur_pre开始，第一个是根结点，再右边的leftlen个结点是左孩子，再右边rightlen个结点是右孩子,
 *        则当前二叉树左孩子的先序序列从cur_pre+1地址开始,长：leftlen。当前二叉树右孩子的先序序列从cur_pre+1+leftlen地址开始，长：rightlen。
 *     从当前二叉树中序序列根元素开始，左右分开，左边是当前二叉树左孩子，右边是当前二叉树右孩子。
 *     则当前二叉树左孩子的中序序列继续从当前二叉树的中序序列的cur_mid地址开始,长：leftlen。当前二叉树右孩子的中序序列从cur_mid+leftlen+1地址开始，长：rightlen。
***********************************************************/
int CreateBinaryThrTreeByPreAndMid(BinaryThrNodePtr * root, char * cur_pre, char * cur_mid)
{
    int i = 0;
    int ret = -1;
    int leftlen; /*当前二叉树左孩子的结点数*/
    int rightlen; /*当前二叉树右孩子的结点数*/
    char left_pre[128]; /*当前二叉树左孩子的先序序列*/
    char left_mid[128]; /*当前二叉树左孩子的中序序列*/
    char right_pre[128]; /*当前二叉树右孩子的先序序列*/
    char right_mid[128]; /*当前二叉树右孩子的中序序列*/

    memset(left_pre, 0 ,sizeof(left_pre));
    memset(left_mid, 0, sizeof(left_mid));
    memset(right_pre, 0 ,sizeof(right_pre));
    memset(right_mid, 0, sizeof(right_mid));

    if((cur_pre != NULL)&&(cur_mid != NULL)) /*当树的序列非空，则表明树是存在的*/
    {
        /*接下来创建一个结点的存储区域*/
        *root = (BINARYTHRNODE *)malloc(sizeof(BINARYTHRNODE));
        if(*root == NULL)
        {
            printf("CreateBinaryThrTreeByPreAndMid malloc err!\n");
            return -1;
        }
        memset(*root, 0, sizeof(BINARYTHRNODE));
        memset((*root)->name, 0, sizeof(STRING));
        memset((*root)->value, 0, sizeof(STRING));
        /*以当前二叉树先序序列cur_pre中的第一个元素(*cur_pre)作为域值来生成根结点*/
        strncpy((*root)->name, cur_pre, sizeof(char)*1); /*填充根结点名*/
        /*整颗二叉树是10个节点，data[i]中的数据是10个字符串，即为先序序列cur_pre中相同的数据*/
        for(i=0; i<10; i++)
        {
            /*或者：if((*cur_pre) == data[i][0])*/
            if(strncmp(cur_pre, data[i], sizeof(char)*1) == 0) /*定位结点数据域要填充的字符串*/
            {
                strcpy((*root)->value, data[i]); /*填充根结点值*/
                break;
            }
        }
        (*root)->LTag = (*root)->RTag = Link;
        (*root)->leftchild = (*root)->rightchild = NULL; /*刚生成的节点左右孩子指针先赋NULL值*/

        /*获取当前二叉树左孩子的结点数leftlen, 右孩子的结点数rightlen*/
        GetLeftRightchildLenByPreAndMid(cur_pre, cur_mid, &leftlen, &rightlen);

        memcpy(left_pre, cur_pre+1, leftlen); /*左孩子的先序序列*/
        memcpy(left_mid, cur_mid, leftlen); /*左孩子的中序序列*/
        /*printf("结点=[%c],左孩子:结点数=[%d],先序序列=[%s],中序序列=[%s]\n", *cur_pre, leftlen, left_pre,left_mid);*/
        memcpy(right_pre, cur_pre+1+leftlen, rightlen); /*右孩子的先序序列*/
        memcpy(right_mid, cur_mid+leftlen+1, rightlen); /*右孩子的中序序列*/
        /*printf("结点=[%c],右孩子:结点数=[%d],先序序列=[%s],中序序列=[%s]\n", *cur_pre, rightlen, right_pre, right_mid);*/

        if(leftlen > 0) /*当前二叉树左孩子存在,才需要创建这颗二叉树*/
        {
            ret = CreateBinaryThrTreeByPreAndMid(&((*root)->leftchild), left_pre, left_mid); /*创建当前二叉树的左孩子*/
            if(ret < 0)
                return -1;
        }

        if(rightlen > 0) /*当前二叉树右孩子存在，才需要创建这颗二叉树*/
        {
            ret = CreateBinaryThrTreeByPreAndMid(&((*root)->rightchild), right_pre, right_mid); /*创建当前二叉树的右孩子*/
            if(ret < 0)
                return -1;
        }
    }
    else; /*树不存在,二叉树的根节点已经赋空，这里什么都不需要做*/
    return 0;
}

/*功能：打印出整颗二叉树(按照先序遍历序列)*/
void PrintBinaryTreeNodeByPre(BinaryThrNodePtr binarythrnodeptr)
{
    if(binarythrnodeptr == NULL)
    {
        return;
    }
    else
    {
        printf("结点名=[%s],结点值=[%s],LTag=[%d],RTag=[%d]\n", binarythrnodeptr->name, binarythrnodeptr->value, binarythrnodeptr->LTag, binarythrnodeptr->RTag);
        PrintBinaryTreeNodeByPre(binarythrnodeptr->leftchild);
        PrintBinaryTreeNodeByPre(binarythrnodeptr->rightchild);
    }
}

/*功能：打印出整颗二叉树(按照中序遍历序列)*/
void PrintBinaryTreeNodeByMid(BinaryThrNodePtr binarythrnodeptr)
{
    if(binarythrnodeptr == NULL)
    {
        return;
    }
    else
    {
        PrintBinaryTreeNodeByMid(binarythrnodeptr->leftchild);
        printf("结点名=[%s],结点值=[%s],LTag=[%d],RTag=[%d]\n", binarythrnodeptr->name, binarythrnodeptr->value, binarythrnodeptr->LTag, binarythrnodeptr->RTag);
        PrintBinaryTreeNodeByMid(binarythrnodeptr->rightchild);
    }
}

/*功能：打印出整颗二叉树(按照后序遍历序列)*/
void PrintBinaryTreeNodeByPos(BinaryThrNodePtr binarythrnodeptr)
{
    if(binarythrnodeptr == NULL)
    {
        return;
    }
    else
    {
        PrintBinaryTreeNodeByPos(binarythrnodeptr->leftchild);
        PrintBinaryTreeNodeByPos(binarythrnodeptr->rightchild);
        printf("结点名=[%s],结点值=[%s],LTag=[%d],RTag=[%d]\n", binarythrnodeptr->name, binarythrnodeptr->value, binarythrnodeptr->LTag, binarythrnodeptr->RTag);
    }
}

/*功能：打印出整颗中序线索化二叉树(按照中序遍历序列，非递归)
这个还可以仿照下面的改进*/
void PrintBinaryThrTreeNodeByMid(BinaryThrNodePtr threadhead)
{
    BinaryThrNodePtr p = NULL;
    p = threadhead->leftchild; /*p指向根结点*/
    while(p != threadhead) /*p指向threadhead时：表示遍历结束*/
    {
        while(p->LTag == Link) /*结点指针走到最左下结点,就可以访问了*/
        {
            p = p->leftchild;
        }
        printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);

        while((p->RTag == Thread)&&(p->rightchild != threadhead)) /*有后继结点，就一直向后找*/
        {
            p = p->rightchild; /*指向后继结点，是可以直接访问的*/
            printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);
        }
        p = p->rightchild; /*后继找完了，就找右孩子结点*/
    }
}

/*功能：打印出整颗先序线索化二叉树(按照先序遍历序列，非递归)*/
void PrintBinaryThrTreeNodeByPre(BinaryThrNodePtr threadhead)
{
    BinaryThrNodePtr p = NULL;
    p = threadhead->leftchild; /*p指向根结点*/
    while(p != threadhead) /*p指向线索链表头threadhead时：表示遍历结束*/
    {
        while(p->LTag == Link)
        {
            /*p指向的结点：有左子树，就可以访问了*/
            printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);
            p = p->leftchild;
        }

        while(p->RTag == Thread) /*有后继结点，就一直向后找*/
        {
            /*p指向的结点：有后继结点，是可以直接访问的*/
            printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);
            p = p->rightchild;
            if(p == threadhead) /*p指向线索头结点了，就可以跳出循环了*/
            {
                break;
            }
        }
    }
}

/*功能：打印出整颗后序线索化二叉树(按照后序遍历序列，非递归)*/
void PrintBinaryThrTreeNodeByPos(BinaryThrNodePtr threadhead)
{
    BinaryThrNodePtr p = NULL;
    BinaryThrNodePtr parentptr = NULL;
    p = threadhead->leftchild; /*p指向根结点*/

    /*从根开始：一直向左，走到最左下方*/
    while(p->LTag == Link)
    {
        p = p->leftchild; /*p指向第一个被访问的节点*/
    }

    while(p != threadhead)
    {
        printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);
        parentptr = GetBinaryThrTreeParent(threadhead, p); /*parentptr是p的双亲*/

        if(parentptr == threadhead) /*p是根节点，整颗树就一个结点,没有左右孩子*/
        {
            break;
        }

        if(parentptr->RTag == Thread) /*parentptr没有右孩子*/
        {
            p = parentptr; /*根据(后序:左,右,根)p是左孩子,右孩子为空,可以开始遍历根结点了*/
        }
        else if(p == parentptr->rightchild) /*p是parentptr的右孩子*/
        {
            p = parentptr; /*根据(后序:左,右,根)p是右孩子,已访问,可以开始遍历根结点了*/
        }
        else if(p == parentptr->leftchild) /*p是parentptr的左孩子*/
        {
            if(parentptr->RTag == Link) /*parentptr有右孩子*/
            {
                parentptr = parentptr->rightchild; /*再把这个根的右孩子,当做根结点*/
                while(parentptr->LTag == Link) /*从根开始：一直向左，走到最左下方*/
                {
                    parentptr = parentptr->leftchild;
                }
            }
            p = parentptr;
        }
    }
}