前驱后继与线索二叉树

  |  

摘要: 线索树

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


对树进行遍历的过程中,会产生一个遍历序,参考文章 遍历序的基本概念与性质。基于这个遍历序,每个节点都有一个前驱节点与后继节点。

在实际问题中,经常需要求某节点在某种次序下的前驱或后继节点,参考文章 二叉查找树的中序遍历和前驱后继。对于二叉树来说,给定一个节点如何快速得到其在某种序下的前驱和后继,比较好想的有以下几种方法解决:

  • 按照指定次序的遍历方法,遍历一遍,发现节点的前驱和后继。这样的话每次查询都需要从根节点开始按给定的序遍历一遍。时间复杂度为 $O(N)$。
  • 在二叉树节点中增设前驱指针和后继指针,分别指示该节点在某种序下的前驱和后继。这样可以非常方便 $O(1)$ 地查询,但是需要额外的空间。

利用二叉链表中的空指针域,将二叉链表中的空的指针域改为指向其前驱和后继,是一种办法。空的左指针指向其前驱、空的右指针指向其后继,这种指针称为线索。所得到的二叉树被称为线索二叉树,将二叉树转变成线索二叉树的过程称为线索化

Morris遍历与Morris序 中,进行 Morris 遍历的时候涉及到线索的连接和断开,但是只涉及到 Morris 序的后继。

本文以中序遍历为例,看看在二叉树的基础上,如何进行线索化。在线索化之后,可以查询任意节点的前驱和后继,以及可以在空间复杂度为 $O(1)$ 的情况下进行中序遍历。线索树中对节点的插入删除比较复杂,本文不涉及。

在实现线索树 InOrderThreadTree 后,我们用它解决 173. 二叉搜索树迭代器

节点定义

由于需要区分 node -> leftnode -> right 是指针还是线素,增加两个区分标志 ltag, rtag,true 表示线索、false 表示指针。

1
2
3
4
5
6
7
8
struct ThreadNode
{
int val;
ThreadNode *left, *right;
bool ltag, rtag;
ThreadNode(){}
ThreadNode(int val):val(val),left(nullptr),right(nullptr),ltag(false),rtag(false){}
};

接口定义

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
class ThreadTree
{
public:
ThreadTree(){}
ThreadTree(ThreadNode *node)
{
root = node;
}
~ThreadTree()
{
if(root)
delete_sub_tree(root);
}
void inOrder_thread(); // 线索化
vector<int> inOrder_traversal(); // 中序遍历中序线索二叉树
ThreadNode* inOrder_precursor(ThreadNode* node); // 查询前驱
ThreadNode* inOrder_successor(ThreadNode* node); // 查询后继

private:
ThreadNode *root; //根结点指针

void _inOrder(ThreadNode* node, ThreadNode*& precursor);

void delete_sub_tree(ThreadNode* node)
{
if(node -> left)
delete_sub_tree(node -> left);
if(node -> right)
delete_sub_tree(node -> right);
delete node;
node = nullptr;
}
};

中序线索化

在中序遍历过程中维护前驱节点,参考文章 中序遍历过程中通过引用维护前驱

在处理当前节点时,建立其前驱线索和后继线索。

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
void ThreadTree::inOrder_thread()
{
ThreadNode *precursor = nullptr;
_inOrder(root, precursor);
}

void ThreadTree::_inOrder(ThreadNode* node, ThreadNode*& precursor)
{
if(node -> left)
_inOrder(node -> left, precursor);

// 建立前驱线索
if(!node -> left)
{
node -> ltag = true;
node -> left = precursor;
}
// 建立后继线索
if(precursor && !precursor -> right)
{
precursor -> rtag = true;
precursor -> right = node;
}

precursor = node;
if(node -> right)
_inOrder(node -> right, precursor);
}

在中序线索树上中序遍历

通常进行中序遍历时,需要一个 $O(h)$ 的额外空间来保存栈。而在线索树中,从第一个节点开始,依次访问后缀即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> ThreadTree::inOrder_traversal()
{
if(!root)
return {};
vector<int> result;
ThreadNode *node = root;
// 找起始节点
while(!node -> ltag)
node = node -> left;
// 遍历
while(node)
{
// 访问当前节点 node
result.push_back(node -> val);
node = inOrder_successor(node);
}
return result;
}

查询中序前驱

  • 如果 node -> ltag 为 true,那么其左指针指向的结点便是 node 的前驱。
  • 如果 node -> ltag 为 false,则表明 node 有左子节点。根据中序遍历的定义,其前驱是左子树的最右节点。
1
2
3
4
5
6
7
8
9
ThreadNode* ThreadTree::inOrder_precursor(ThreadNode* node)
{
if(node -> ltag)
return node -> left;
ThreadNode *precursor = node -> left;
while(precursor && !precursor -> rtag)
precursor = precursor -> right;
return precursor;
}

查询中序后继

  • 如果 node -> rtag 为 true,那么其右指针指向的结点便是 node 的后继。
  • 如果 node -> rtag 为 false,则表明 node 有右子节点。根据中序遍历的定义,其后继是右子树的最左节点。
1
2
3
4
5
6
7
8
9
ThreadNode* ThreadTree::inOrder_successor(ThreadNode* node)
{
if(node -> rtag)
return node -> right;
ThreadNode *successor = node -> right;
while(successor && !successor -> ltag)
successor = successor -> left;
return successor;
}

完整代码 (C++)

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
struct ThreadNode
{
int val;
ThreadNode *left, *right;
bool ltag, rtag;
ThreadNode(){}
ThreadNode(int val):val(val),left(nullptr),right(nullptr),ltag(false),rtag(false){}
};


class ThreadTree
{
public:
ThreadTree(){}
ThreadTree(ThreadNode *node)
{
root = node;
}
~ThreadTree()
{
if(root)
delete_sub_tree(root);
}
void inOrder_thread(); // 线索化
vector<int> inOrder_traversal(); // 中序遍历中序线索二叉树
ThreadNode* inOrder_precursor(ThreadNode* node); // 查询前驱
ThreadNode* inOrder_successor(ThreadNode* node); // 查询后继

private:
ThreadNode *root; //根结点指针

void _inOrder(ThreadNode* node, ThreadNode*& precursor);

void delete_sub_tree(ThreadNode* node)
{
if(node -> left)
delete_sub_tree(node -> left);
if(node -> right)
delete_sub_tree(node -> right);
delete node;
node = nullptr;
}
};

void ThreadTree::inOrder_thread()
{
ThreadNode *precursor = nullptr;
_inOrder(root, precursor);
}

void ThreadTree::_inOrder(ThreadNode* node, ThreadNode*& precursor)
{
if(node -> left)
_inOrder(node -> left, precursor);

// 建立前驱线索
if(!node -> left)
{
node -> ltag = true;
node -> left = precursor;
}
// 建立后继线索
if(precursor && !precursor -> right)
{
precursor -> rtag = true;
precursor -> right = node;
}

precursor = node;
if(node -> right)
_inOrder(node -> right, precursor);
}

vector<int> ThreadTree::inOrder_traversal()
{
if(!root)
return {};
vector<int> result;
ThreadNode *node = root;
// 找起始节点
while(!node -> ltag)
node = node -> left;
// 遍历
while(node)
{
// 访问当前节点 node
result.push_back(node -> val);
node = inOrder_successor(node);
}
return result;
}

ThreadNode* ThreadTree::inOrder_precursor(ThreadNode* node)
{
if(node -> ltag)
return node -> left;
ThreadNode *precursor = node -> left;
while(precursor && !precursor -> rtag)
precursor = precursor -> right;
return precursor;
}

ThreadNode* ThreadTree::inOrder_successor(ThreadNode* node)
{
if(node -> rtag)
return node -> right;
ThreadNode *successor = node -> right;
while(successor && !successor -> ltag)
successor = successor -> left;
return successor;
}

测试

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
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(!root)
return {};
ThreadNode *thread_root = new ThreadNode(root -> val);
build(root, thread_root);
ThreadTree *thread_tree = new ThreadTree(thread_root);
thread_tree -> inOrder_thread();
return thread_tree -> inOrder_traversal();
}

void build(TreeNode* node, ThreadNode* thread_node)
{
if(node -> left)
{
thread_node -> left = new ThreadNode(node -> left -> val);
build(node -> left, thread_node -> left);
}
if(node -> right)
{
thread_node -> right = new ThreadNode(node -> right -> val);
build(node -> right, thread_node -> right);
}
}
};

173. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器:

  • BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。
  • boolean hasNext() 如果向指针右侧遍历存在数字,则返回 true ;否则返回 false 。
  • int next()将指针向右移动,然后返回指针处的数字。

注意,指针初始化为一个不存在于 BST 中的数字,所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 的中序遍历中至少存在一个下一个数字。

提示:

1
2
3
树中节点的数目在范围 [1, 1e5] 内
0 <= Node.val <= 1e6
最多调用 1e5 次 hasNext 和 next 操作

示例:
输入
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False

进阶:

你可以设计一个满足下述条件的解决方案吗?next() 和 hasNext() 操作均摊时间复杂度为 O(1) ,并使用 O(h) 内存。其中 h 是树的高度。

算法:非递归中序遍历

在非递归中序遍历的基础上稍作修改。

代码 (C++)

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
class BSTIterator {
public:
BSTIterator(TreeNode* root) {
while(root)
{
st.push(root);
root = root -> left;
}
}

/** @return the next smallest number */
int next() {
if(!hasNext())
return -1;
TreeNode *cur = st.top();
int result = cur -> val;
st.pop();
cur = cur -> right;
while(cur)
{
st.push(cur);
cur = cur -> left;
}
return result;
}

/** @return whether we have a next smallest number */
bool hasNext() {
return(!st.empty());
}

private:
stack<TreeNode*> st;
};

算法:线索树

先建立线索树,然后 nexthasNext 均通过线索树的后继查询来做。

代码 (C++)

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
class BSTIterator {
public:
BSTIterator(TreeNode* root) {
ThreadNode *thread_root = new ThreadNode(root -> val);
build(root, thread_root);
thread_tree = new ThreadTree(thread_root);
thread_tree -> inOrder_thread();
iter = thread_root;
while(!iter -> ltag)
iter = iter -> left;
}

int next() {
if(!hasNext())
return -1;
int ans = iter -> val;
iter = thread_tree -> inOrder_successor(iter);
return ans;
}

bool hasNext() {
return iter != nullptr;
}

private:
ThreadTree *thread_tree;
ThreadNode *iter;

void build(TreeNode* node, ThreadNode* thread_node)
{
if(node -> left)
{
thread_node -> left = new ThreadNode(node -> left -> val);
build(node -> left, thread_node -> left);
}
if(node -> right)
{
thread_node -> right = new ThreadNode(node -> right -> val);
build(node -> right, thread_node -> right);
}
}
};

Share