• 数据结构-难点突破（线索化二叉树与遍历 C++中序线索化二叉树，前序线索二叉树，后序线索二叉树）

    思路来源：数据结构（十七） – C语言版 – 树 - 二叉树的线索化及遍历 – 先序线索化、中序线索化、后序线索化

    文章目录

    1. 中序线索化二叉树

    这里给出上述博客的中序线索化二叉树的大致内容，有什么不懂，可以移步上述博客：

    二叉树的遍历有四种方式：先序遍历、中序遍历、后序遍历、层序遍历。

    那么根据遍历来进行线索化的方式也就有四种方式：先序线索化、中序线索化、后序线索化、层序线索化，其实严格意义上来说，除了遍历的顺序不同，其他的没什么太大的区别。对于线索化来将也是一样的。

    原来的二叉链表的节点中包含了两个指针域（左右指针）、一个数据域，很难确定节点的两个指针域保存的是子树还是线索了。那么为了解决这样的问题，我们需要在结构定义的基础上加入两个标志位（ ltag、rtag ）分别用来表示当前指针的指向的含义。

    ltag=0：节点左子树指向这个节点的左孩子
    ltag=1：节点左子树指向这个节点的前驱

    rtag=0：节点的右子树指向这个节点的右孩子
    rtag=1：节点的右子树指向这个节点的后继

    中序线索化二叉树步骤

    在中序遍历的基础上，将原本遍历函数中输出的语句修改成线索化的代码即可。

    1. 如果当前节点 current 左指针域为空，则需要将其做指针域加上前驱线索
    2. 如果当前节点的上一次访问的节点（ prev 指针）右子树为空，则需要为 prev 指针指向后继节点
    3. 使 prev 指针跟上当前节点指针

    测试中序线索二叉树构造类

    这里为了方便，选择了二叉搜索树的构造方式来创建树

    #include 
#include 

struct TreeNode
{
    int data;
    TreeNode *left = nullptr;
    TreeNode *right = nullptr;
    int ltag = 0;
    int rtag = 0;
    TreeNode(int _data) : data(_data) {}
};

class Tree
{
private:
    void InsertNode(int data)
    {
        if (root == nullptr)
        {
            root = new TreeNode(data);
        }
        else
        {
            TreeNode *prev = nullptr;
            TreeNode *node = root;
            while (node != nullptr)
            {
                prev = node;
                if (node->data >= data)
                {
                    node = node->left;
                }
                else
                {
                    node = node->right;
                }
            }
            TreeNode *next = new TreeNode(data);
            if (prev->data >= data)
            {
                prev->left = next;
            }
            else
            {
                prev->right = next;
            }
        }
    }

    void _InodesDisplay(TreeNode *root)
    {
        if (root == nullptr)
            return;
        _InodesDisplay(root->left);
        std::cout << root->data << " ";
        _InodesDisplay(root->right);
    }

    void Destroy(TreeNode *root)
    {
        if (root == nullptr)
        {
            return;
        }
        Destroy(root->left);
        Destroy(root->right);
        delete root;
    }

public:
    TreeNode *root;

    Tree(const std::vector<int> &vet)
    {
        this->root = nullptr;
        for (int i = 0; i < vet.size(); i++)
        {
            InsertNode(vet[i]);
        }
    }

    ~Tree()
    {
        Destroy(root);
    }

    //中序遍历
    void InodesDisplay()
    {
        _InodesDisplay(root);
        std::cout << "\n";
    }
};

    • 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

    中序线索二叉树实现与测试：

    //思路:https://blog.csdn.net/songshuai0223/article/details/106551499?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166795700016782425681940%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166795700016782425681940&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-106551499-null-null.142^v63^control,201^v3^control_2,213^v2^t3_esquery_v1&utm_term=%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1018.2226.3001.4187

#include "CreatTree.h"

using namespace std;

//中序线索化二叉树
void InorderSpan(TreeNode *root, TreeNode *&prev)
{
    if (root == nullptr)
        return;

    InorderSpan(root->left, prev);

    //当前节点左指针为空，左指针指向前驱
    if (root->left == nullptr)
    {
        root->left = prev;
        root->ltag = 1;
    }
    // prev节点右指针为空，右指针指向当前节点(后继节点)
    if (prev != nullptr && prev->right == nullptr)
    {
        prev->right = root;
        prev->rtag = 1;
    }
    prev = root;

    InorderSpan(root->right, prev);
}

TreeNode *InorderSpan(TreeNode *&root)
{
    TreeNode *ret = root;
    root = nullptr; //摘头，Tree类防止析构函数崩溃
    TreeNode *prev = nullptr;
    InorderSpan(ret, prev);
    return ret;
}

//中序线索化二叉树的遍历

TreeNode *GetNextNode(TreeNode *root)
{
    if (root == nullptr)
    {
        return nullptr;
    }
    // 右标志位 1，可以直接得到后继节点
    if (root->rtag == 1)
    {
        return root->right;
    }
    // 右标志位0，则要找到右子树最左下角的节点
    else
    {
        TreeNode *ret = root->right;
        while (ret != nullptr && ret->ltag == 0)
        {
            ret = ret->left;
        }
        return ret;
    }
}
void DisplayTree(TreeNode *root)
{
    if (root == nullptr)
        return;
    //找最左下的节点
    while (root->ltag == 0)
    {
        root = root->left;
    }
    cout << root->data << " ";
    //根据后继节点打印这颗树
    while (root->right != nullptr)
    {
        root = GetNextNode(root);
        cout << root->data << " ";
    }
}

//释放线索化二叉树的节点
void Destroy(TreeNode *root)
{
    if (root == nullptr)
        return;
    while (root->ltag == 0)
    {
        root = root->left;
    }
    TreeNode *next = root->right;
    delete root;
    root = nullptr;
    while (next != nullptr)
    {
        TreeNode *node = next;
        next = GetNextNode(next);
        delete node;
        node = nullptr;
    }
}

int main(int argc, char const *argv[])
{
    Tree tree({3, 2, 4, 6, 7, 1, 2, 7, 1, 0, 7, 9});
    tree.InodesDisplay();

    TreeNode *ret = InorderSpan(tree.root);
    DisplayTree(ret);
    //销毁线索化二叉树
    Destroy(ret);
    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

    在这里插入图片描述

    2. 前序线索二叉树

    思路和中序线索二叉树类似：

    首先大致递归思路是前序遍历顺序。

    1. 如果当前节点 current 左指针域为空，则需要将其做指针域加上前驱线索
    2. 如果当前节点的上一次访问的节点（ prev 指针）右子树为空，则需要为 prev 指针指向后继节点
    3. 使 prev 指针跟上当前节点指针
    #include "CreatTree.h"

using namespace std;

//前序线索二叉树
void PreorderSpan(TreeNode *root, TreeNode *&prev)
{
    if (root == nullptr)
    {
        return;
    }
    if (root->left == nullptr)
    {
        root->left = prev;
        root->ltag = 1;
    }
    if (prev != nullptr && prev->right == nullptr)
    {
        prev->right = root;
        prev->rtag = 1;
    }
    prev = root;

    //因为是先修改的Node的tag,所以这里需要判断tag，否则会出现死循环
    if (root->ltag == 0)
        PreorderSpan(root->left, prev);
    if (root->rtag == 0)
        PreorderSpan(root->right, prev);
}

TreeNode *PreorderSpan(TreeNode *&root)
{
    TreeNode *prev = nullptr;
    TreeNode *ret = root;
    root = nullptr;
    PreorderSpan(ret, prev);
    return ret;
}

void DisplayTree(TreeNode *root)
{
    if (root == nullptr)
    {
        return;
    }
    while (root != nullptr)
    {
        while (root->ltag == 0)
        {
            cout << root->data << " ";
            root = root->left;
        }
        cout << root->data << " ";
        root = root->right;
    }
}

void Destroy(TreeNode *root)
{
    if (root == nullptr)
    {
        return;
    }
    while (root != nullptr)
    {
        while (root->ltag == 0)
        {
            TreeNode *next = root->left;
            delete root;
            root = next;
        }
        TreeNode *next = root->right;
        delete root;
        root = next;
    }
}

int main(int argc, char const *argv[])
{
    Tree tree({2, 4, 1, 5, 2, 6, 7, 3, 1, 0, 9});
    tree.InodesDisplay();
    TreeNode *node = PreorderSpan(tree.root);
    DisplayTree(node);
    Destroy(node);
    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

    在这里插入图片描述

    3. 后序线索二叉树

    首先按照后序递归的方式进行递归，在打印的步骤出修改成：

    如果当前节点的左子树为空，让左子树指针指向前驱。
    当前节点的右子树为空，让右子树指针指向后继。

    唯一不同的是：在进行遍历线索二叉树时，后序遍历需要记录父节点，这里采用参考博客的思路
    先按照 根节点->右孩子->左孩子 的方式来遍历访问节点，并且将顺序记录一下，最后将刚才记录的顺序翻转即可

    这里选择将反向输出的节点放入栈中达到逆向目的。

    #include "CreatTree.h"

#include 

using namespace std;

//后序线索二叉树
void PostorderSpan(TreeNode *root, TreeNode *&prev)
{
    if (root == nullptr)
        return;
    PostorderSpan(root->left, prev);
    PostorderSpan(root->right, prev);

    if (root->left == nullptr)
    {
        root->left = prev;
        root->ltag = 1;
    }
    if (prev != nullptr && prev->right == nullptr)
    {
        prev->rtag = 1;
        prev->right = root;
    }
    prev = root;
}

TreeNode *PostorderSpan(TreeNode *&root)
{
    TreeNode *ret = root;
    root = nullptr;
    TreeNode *prev = nullptr;
    PostorderSpan(ret, prev);
    return ret;
}

//遍历线索二叉树
//先按照 根节点->右孩子->左孩子 的方式来遍历访问节点，并且将顺序记录一下，最后将刚才记录的顺序翻转即可(使用栈)
TreeNode *GetNextNode(TreeNode *root)
{
    if (root == nullptr)
        return nullptr;

    //将前驱节点返回，最后逆置相当于找后继节点
    if (root->ltag == 1)
    {
        return root->left;
    }
    else
    {
        // root->ltag = 0;有左子树
        if (root->rtag == 1)
        {
            //存在后继节点
            return root->left;
        }
        else if (root->right != nullptr && root->rtag == 0)
        {
            //左右子树都存在，向右子树走
            return root->right;
        }
        else
        {
            return root->left;
        }
    }
}

void DisplayTree(TreeNode *root)
{
    stack<TreeNode *> st;
    while (root != nullptr)
    {
        st.push(root);
        root = GetNextNode(root);
    }

    while (!st.empty())
    {
        cout << st.top()->data << " ";
        st.pop();
    }
}

int main(int argc, char const *argv[])
{
    Tree tree({5, 1, 0, 2});
    tree.InodesDisplay();
    TreeNode *node = PostorderSpan(tree.root);
    DisplayTree(node);
    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

    在这里插入图片描述

  • 相关阅读:
    2023年天津财经大学珠江学院专升本经济学专业课考试大纲
    Java设计模式之原型模式
    操作系统【OS】操作系统结构
    队列和栈的实现和应用
    计算机导论真题（一）
    Stm32_点灯
    在数据分析中，对缺失值解决方案的分析
    大数据讲课笔记3.3 Hadoop集群配置
    项目风险管理的5大关键点，你做了几点？
    11.23Spring 学习第三天
  • 原文地址：https://blog.csdn.net/dodamce/article/details/127764156