中序穿线二叉树的实现

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

// 7.6.3 中序穿线二叉树(线索二叉树)的实现
typedef char dataType;
// 线索二叉树的结点结构
typedef struct node
{
    dataType data; // 数据域
    struct node *lChild, *rChild; // 左、右孩子指针
    int lTag, rTag; // 左、右指针是否是线索的标志
}treeNode, *binaryTree;

// 1. 按前序遍历顺序建立二叉树
treeNode *createTree()
{
    treeNode *tree;
    char c;
    if((c = getchar()) == '#')
        tree = NULL;
    else
    {
        tree = (treeNode *) malloc(sizeof(treeNode));
        tree->data = c;
        tree->lChild = createTree();
        tree->rChild = createTree();
    }
    return tree;
}

// 2. 对二叉树中序线索化
treeNode *pre = NULL; // 初始化前驱结点指针
void inThread(binaryTree tree)
{
    if(tree)
    {
        inThread(tree->lChild); // 左子树线索化
        tree->lTag = tree->lChild ? 0:1;
        tree->rTag = tree->rChild ? 0:1;
        if(pre) // 对当前结点及前驱结点线索化
        {
            if(tree->lTag) tree->lChild = pre;
            if(pre->rTag) pre->rChild = tree;
        }
        pre = tree;
        inThread(tree->rChild); // 右子树线索化
    }
}

// 3. 建立中序线索二叉树
void createInThreadTree(binaryTree *tree)
{
    *tree = createTree();
    inThread(*tree);
}

// 4. 寻找中序线索二叉树中p结点的后继结点
treeNode *inNextNode(binaryTree p)
{
    if(p->rTag == 1) return p->rChild;
    p = p->rChild;
    while (p->lTag == 0)
        p = p->lChild;
    return p;
}

// 5. 中序线索二叉树的中序遍历
void inOrder(binaryTree tree)
{
    if(tree)
    {
        while (tree->lTag == 0)
            tree = tree->lChild;
        while (tree)
        {
            printf("%c ",tree->data);
            tree = inNextNode(tree);
        }
    }
}

int main()
{
    binaryTree tree; // 声明二叉树
    printf("请输入结点，创建一颗二叉树，#表示空结点:\n");
    createInThreadTree(&tree); //建立中序线索二叉树 ABD#E##FG###C##
    printf("中序线索二叉树的中序遍历\n");
    inOrder(tree);
    return 0;
}