(34)王道数据结构-二叉线索树的概念

问题引入

从中序遍历的角度来看，找前驱、后继很不方便；遍历操作必须从根开始

思路

从根节点开始，重新进行一次中序遍历，指针q记录当前访问的节点，指针p记录上一个被访问的结点。
①当q == p时，p为前驱
②当p == p时，q为后继

方案

n个结点的二叉树，有n+1个空链域！可以用来记录前驱、后继的信息。指向前驱、后继的指针称为“线索”

前驱线索: 由左孩子指针充当
后继线索: 由右孩子指针充当

存储结构

1
2
3
4
5
6
//tag称为线索链表
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; //左、右线索标志
} ThreadNode, * ThreadTree;

tag == 0, 表示指针指向孩子
tag == 1, 表示指针是“线索”

需要注意的是，先序线索二叉树是按照“先序序列”进行线索化，后续线索二叉树是按照“后序序列”进行线索化的。

代码实现

中序线索化

代码一：右线索出现了问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<stdio.h>
#include<stdlib.h>
typedef struct ThreadNode {
    char data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;     //左、右线索标志
}ThreadNode, *ThreadTree;

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//为树的当前节点添加左子节点
bool addLeftChild(ThreadTree root, char leftData) {
  //分配新节点
  ThreadTree leftNode = (ThreadTree)malloc(sizeof(ThreadNode));
  //为新节点挂载数据
  leftNode->data = leftData;
  //新节点暂时无子节点
  leftNode->lchild = NULL;
  leftNode->rchild = NULL;
  //将新节点挂到当前节点下
  root->lchild = leftNode;
  return true;
}

//为树的当前节点添加右子节点
bool addRightChild(ThreadTree root, char rightData) {
  //分配新节点
  ThreadTree rightNode = (ThreadTree)malloc(sizeof(ThreadNode));
  //为新节点挂载数据
  rightNode->data = rightData;
  
  //新节点暂时无子节点
  rightNode->lchild = NULL;
  rightNode->rchild = NULL;
  
  //将新节点挂到当前节点下
  root->rchild = rightNode;
  return true;
}

void visit(ThreadNode *q) {
    if (q->lchild == NULL) {    //左字树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = q;    //建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;
    printf("%c ltag=%d rtag=%d\n", q->data,q->ltag,q->rtag);
}

// 中序遍历，一边遍历一边线索化
void InThread(ThreadTree T) {
    if (T != NULL) {
        InThread(T->lchild);    //递归遍历左子树
        visit(T);              //访问根节点
        InThread(T->rchild);   //递归遍历右子树
    }
}

//释放二叉树节点内存
void deltree(ThreadTree tree){
    if (tree != NULL) {
        deltree(tree->lchild);//先往左子树一直寻找
        deltree(tree->rchild);//再往右子树一直寻找
        free(tree); //找不到了free返回上一级
    }
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T) {
    pre = NULL;         //pre初始为NULL
    if (T != NULL) {    //非空二叉树才能线索化
        InThread(T);
        if (pre->rchild == NULL) {
            pre->rtag = 1;  //处理遍历最后一个结点
        }
    }
}

int main() {
  //设定根节点
  ThreadTree root;
  root = (ThreadTree)malloc(sizeof(ThreadNode));
  
  //根节点A
  root->data = 'A';
  addLeftChild(root, 'B');
  addRightChild(root, 'C');
  
  //为B节点增加子节点
  addLeftChild(root->lchild, 'D');
  addRightChild(root->lchild, 'E');
  
  //为D结点添加子结点
  addRightChild(root->lchild->lchild,'G');
  
  //为C节点增加子节点
  addLeftChild(root->rchild, 'F');
  
  //线索化二叉树
  CreateInThread(root);
  
  deltree(root);
  return 0;
}
代码二：无问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <stdlib.h>
#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum {
    Link,
    Thread
}PointerTag;

//结点结构构造
typedef struct ThreadNode {
    TElemType data;//数据域
    struct ThreadNode* lchild, *rchild;//左孩子，右孩子指针域
    PointerTag ltag, rtag;//标志域，枚举类型
}ThreadNode, *ThreadTree;
ThreadTree pre = NULL;

//为树的当前节点添加左子节点
bool addLeftChild(ThreadTree root, char leftData) {
  //分配新节点
  ThreadTree leftNode = (ThreadTree)malloc(sizeof(ThreadNode));
  //为新节点挂载数据
  leftNode->data = leftData;
  //新节点暂时无子节点
  leftNode->lchild = NULL;
  leftNode->rchild = NULL;
  //将新节点挂到当前节点下
  root->lchild = leftNode;
  return true;
}

//为树的当前节点添加右子节点
bool addRightChild(ThreadTree root, char rightData) {
  //分配新节点
  ThreadTree rightNode = (ThreadTree)malloc(sizeof(ThreadNode));
  //为新节点挂载数据
  rightNode->data = rightData;
  
  //新节点暂时无子节点
  rightNode->lchild = NULL;
  rightNode->rchild = NULL;
  
  //将新节点挂到当前节点下
  root->rchild = rightNode;
  return true;
}

//中序对二叉树进行线索化
void InThreading(ThreadTree p) {
    //如果当前结点存在
    if (p != NULL) {
        InThreading(p->lchild);//递归当前结点的左子树，进行线索化
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre
        if (!p->lchild) {
            p->ltag = Thread;
            p->lchild = pre;
        }
        //如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
        if (pre && !pre->rchild) {
            pre->rtag = Thread;
            pre->rchild = p;
        }
        pre = p;//pre指向当前结点
        InThreading(p->rchild);//递归右子树进行线索化
    }
}

//中序遍历线索二叉树
void InThread(ThreadTree p) {
    while (p != NULL) {
        //一直找左孩子，最后一个为中序序列中排第一的
        while (p->ltag == Link) {
            p = p->lchild;
        }
        printf("%c ltag=%d, rtag=%d\n", p->data, p->ltag, p->rtag);  //操作结点数据
        //当结点右标志位为1时，直接找到其后继结点
        while (p->rtag == Thread && p->rchild != NULL) {
            p = p->rchild;
            printf("%c ltag=%d, rtag=%d\n", p->data, p->ltag, p->rtag);
        }
        //否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
        p = p->rchild;
    }
}

int main() {
    ThreadTree root;
    root = (ThreadTree)malloc(sizeof(ThreadNode));
  
    //根节点A
    root->data = 'A';
    addLeftChild(root, 'B');
    addRightChild(root, 'C');
  
    //为B节点增加子节点
    addLeftChild(root->lchild, 'D');
    addRightChild(root->lchild, 'E');
  
    //为D结点添加子结点
    addRightChild(root->lchild->lchild,'G');
  
    //为C节点增加子节点
    addLeftChild(root->rchild, 'F');
    
    InThreading(root);
    printf("中序序列:\n");
    InThread(root);
    return 0;
}

先序线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<stdio.h>
#include<stdlib.h>
typedef struct ThreadNode {
    char data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;     //左、右线索标志
}ThreadNode, *ThreadTree;

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//为树的当前节点添加左子节点
bool addLeftChild(ThreadTree root, char leftData) {
  //分配新节点
  ThreadTree leftNode = (ThreadTree)malloc(sizeof(ThreadNode));
  //为新节点挂载数据
  leftNode->data = leftData;
  //新节点暂时无子节点
  leftNode->lchild = NULL;
  leftNode->rchild = NULL;
  //将新节点挂到当前节点下
  root->lchild = leftNode;
  return true;
}

//为树的当前节点添加右子节点
bool addRightChild(ThreadTree root, char rightData) {
  //分配新节点
  ThreadTree rightNode = (ThreadTree)malloc(sizeof(ThreadNode));
  //为新节点挂载数据
  rightNode->data = rightData;
  
  //新节点暂时无子节点
  rightNode->lchild = NULL;
  rightNode->rchild = NULL;
  
  //将新节点挂到当前节点下
  root->rchild = rightNode;
  return true;
}

void visit(ThreadNode *q) {
    if (q->lchild == NULL) {    //左字树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = q;    //建立前驱结点的后继线索
        pre->rtag = 1;
    }
    printf("%c ltag=%d rtag=%d\n", q->data,q->ltag,q->rtag);
    pre = q;
}

//先序遍历，一边遍历一边线索化
void PreThread(ThreadTree T) {
    if (T != NULL) {
        visit(T);              //访问根节点
        
        if (T->ltag == 0) { //lchild不是前驱线索
            PreThread(T->lchild);
        }
        if (T->rtag == 0) {
            PreThread(T->rchild);
        }
    }
}

//释放二叉树节点内存
void deltree(ThreadTree tree){
    if (tree != NULL) {
        deltree(tree->lchild);//先往左子树一直寻找
        deltree(tree->rchild);//再往右子树一直寻找
        free(tree); //找不到了free返回上一级
    }
}

//先序线索化二叉树T
void CreatePreThread(ThreadTree T) {
    pre = NULL;         //pre初始为NULL
    if (T != NULL) {    //非空二叉树才能线索化
        PreThread(T);
        if (pre->rchild == NULL) {
            pre->rtag = 1;  //处理遍历最后一个结点
        }
    }
}

int main() {
  //设定根节点
  ThreadTree root;
  root = (ThreadTree)malloc(sizeof(ThreadNode));
  
  //根节点A
  root->data = 'A';
  addLeftChild(root, 'B');
  addRightChild(root, 'C');
  
  //为B节点增加子节点
  addLeftChild(root->lchild, 'D');
  addRightChild(root->lchild, 'E');
  
  //为D结点添加子结点
  addRightChild(root->lchild->lchild,'G');
  
  //为C节点增加子节点
  addLeftChild(root->rchild, 'F');
  
  //线索化二叉树
  CreatePreThread(root);
  
  deltree(root);
  return 0;
}

后序线索化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<stdio.h>
#include<stdlib.h>
typedef struct ThreadNode {
    char data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;     //左、右线索标志
}ThreadNode, *ThreadTree;

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//为树的当前节点添加左子节点
bool addLeftChild(ThreadTree root, char leftData) {
  //分配新节点
  ThreadTree leftNode = (ThreadTree)malloc(sizeof(ThreadNode));
  //为新节点挂载数据
  leftNode->data = leftData;
  //新节点暂时无子节点
  leftNode->lchild = NULL;
  leftNode->rchild = NULL;
  //将新节点挂到当前节点下
  root->lchild = leftNode;
  return true;
}

//为树的当前节点添加右子节点
bool addRightChild(ThreadTree root, char rightData) {
  //分配新节点
  ThreadTree rightNode = (ThreadTree)malloc(sizeof(ThreadNode));
  //为新节点挂载数据
  rightNode->data = rightData;
  
  //新节点暂时无子节点
  rightNode->lchild = NULL;
  rightNode->rchild = NULL;
  
  //将新节点挂到当前节点下
  root->rchild = rightNode;
  return true;
}

void visit(ThreadNode *q) {
    if (q->lchild == NULL) {    //左字树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = q;    //建立前驱结点的后继线索
        pre->rtag = 1;
    }
    printf("%c ltag=%d rtag=%d\n", q->data,q->ltag,q->rtag);
    pre = q;
}

// 中序遍历，一边遍历一边线索化
void PostThread(ThreadTree T) {
    if (T != NULL) {
        PostThread(T->lchild);    //递归遍历左子树
        PostThread(T->rchild);   //递归遍历右子树
        visit(T);              //访问根节点
    }
}

//释放二叉树节点内存
void deltree(ThreadTree tree){
    if (tree != NULL) {
        deltree(tree->lchild);//先往左子树一直寻找
        deltree(tree->rchild);//再往右子树一直寻找
        free(tree); //找不到了free返回上一级
    }
}

//中序线索化二叉树T
void CreatePostThread(ThreadTree T) {
    pre = NULL;         //pre初始为NULL
    if (T != NULL) {    //非空二叉树才能线索化
        PostThread(T);
        if (pre->rchild == NULL) {
            pre->rtag = 1;  //处理遍历最后一个结点
        }
    }
}

int main() {
  //设定根节点
  ThreadTree root;
  root = (ThreadTree)malloc(sizeof(ThreadNode));
  
  //根节点A
  root->data = 'A';
  addLeftChild(root, 'B');
  addRightChild(root, 'C');
  
  //为B节点增加子节点
  addLeftChild(root->lchild, 'D');
  addRightChild(root->lchild, 'E');
  
  //为D结点添加子结点
  addRightChild(root->lchild->lchild,'G');
  
  //为C节点增加子节点
  addLeftChild(root->rchild, 'F');
  
  //线索化二叉树
  CreatePostThread(root);
  
  deltree(root);
  return 0;
}
信工核心
#数据结构 #树 #二叉树 #二叉线索树
(34)王道数据结构-二叉线索树的概念
https://www.eldpepar.com/iecore/56134/
作者
EldPepar
发布于
2022年8月5日
许可协议