(35)王道数据结构-二叉线索树前驱后继

中序后继

在中序线索二叉树中找到指定结点*p的中序后继next
①若p->rtag==1，则next = p->rchild
②若p->rtag == 0，指定结点有右孩子
中序遍历====左 根 右
===========左 根 (左 根 右)
===========左 根 ((左 根 右) 根 左)
next = p的右子树种最左下结点

实现代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#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;
}

//找到以P为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p) {
    //循环找到最左下结点(不一定是叶结点)
    while (p->ltag == 0) {
        p = p->lchild;
    }
    return p;
}

//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p) {
    //右子树中最左下结点
    if (p->rtag == 0) {
        return Firstnode(p->rchild);
    } else {
        return p->rchild;   //rtag==1直接返回后继线索
    }
}

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

//中序遍历线索二叉树
void visit(ThreadTree p) {
    printf("%c ltag=%d, rtag=%d\n", p->data, p->ltag, p->rtag); 
}

// 中序遍历
void InThread(ThreadNode *T) {
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p)) {
        visit(p);
    }
}

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

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);
  
  //中序遍历
  InThread(root);
  
  deltree(root);
  return 0;
}

中序前驱

在中序线索二叉树中找到指定结点*p的中序前驱pre
①若p->ltag==1，则pre = p->lchild
②若p->ltag == 0，指定结点有左孩子
中序遍历====左 根 右
===========(左 根 右) 根 右
===========(左 根 (左 根 右)) 根 右
pre = p的左子树中最右下结点

实现代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#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;
}

//找到以P为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p) {
    //循环找到最右下结点(不一定是叶结点)
    while (p->rtag == 0) {
        p = p->rchild;
    }
    return p;
}

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p) {
    //左子树中最右下结点
    if (p->ltag == 0) {
        return Lastnode(p->lchild);
    } else {
        return p->lchild;   //ltag==1直接返回前驱线索
    }
}

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

//中序遍历线索二叉树
void visit(ThreadTree p) {
    printf("---------visit\n");
    printf("%c ltag=%d, rtag=%d\n", p->data, p->ltag, p->rtag); 
}

// 对中序线索二叉树进行逆中序遍历
void RevInorder(ThreadNode *T) {
    for (ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p)) {
        visit(p);
    }
}

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

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);
  
  //中序遍历
  RevInorder(root);
  
  deltree(root);
  return 0;
}

先序后继

在先序线索二叉树中找到指定结点*P的先序后继next
①若p->rtag == 1，则next = p->rchild
②若p->rtag == 0，p必有右孩子
1.假设有左孩子
若p有左孩子，则先序后继为左孩子

先序遍历===根 左 右
==========根 (根 左 右) 右

2.假设无左孩子
若p没有左孩子，则先序后继为右孩子

先序遍历===根 右
==========根 (根 左 右)

先序前驱

在先序线索二叉树中找到指定结点*p的先序前驱pre
①若p->ltag == 1，则next = p->lchild
②若p->ltag == 0，p必有左孩子

先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱

①如果能找到p的付结点，且p是左孩子
先序遍历===根 左 右
==========根 (根 左 右) 右
p的父结点即为其前驱

②如果能找到p的父结点，且p是右孩子，其左兄弟为空
先序遍历===根 右
==========根 (根 左 右)
p到父结点即为其前驱

③如果能找到p的父结点，且p是右孩子，其左兄弟非空
先序遍历===根 左 右
p的前驱为左兄弟子树中最后一个被先序遍历的结点

④如果p是根结点，则p没有先序前驱

后续前驱

在后续线索二叉树中找到指定结点*p的后续前驱pre
①若p->ltag == 1，则pre = p->lchild
②若p->ltag == 0，p必有左孩子

1.假设有右孩子
后续遍历===左 右 根
==========左 (左 右 根) 根
若p有右孩子，则后续前驱为右孩子

2.假设无右孩子
后续遍历===左 根
若p没有右孩子，则后续前驱为左孩子

后续后继

在后续线索二叉树中找到指定结点*p的后续后继next
①若p->rtag == 1，则next = p->rchild
②若p->rtag == 0，p必有左孩子,p必有右孩子

后续遍历===左 右 根
后续遍历中，左右子树中的结点只可能是根的前驱，不可能是后继

①如果能找到p的父结点，且p是右孩子
后续遍历===左 右 根
==========左 (左 右 根) 根(这里p的父结点即为其后继)
改用三叉链表可以找到父结点

②如果能找到p的父结点，且p是左孩子，其左兄弟为空
后续遍历====左 根
===========(左 右 根) 根
p的父结点即为其后继

③如果能找到p的父结点，且p是左孩子，其右兄弟非空
p的后继为右兄弟子树中第一个被后续便利店结点

④如果p是根结点，则p没有后续后继是

信工核心
#数据结构 #树 #二叉树 #二叉线索树
(35)王道数据结构-二叉线索树前驱后继
https://www.eldpepar.com/iecore/35069/
作者
EldPepar
发布于
2022年8月6日
许可协议