1
// 线索二叉树结点
2
/*
3
ltag：0 lchild指向该节点的孩子；1 lchild指向该节点的前驱
4
rtag：0 rchild指向该节点的孩子；1 rchild指向该节点的后继
5
*/
6
typedef struct
7
{
8
    int value;
9
    struct ThrNode *lchild, *rchild;
10
    int ltag, rtag;
11
}ThrNode;
12

13
// 创建线索树结点
14
/*
15
value：结点的值
16
*/
17
ThrNode* thrNode_createNode(int value)
18
{
19
    ThrNode* node = (ThrNode* )malloc(sizeof(ThrNode));
20
    // 初始化
21
    node->ltag = 0;
22
    node->rtag = 0;
23
    node->lchild = NULL;
24
    node->rchild = NULL;
25
    node->value = value;
26
    return node;
27
}

1
// 递归用数组没带线索的树
2
// 用数组表示的二叉树，值为0表示没有这个节点
3
/*
4
arr：二叉树数组
5
len：数组长度
6
*/
7
ThrNode* thrNode_createTreeByArr(int* arr, int len)
8
{
9
    ThrNode* root = thrNode_createNode(arr[0]);
10
    thrNode_createTreeByArr_main(arr, len, 1, root ,'l');
11
    thrNode_createTreeByArr_main(arr, len, 2, root ,'r');
12
    return root;
13
}
14

15
// 递归创建二叉树
16
/*
17
arr：二叉树数组
18
len：数组长度
19
i：当前结点在arr中的索引
20
parent：当前结点的双亲
21
RorL：当前结点是左子树还是右子树
22
*/
23
void thrNode_createTreeByArr_main(int* arr,int len, int i, ThrNode* parent, char RorL)
24
{
25
    if(i >= len || arr[i]==0)
26
    {
27
        // 越界了或没有结点
28
        return;
29
    }
30

31
    ThrNode* node = thrNode_createNode(arr[i]);
32
    if(RorL == 'r')
33
    {
34
        parent->rchild = node;
35
    }
36
    else
37
    {
38
        parent->lchild = node;
39
    }
40
    thrNode_createTreeByArr_main(arr, len, 2*(i+1)-1, node, 'l');
41
    thrNode_createTreeByArr_main(arr, len, 2*(i+1), node, 'r');
42
}

1
// 递归生成中序线索
2
void thrNode_thrTree(ThrNode* root)
3
{
4
    thrNode_thrTree_main(root, NULL);
5
}
6

7
// 执行函数
8
/*
9
cur：需要用来建立线索的主要结点
10
pre：cur的双亲
11
*/
12
void thrNode_thrTree_main(ThrNode* cur, ThrNode* pre)
13
{
14
    // 递归结束条件
15
    if(cur == NULL) return;
16

17
    // 左子树线索化
18
    thrNode_thrTree_main(cur->lchild, pre);
19

20
    // 当左子树为空，要指向前驱
21
    if(cur->lchild == NULL)
22
    {
23
        // 如果有前驱
24
        /*
25
        中序线索二叉树中，
26
        第一个输出的结点没有前驱，
27
        最后一个输出的结点没有后继
28
        */
29
        if(pre)
30
        {
31
            // 建立前驱线索
32
            cur->lchild = pre;
33
            cur->ltag = 1;
34
            printf("建立前驱 %d -> %d\n", cur->value, pre->value, cur->ltag);
35
        }
36
    }
37
    else
38
    {
39
        // 如果有左子树，那么cur结点就是左子树最右结点的后继
40
        ThrNode* tmp = cur->lchild;
41
        while(tmp->rchild)
42
        {
43
            tmp = tmp->rchild;
44
        }
45
        tmp->rchild = cur;
46
        tmp->rtag = 1;
47
        printf("建立后继 %d -> %d\n", tmp->value, cur->value, tmp->rtag);
48
    }
49

50
    // 右子树线索化
51
    thrNode_thrTree_main(cur->rchild, cur);
52
}

1
// 中序线索树的遍历
2

3
/*
4
root：要遍历的中序线索二叉树
5
printStr：输出结点值的格式
6
startStr：遍历前要输出的字符串
7
endStr：遍历结束后要输出的字符串
8
*/
9
void thrNode_thrTree_inOrder(ThrNode* root, char* printStr, char* startStr, char* endStr)
10
{
11
    printf(startStr);
12

13
    // 先找到中序遍历第一个结点，并输出
14
    while(root->ltag == 0 && root->lchild)
15
    {
16
        root = root->lchild;
17
    }
18
    printf(printStr, root->value);
19

20
    //当右子树不为空，循环
21
    /*
22
    因为是线索二叉树，所以只有最后一个输出的结点没有后继，
23
    也就是右孩子，其他结点的右孩子是真右孩子或后继结点
24
    */
25
    while(root->rchild != NULL)
26
    {
27
        // 右孩子是后继结点
28
        if(root->rtag == 1)
29
        {
30
            // 可以直接得到下一个结点
31
            root = root->rchild;
32
        }
33
        else
34
        {
35
            // 右孩子不是后继结点
36
            // 找右子树的最左结点
37
            root = root->rchild;
38
            while(root->ltag == 0)
39
            {
40
                root = root->lchild;
41
            }
42
        }
43
        // 输出
44
        printf(printStr, root->value);
45
    }
46

47
    printf(endStr);
48
}

1
// 线索二叉树的普通中序遍历
2
/*
3
root：要遍历的二叉树
4
printStr：输出格式
5
*/
6
void thrNode_inOrder(ThrNode* root, char* printStr)
7
{
8
    thrNode_inOrder_main(root, 0, printStr);
9
}
10

11
// 递归函数
12
/*
13
root：要遍历的二叉树
14
tag：当前结点是不是线索节点
15
printStr：输出格式
16
*/
17
void thrNode_inOrder_main(ThrNode* root, int tag, char* printStr)
18
{
19
    // 如果当前节点为空或是线索节点，返回
20
    if(root == NULL || tag == 1) return;
21
    thrNode_inOrder_main(root->lchild, root->ltag, printStr);
22
    printf(printStr, root->value);
23
    thrNode_inOrder_main(root->rchild, root->rtag, printStr);
24
}

1
#define N 15
2

3
int main()
4
{
5
    int arr[N] = {1,2,3,0,4,6,0,0,0,5,0,0,7,0,0};
6

7
    ThrNode* root = thrNode_createTreeByArr(arr, N);
8
    thrNode_thrTree(root);
9
    thrNode_thrTree_inOrder(root, "%d ", "线索中序遍历：", "\n");
10
    printf("普通中序遍历：");
11
    thrNode_inOrder(root, "%d ");
12

13
    return 0;
14
}