中序线索化二叉树及其中序遍历

输入样例

• 输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。

注意:共一行，包含一串字符，表示按中序遍历二叉线索树得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。

ABC  DE G  F  

输出样例

C B E G D F A 

思路：

1. 首先需要根据先序序列创建一个二叉树。
2. 把创建的二叉树进行中序线索化。
3. 线索化完成之后，需要进行中序线索化遍历。

算法思想

• 首先创建线索化二叉树的结构体

ltag = 0:lchild指向左孩子
ltag = 1:lchild指向结点的前驱;
rtag = 0:rchild指向右孩子
rtag = 1:rchild指向后继

• 根据先序序列创建二叉树
• 进行中序线索化
  ①定义一个前驱指针pre用来指向当前结点的”前一个”结点
  ②如果当前结点不为NULL，就根据中序的思想来递归线索化(左根右)
  ③线索完成之后就根据线索进行中序线索遍历(左根右)

C语言代码

//下面用了一点C++的引用(&)
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
//线索化二叉树的结构
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode* lchild, * rchild;
    /*
        ltag = 0:lchild指向左孩子
        ltag = 1:lchild指向结点的前驱;
        rtag = 0:rchild指向右孩子
        rtag = 1:rchild指向后继
    */
    int ltag, rtag;
}ThreadNode,*ThreadTree;

//创建二叉树
void CreatBiTree(ThreadTree& root) {
    ElemType data;
    scanf("%c", &data);
    //data = getchar();
    if (data == ' ')
    {
        root = NULL;
    }
    else
    {
        root = (ThreadNode*)calloc(1, sizeof(ThreadNode));
        root->data = data;
        CreatBiTree(root->lchild);
        CreatBiTree(root->rchild);
    }
}

//中序遍历对二叉树进行线索化
void InThread(ThreadTree& root, ThreadTree& pre) {
    //左根右
    if (root != NULL)
    {
        InThread(root->lchild, pre);//递归线索化左子树(处理左子树)

        //处理根
        if (root->lchild == NULL)//如果左子树为空，则建立前驱线索
        {
            root->lchild = pre;
            root->ltag = 1;//建立线索之后修改ltag，表示指向了前驱
        }
        if (pre != NULL && pre->rchild == NULL)
        {
            pre->rchild = root;//建立前驱结点的后继线索
            pre->rtag = 1;
        }
        pre = root;//修改前一个结点，让其指向当前结点

        InThread(root->rchild, pre);//递归线索化右子树(处理右子树)
    }
}

//中序遍历创建中序线索二叉树
void CreatInThread(ThreadTree root) {
    ThreadTree pre = NULL;//用来指向当前结点的前一个结点
    if (root != NULL)//非空二叉树，则线索化
    {
        InThread(root,pre);//线索化二叉树
        if (pre->rchild == NULL)//对最后一个结点的处理
        {
            pre->rtag = 1;
        }
        /*pre->rchild = NULL;
        pre->rtag = 1;*/
    }
}

//求中序线索化二叉树中中序序列下的第一个结点
ThreadNode* FirstNode(ThreadNode* p) {
    while (p->ltag == 0)//表示有左子树
    {
        p = p->lchild;//一直找,找到最左下的节点(不一定是叶子结点,只要没有左子树就行)
    }
    return p;//返回最左下的节点
}

//求中序线索化二叉树中中序序列下的后继
ThreadNode* NextNode(ThreadNode* p) {
    if (p->rtag == 0)//如果有右子树
    {
        return FirstNode(p->rchild);//返回右子树中最左下的结点
    }
    return p->rchild;//rtag == 1直接返回后继线索即可
}

//中序线索化二叉树的中序遍历
void ThreadInOrder(ThreadNode *root) {
    //左根右
    for (ThreadNode *p = FirstNode(root);p != NULL;p = NextNode(p))
    {
        printf("%c ", p->data);
    }
}

int main() {
    ThreadTree root;
    CreatBiTree(root);
    CreatInThread(root);
    ThreadInOrder(root);//线索化的中序遍历
    printf("\n");
    return 0;
}

C语言(先序线索二叉树)——注意转圈问题

//先序遍历对二叉树进行线索化
void InThread(ThreadTree& root, ThreadTree& pre) {
    //根左右
    if (root != NULL)
    {

        //处理根
        if (root->lchild == NULL)//如果左子树为空，则建立前驱线索
        {
            root->lchild = pre;
            root->ltag = 1;//建立线索之后修改ltag，表示指向了前驱
        }
        if (pre != NULL && pre->rchild == NULL)
        {
            pre->rchild = root;//建立前驱结点的后继线索
            pre->rtag = 1;
        }
        pre = root;//修改前一个结点，让其指向当前结点

        if(root->ltag == 0){//lchild不是前驱线索，才向左走，防止出现转圈问题
            InThread(root->lchild, pre);//递归线索化左子树(处理左子树)
        }

        InThread(root->rchild, pre);//递归线索化右子树(处理右子树)
    }
}

C语言(后序线索二叉树)

//后序遍历对二叉树进行线索化
void InThread(ThreadTree& root, ThreadTree& pre) {
    //左右根
    if (root != NULL)
    {
        InThread(root->lchild, pre);//递归线索化左子树(处理左子树)

        InThread(root->rchild, pre);//递归线索化右子树(处理右子树)

        //处理根
        if (root->lchild == NULL)//如果左子树为空，则建立前驱线索
        {
            root->lchild = pre;
            root->ltag = 1;//建立线索之后修改ltag，表示指向了前驱
        }
        if (pre != NULL && pre->rchild == NULL)
        {
            pre->rchild = root;//建立前驱结点的后继线索
            pre->rtag = 1;
        }
        pre = root;//修改前一个结点，让其指向当前结点


    }
}