前驱后继与线索二叉树

字数统计: 2.3k字 | 阅读时长: 10分

2023-10-01

摘要: 线索树

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

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

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

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

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

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

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

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

节点定义

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

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);
}

在中序线索树上中序遍历

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

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 有左子节点。根据中序遍历的定义，其前驱是左子树的最右节点。

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 有右子节点。根据中序遍历的定义，其后继是右子树的最左节点。

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++)

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;
}

测试

94. 二叉树的中序遍历

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++)

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;
};

算法：线索树

先建立线索树，然后 next 和 hasNext 均通过线索树的后继查询来做。

代码 (C++)

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);
        }
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法数据结构

前驱后继与线索二叉树

节点定义

接口定义

中序线索化

在中序线索树上中序遍历

查询中序前驱

查询中序后继

完整代码 (C++)

测试

173. 二叉搜索树迭代器

算法：非递归中序遍历

代码 (C++)

算法：线索树

代码 (C++)