线索二叉树的建立与遍历 输出问题

Question

#include<stdio.h>
#include<stdlib.h>
//线索化二叉树
//定义线索二叉树的存储结构
typedef struct ThreadNode{
    char data;     //存数据
    struct ThreadNode* Left;   //指针域 
    struct ThreadNode* Right;   //指针域 
    int Tag_Left,Tag_Right;          //标识域 
}ThreadNode,*ThreadTreeNode;  

ThreadTreeNode pre = NULL;   //辅助指针 指向刚访问的树结点 全局变量 
//线索二叉树的初始化（建立）先序建立  按顺序插入 
ThreadTreeNode InitThreadTree(ThreadTreeNode Tree){
    char ch;
    printf("请输入数据 (#表示空指针):\n");
    ch = getchar();
    getchar();                      //吃掉enter产生的空格 
    if(ch == '#') Tree = NULL;      //以#代表空 
    else{
        Tree = (ThreadTreeNode)malloc(sizeof(ThreadNode));
        Tree->data = ch;
        //此时不对标识域进行初始化 遍历的时候才对标识域进行处理 
        Tree->Left = InitThreadTree(Tree->Left);
        Tree->Right = InitThreadTree(Tree->Right);
    }
    return Tree;
}
//中序线索化 不同遍历顺序 有不同的线索化二叉树 
/*每个树结点都考虑两次 如果其左子树为空 则指向前驱 
考虑后继的时候要到下一个结点操作 如果pre不空且pre有右子树则成为pre的后继*/

/*TreeRoot为根结点指针 中序线索二叉树(不带头结点)*/
void InThreading(ThreadTreeNode TreeRoot)   //TreeRoot为根结点指针 
{
    if(TreeRoot)
    {
        InThreading(TreeRoot->Left);        /*左子树递归线索化*/
        if(TreeRoot->Left == NULL)                /*如果没有左子树*/
        {
            TreeRoot->Tag_Left = 1;            /*Tag = 1*/
            TreeRoot->Left = pre;          /*设置前驱*/
        }
        
        else TreeRoot->Tag_Left= 0;            /*有左子树  Tag = 0*/
 
        //判断当前节点的前驱节点不为空且其右子树为空，则改其右指针指向当前节点  
        if(pre != NULL && pre->Right == NULL)
        {
            pre->Tag_Right = 1;            /*设置后继*/
            pre->Right = TreeRoot;
        }
 
        else pre->Tag_Right = 0;
 
        pre = TreeRoot;                       /*记录结点 */
 
        InThreading(TreeRoot->Right);        /*右子树递归线索化*/
    }
}

/*---------带头结点的二叉树的中序线索化--------*/
void HeadNode_InitThreadTree(ThreadTreeNode &HeadNode,ThreadTreeNode TreeRoot)
{
     HeadNode = (ThreadTreeNode)malloc(sizeof(ThreadNode));  //头结点
    HeadNode->Tag_Left= 0;            /*头结点有左孩子，为根结点*/
    HeadNode->Tag_Right = 1;        /*头结点无右孩子，后继线索为中序遍历的最后一个结点*/
    
    HeadNode->Right = HeadNode;        /*初始化时后继为头结点本身*/
 
    if(!TreeRoot) HeadNode->Left = HeadNode;    /*若二叉树为空，左孩子也为头结点本身*/
 
    else
    {
        HeadNode->Left= TreeRoot;     /*头结点的作用体现，统一根结点与其他结点的处理方式*/
         pre = TreeRoot;
        InThreading(TreeRoot);            /*对二叉树中序线索化*/
 
        pre->Tag_Right = 1;                /*线索化结束后，pre为二叉树的最右结点*/
 
        pre->Left = HeadNode;            /*使其右线索指向头结点*/
                                    
        HeadNode->Right = pre;            /*将头结点的后继从它本身改为最右结点*/
    }
}

/*----------遍历中序线索二叉树----------*/
 
void Show(ThreadTreeNode HeadNode)
{/*HeadNode指向线索二叉树的头结点，而头结点的左指针指向二叉树的根结点*/
    ThreadTreeNode Woke_Ptrl = HeadNode->Left;        /*使p指向根结点*/
 
    while(Woke_Ptrl != HeadNode)                    /*若线索二叉树不为空或遍历未结束*/
    {
        while(Woke_Ptrl->Tag_Left == 0)         /*沿左孩子往下，定位*/
        Woke_Ptrl=Woke_Ptrl->Left;    
        printf("%c ",Woke_Ptrl->data);                        /*访问左子树为空的结点*/
        /*若有右线索，且右线索不为头结点*/
        while(Woke_Ptrl->Tag_Right == 1 && Woke_Ptrl->Right != HeadNode)    
        {
            Woke_Ptrl = Woke_Ptrl->Right;
            printf("%c ",Woke_Ptrl->data);                    /*沿右线索访问后继结点*/
        }
        
        Woke_Ptrl = Woke_Ptrl->Right;                /*转向p的右子树*/
    }
}
int main(){
    ThreadTreeNode HeadNode =NULL;  //头结点
    ThreadTreeNode tree = NULL;
    tree = InitThreadTree(tree);
    HeadNode_InitThreadTree(HeadNode,tree);
    printf("中序线索二叉树的输出:\n");
    Show(HeadNode);
}

Answer 1

修改如下，供参考：

#include<stdio.h>
#include<stdlib.h>
//线索化二叉树
//定义线索二叉树的存储结构
typedef struct ThreadNode {
    char data;     //存数据
    struct ThreadNode* Left;   //指针域 
    struct ThreadNode* Right;   //指针域 
    int Tag_Left, Tag_Right;    //标识域 
}ThreadNode, * ThreadTreeNode;
ThreadTreeNode pre = NULL;   //辅助指针 指向刚访问的树结点 全局变量 
//线索二叉树的初始化（建立）先序建立  按顺序插入 
ThreadTreeNode InitThreadTree(ThreadTreeNode  Tree) {
    char ch;
    printf("请输入数据 (#表示空指针):\n");
    ch = getchar();
    getchar();                      //吃掉enter产生的空格 
    if (ch == '#') Tree = NULL;      //以#代表空 
    else {
        Tree = (ThreadTreeNode)malloc(sizeof(ThreadNode));
        Tree->data = ch;
        //此时不对标识域进行初始化 遍历的时候才对标识域进行处理 
        Tree->Left = InitThreadTree(Tree->Left);
        Tree->Right = InitThreadTree(Tree->Right);
    }
    return Tree;
}
//中序线索化 不同遍历顺序 有不同的线索化二叉树 
//每个树结点都考虑两次 如果其左子树为空 则指向前驱
//考虑后继的时候要到下一个结点操作 如果pre不空且pre有右子树则成为pre的后继
//TreeRoot为根结点指针 中序线索二叉树(不带头结点)
void InThreading(ThreadTreeNode TreeRoot)   //TreeRoot为根结点指针 
{
    if (TreeRoot)
    {
        InThreading(TreeRoot->Left);        //左子树递归线索化
        if (TreeRoot->Left == NULL)          //如果没有左子树
        {
            TreeRoot->Tag_Left = 1;         //Tag = 1
            TreeRoot->Left = pre;          //设置前驱
        }
        else TreeRoot->Tag_Left = 0;      //有左子树  Tag = 0
                                    //判断当前节点的前驱节点不为空且其右子树为空，则改其右指针指向当前节点  
        if (pre->Right == NULL )           //&& pre->Tag_Right == NULL)//
        {
            pre->Tag_Right = 1;            //设置后继
            pre->Right = TreeRoot;
        }
        else pre->Tag_Right = 0;
        pre = TreeRoot;                       //记录结点 
        InThreading(TreeRoot->Right);        //右子树递归线索化
    }
}
//---------带头结点的二叉树的中序线索化--------
void HeadNode_InitThreadTree(ThreadTreeNode& HeadNode, ThreadTreeNode TreeRoot)
{
    HeadNode = (ThreadTreeNode)malloc(sizeof(ThreadNode));  //头结点
    HeadNode->Tag_Left = 0;            //头结点有左孩子，为根结点
    HeadNode->Tag_Right = 1;        //头结点无右孩子，后继线索为中序遍历的最后一个结点
    HeadNode->Right = HeadNode;        //初始化时后继为头结点本身
    if (!TreeRoot) HeadNode->Left = HeadNode;    //若二叉树为空，左孩子也为头结点本身
    else
    {
        HeadNode->Left = TreeRoot;     //头结点的作用体现，统一根结点与其他结点的处理方式                          
        pre = HeadNode;//pre = TreeRoot;
        InThreading(TreeRoot);            //对二叉树中序线索化
        pre->Tag_Right = 1;                //线索化结束后，pre为二叉树的最右结点
        pre->Right = HeadNode;//pre->Left = HeadNode;//使其右线索指向头结
        HeadNode->Right = pre;            //将头结点的后继从它本身改为最右结点
    }
}
//----------遍历中序线索二叉树----------
void Show(ThreadTreeNode HeadNode)
{//HeadNode指向线索二叉树的头结点，而头结点的左指针指向二叉树的根结点
    ThreadTreeNode Woke_Ptrl = HeadNode->Left;        //使p指向根结点
    while (Woke_Ptrl != HeadNode)                    //若线索二叉树不为空或遍历未结束
    {
        while (Woke_Ptrl->Tag_Left == 0)    //沿左孩子往下，定位
            Woke_Ptrl = Woke_Ptrl->Left;
        printf("%c ", Woke_Ptrl->data);     //访问左子树为空的结点
                                            //若有右线索，且右线索不为头结点
        while (Woke_Ptrl->Tag_Right == 1 && Woke_Ptrl->Right != HeadNode)
        {
            Woke_Ptrl = Woke_Ptrl->Right;
            printf("%c ", Woke_Ptrl->data);   //沿右线索访问后继结点
        }
        Woke_Ptrl = Woke_Ptrl->Right;       //转向p的右子树
    }
}
int main() 
{
    ThreadTreeNode HeadNode = NULL;  //头结点
    ThreadTreeNode tree = NULL;
    tree = InitThreadTree(tree);
    HeadNode_InitThreadTree(HeadNode, tree);
    printf("中序线索二叉树的输出:\n");
    Show(HeadNode);
    return 0;
}