全线索二叉树

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

#define SZ_STRING 1024

typedef char STRING[SZ_STRING];

/************************************begin二叉树定义区****************************/
/*二叉树的二叉线索存储表示*/
/*可以得到全线索链表 : 全线索链表建成之后，就相当于双向循环链表一样使用，非常方便
但是它占用的空间大！*/
typedef struct binaryallthrnode
{
    STRING name; /*结点名称*/
    STRING value;     /*结点值*/
    struct binaryallthrnode * prior; /*前驱指针*/
    struct binaryallthrnode * next; /*后继指针*/
    struct binaryallthrnode * leftchild;     /*左孩子指针*/
    struct binaryallthrnode * rightchild;     /*右孩子指针*/
}BINARYALLTHRNODE;

typedef BINARYALLTHRNODE * BinaryAllThrNodePtr;

int GetLeftRightchildLenByPreAndMid(char * cur_pre, char * cur_mid, int * leftlen, int * rightlen);
int CreateBinaryAllThrTreeByPreAndMid(BinaryAllThrNodePtr * root, char * cur_pre, char * cur_mid);

void PreAllThreading(BinaryAllThrNodePtr root, BinaryAllThrNodePtr * prenode);
void MidAllThreading(BinaryAllThrNodePtr root, BinaryAllThrNodePtr * prenode);
void PosAllThreading(BinaryAllThrNodePtr root, BinaryAllThrNodePtr * prenode);
int CreateBinaryTreeAllThreading(BinaryAllThrNodePtr * threadhead, BinaryAllThrNodePtr root, int type);

void PrintBinaryTreeNodeByPre(BinaryAllThrNodePtr root);
void PrintBinaryTreeNodeByMid(BinaryAllThrNodePtr root);
void PrintBinaryTreeNodeByPos(BinaryAllThrNodePtr root);
void PrintBinaryAllThrTreeNodeByPre(BinaryAllThrNodePtr allthreadhead);
void PrintBinaryAllThrTreeNodeByMid(BinaryAllThrNodePtr allthreadhead);
void PrintBinaryAllThrTreeNodeByPos(BinaryAllThrNodePtr allthreadhead);

void PreOrderTraverseAllThr(BinaryAllThrNodePtr allthreadhead, char * pre);
void MidOrderTraverseAllThr(BinaryAllThrNodePtr allthreadhead, char * mid);
void PosOrderTraverseAllThr(BinaryAllThrNodePtr allthreadhead, char * pos);

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

STRING data[26];

int main(int argc, char * * argv)
{
    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");
    BinaryAllThrNodePtr rootallthrnodeptr1 = NULL;
    CreateBinaryAllThrTreeByPreAndMid(&rootallthrnodeptr1, pre, mid);
    printf("按照中序遍历序列,打印出整颗二叉树:\n");
    PrintBinaryTreeNodeByMid(rootallthrnodeptr1);

    BinaryAllThrNodePtr allthreadhead = NULL; /*全线索链表的头节点*/
    printf("中序全线索化二叉树:\n");
    CreateBinaryTreeAllThreading(&allthreadhead, rootallthrnodeptr1, 0); /*中序全线索化二叉树*/
    printf("按照中序遍历序列,打印出整颗中序全线索化二叉树:\n");
    PrintBinaryAllThrTreeNodeByMid(allthreadhead);
    memset(mid, 0, sizeof(mid));
    MidOrderTraverseAllThr(allthreadhead, 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");
    BinaryAllThrNodePtr rootallthrnodeptr2 = NULL;
    CreateBinaryAllThrTreeByPreAndMid(&rootallthrnodeptr2, pre, mid);
    printf("按照先序遍历序列,打印出整颗二叉树:\n");
    PrintBinaryTreeNodeByPre(rootallthrnodeptr2);

    printf("先序全线索化二叉树:\n");
    CreateBinaryTreeAllThreading(&allthreadhead, rootallthrnodeptr2, -1); /*先序全线索化二叉树*/
    printf("按照先序遍历序列,打印出整颗先序全线索化二叉树:\n");
    PrintBinaryAllThrTreeNodeByPre(allthreadhead);
    memset(pre, 0, sizeof(pre));
    printf("====================================\n");
    PreOrderTraverseAllThr(allthreadhead, 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");
    BinaryAllThrNodePtr rootallthrnodeptr3 = NULL;
    CreateBinaryAllThrTreeByPreAndMid(&rootallthrnodeptr3, pre, mid);
    printf("按照后序遍历序列,打印出整颗二叉树:\n");
    PrintBinaryTreeNodeByPos(rootallthrnodeptr3);

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

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

    return 0;
}

/*************************************************************************
 *函数名：PosOrderTraverseAllThr()
 *功能：遍历后序全线索化二叉树(非递归)
 *输入参数：
 * allthreadhead ：线索二叉树的头结点
 *输出参数：
 * mid : 后序序列
 *返回值：空
 *特点：非递归遍历时，如果有线索链表是可以方便的实现遍历，可以不用栈了。
**************************************************************************/
void PosOrderTraverseAllThr(BinaryAllThrNodePtr allthreadhead, char * pos)
{
    BinaryAllThrNodePtr p = NULL;
    p = allthreadhead->next; /*p指向后序序列的第一个结点*/
    while(p != allthreadhead) /*p指向线索链表头allthreadhead时：表示遍历结束*/
    {
        /*printf("结点名=[%s], 结点值=[%s], LTag=[%d], RTag=[%d]\n", p->name, p->value, p->LTag, p->RTag);*/
        strncat(pos, p->name, sizeof(char)*1); /*得到后序序列*/
        p = p->next;
    }
}

/*************************************************************************
 *函数名：MidOrderTraverseAllThr()
 *功能：遍历中序全线索化二叉树(非递归)
 *输入参数：
 * allthreadhead ：线索二叉树的头结点
 *输出参数：
 * mid : 中序序列
 *返回值：空
 *特点：非递归遍历时，如果有线索链表是可以方便的实现遍历，可以不用栈了。
**************************************************************************/
void MidOrderTraverseAllThr(BinaryAllThrNodePtr allthreadhead, char * mid)
{
    BinaryAllThrNodePtr p = NULL;
    p = allthreadhead->next; /*p指向中序序列的第一个结点*/
    while(p != allthreadhead) /*p指向线索链表头allthreadhead时：表示遍历结束*/
    {
        /*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->next;
    }
}

/*************************************************************************
 *函数名：PreOrderTraverseAllThr()
 *功能：遍历先序全线索化二叉树(非递归)
 *输入参数：
 * allthreadhead ：线索二叉树的头结点
 *输出参数：
 * pre : 先序序列
 *返回值：空
 *特点：非递归遍历时，如果有线索链表是可以方便的实现遍历，可以不用栈了。
**************************************************************************/
void PreOrderTraverseAllThr(BinaryAllThrNodePtr allthreadhead, char * pre)
{
    BinaryAllThrNodePtr p = NULL;
    p = allthreadhead->next; /*p指向先序序列的第一个结点*/
    while(p != allthreadhead) /*p指向线索链表头allthreadhead时：表示遍历结束*/
    {
        /*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->next;
    }
}

/*************************************************************
 *函数名：PreAllThreading()
 *功能：前序全线索化
 *前序全线索化:是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照前序遍历的方法访问结点时建立线索。
 *输入参数：
 * root ：二叉树的根结点
 * prenode : 刚刚访问过的结点 ：即为当前访问结点的前驱
 *输出参数：
 * prenode ：
 *返回值：空
 *注意：第一次递归调用时，prenode指向线索链表的空头结点
 *全线索化的实质：将二叉链表中的前驱和后继指针赋值,使之指向前驱结点或后继结点。
 *线索化的过程：在遍历的过程中对前驱和后继指针赋值的过程
**************************************************************/
void PreAllThreading(BinaryAllThrNodePtr root, BinaryAllThrNodePtr * prenode)
{
    if(root == NULL)
        return;
    /*开始访问前序遍历的结点。*/
    root->prior = (*prenode); /*加前驱线索*/
    (*prenode)->next = root; /*加后继线索*/
    *prenode = root; /*保证*prenode指向刚刚访问过的结点*/

    PreAllThreading(root->leftchild, prenode); /*左子树前序线索化*/

    PreAllThreading(root->rightchild, prenode); /*右子树前序线索化*/
}

/*************************************************************
 *函数名：MidAllThreading()
 *功能：中序全线索化
 *中序全线索化:是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索。
 *输入参数：
 * root ：二叉树的根结点
 * prenode : 刚刚访问过的结点 ：即为当前访问结点的前驱
 *输出参数：
 * prenode ：
 *返回值：空
 *注意：第一次递归调用时，prenode指向线索链表的空头结点
 *全线索化的实质：将二叉链表中的前驱和后继指针赋值,使之指向前驱结点或后继结点。
 *线索化的过程：在遍历的过程中对前驱和后继指针赋值的过程
**************************************************************/
void MidAllThreading(BinaryAllThrNodePtr root, BinaryAllThrNodePtr * prenode)
{
    if(root == NULL)
        return;
    MidAllThreading(root->leftchild, prenode); /*左子树中序线索化*/
    /*开始访问中序遍历的结点。*/
    root->prior = (*prenode); /*加前驱线索*/
    (*prenode)->next = root; /*加后继线索*/
    *prenode = root; /*保证*prenode指向刚刚访问过的结点*/

    MidAllThreading(root->rightchild, prenode); /*右子树中序线索化*/
}

/*************************************************************
 *函数名：PosAllThreading()
 *功能：后序全线索化
 *后序全线索化:是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照后序遍历的方法访问结点时建立线索。
 *输入参数：
 * root ：二叉树的根结点
 * prenode : 刚刚访问过的结点 ：即为当前访问结点的前驱
 *输出参数：
 * prenode ：
 *返回值：空
 *注意：第一次递归调用时，prenode指向线索链表的空头结点
 *全线索化的实质：将二叉链表中的前驱和后继指针赋值,使之指向前驱结点或后继结点。
 *线索化的过程：在遍历的过程中对前驱和后继指针赋值的过程
**************************************************************/
void PosAllThreading(BinaryAllThrNodePtr root, BinaryAllThrNodePtr * prenode)
{
    if(root == NULL)
        return;
    PosAllThreading(root->leftchild, prenode); /*左子树后序线索化*/

    PosAllThreading(root->rightchild, prenode); /*右子树后序线索化*/

    /*开始访问后序遍历的结点。*/
    root->prior = (*prenode); /*加前驱线索*/
    (*prenode)->next = root; /*加后继线索*/
    *prenode = root; /*保证*prenode指向刚刚访问过的结点*/
}

/*************************************************************
 *函数名：CreateBinaryTreeAllThreading()
 *功能：将二叉树全线索化，得到二叉树全线索链表
 *输入参数：
 * root ：待线索化的二叉树根节点
 * type : 全线索方式(-1: 先序遍历， 0：中序遍历， 1：后序遍历)
 *输出参数：
 * allthreadhead ：全线索链表的头结点
 *返回值：
 * 0：成功 -1：失败
 *全线索化的实质：将二叉链表中的前驱和后继指针赋值,使之指向前驱结点或后继结点。
 *线索化的过程：在遍历的过程中对前驱和后继指针赋值的过程
**************************************************************/
int CreateBinaryTreeAllThreading(BinaryAllThrNodePtr * allthreadhead, BinaryAllThrNodePtr root, int type)
{
    BinaryAllThrNodePtr prenode = NULL; /*存放刚刚访问过的结点：即为当前访问结点的前驱*/
    *allthreadhead = (BINARYALLTHRNODE *)malloc(sizeof(BINARYALLTHRNODE)); /*建立头结点*/
    if(*allthreadhead == NULL)
    {
        printf("CreateBinaryTreeAllThreading malloc err!\n");
        return -1;
    }
    (*allthreadhead)->leftchild = *allthreadhead; /*头结点左孩子指针暂时回指*/
    (*allthreadhead)->rightchild = *allthreadhead; /*头结点右孩子指针暂时回指*/
    (*allthreadhead)->prior = *allthreadhead; /*头结点的前驱指针暂时回指*/
    (*allthreadhead)->next = *allthreadhead; /*头结点的后继指针暂时回指*/
    if(root == NULL) /*若二叉树为空*/
    {
        (*allthreadhead)->leftchild = *allthreadhead; /*为空，则左孩子指针回指*/
    }
    else /*二叉树非空*/
    {
        (*allthreadhead)->leftchild = root; /*非空，则头结点的左孩子指向根结点*/
        prenode = (*allthreadhead); /*刚刚访问过的结点记录下来，初始指向线索链表的空头结点*/
        if(type == -1)
        {
            PreAllThreading(root, &prenode); /*前序线索化*/
        }
        else if(type == 0)
        {
            MidAllThreading(root, &prenode); /*中序线索化*/
        }
        else if(type == 1)
        {
            PosAllThreading(root, &prenode); /*后序线索化*/
        }
        else
        {
            printf("type 参数不对！\n");
        }
        /*prenode会指向遍历序列的最后一个结点 : 最后一个结点线索化*/
        prenode->next = *allthreadhead; /*头结点前驱指针指向最后一个结点*/
        (*allthreadhead)->prior = 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;
}

/**********************************************************
 *函数名：CreateBinaryAllThrTreeByPreAndMid()
 *功能：创建二叉树(由前序序列+中序序列，创建一颗二叉树)
 *输入参数：
 * 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 CreateBinaryAllThrTreeByPreAndMid(BinaryAllThrNodePtr * 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 = (BINARYALLTHRNODE *)malloc(sizeof(BINARYALLTHRNODE));
        if(*root == NULL)
        {
            printf("CreateBinaryAllThrTreeByPreAndMid malloc err!\n");
            return -1;
        }
        memset(*root, 0, sizeof(BINARYALLTHRNODE));
        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)->prior = (*root)->next = NULL; /*前驱指针，后继指针*/
        (*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 = CreateBinaryAllThrTreeByPreAndMid(&((*root)->leftchild), left_pre, left_mid); /*创建当前二叉树的左孩子*/
            if(ret < 0)
                return -1;
        }

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

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

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

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

/*功能：打印出整颗全线索二叉树(按照先序遍历序列)*/
void PrintBinaryAllThrTreeNodeByPre(BinaryAllThrNodePtr allthreadhead)
{
    BinaryAllThrNodePtr p = NULL;
    p = allthreadhead->next; /*p指向先序序列的第一个结点*/
    while(p != allthreadhead) /*p指向线索链表头allthreadhead时：表示遍历结束*/
    {
        printf("结点名=[%s], 结点值=[%s]\n", p->name, p->value);
        p = p->next;
    }
}

/*功能：打印出整颗全线索二叉树(按照中序遍历序列)*/
void PrintBinaryAllThrTreeNodeByMid(BinaryAllThrNodePtr allthreadhead)
{
    BinaryAllThrNodePtr p = NULL;
    p = allthreadhead->next; /*p指向中序序列的第一个结点*/
    while(p != allthreadhead) /*p指向线索链表头allthreadhead时：表示遍历结束*/
    {
        printf("结点名=[%s], 结点值=[%s]\n", p->name, p->value);
        p = p->next;
    }
}

/*功能：打印出整颗全线索二叉树(按照后序遍历序列)*/
void PrintBinaryAllThrTreeNodeByPos(BinaryAllThrNodePtr allthreadhead)
{
    BinaryAllThrNodePtr p = NULL;
    p = allthreadhead->next; /*p指向后序序列的第一个结点*/
    while(p != allthreadhead) /*p指向线索链表头allthreadhead时：表示遍历结束*/
    {
        printf("结点名=[%s], 结点值=[%s]\n", p->name, p->value);
        p = p->next;
    }
}