1. 首页
  2. 文章中心
  3. # 数据结构考研学习

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

57 阅读 0 评论
我是靠谱客的博主 笨笨铅笔，最近开发中收集的这篇文章主要介绍数据结构-难点突破（线索化二叉树与遍历 C++中序线索化二叉树，前序线索二叉树，后序线索二叉树）1. 中序线索化二叉树2. 前序线索二叉树3. 后序线索二叉树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

文章目录

  • 1. 中序线索化二叉树
  • 2. 前序线索二叉树
  • 3. 后序线索二叉树

1. 中序线索化二叉树

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

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

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

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

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

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

中序线索化二叉树步骤

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

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

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

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

#include <vector>
#include <iostream>

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

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

//思路: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;
}

在这里插入图片描述

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

在这里插入图片描述

3. 后序线索二叉树

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

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

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

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

#include "CreatTree.h"

#include <stack>

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

在这里插入图片描述

最后

以上就是笨笨铅笔为你收集整理的数据结构-难点突破（线索化二叉树与遍历 C++中序线索化二叉树，前序线索二叉树，后序线索二叉树）1. 中序线索化二叉树2. 前序线索二叉树3. 后序线索二叉树的全部内容，希望文章能够帮你解决数据结构-难点突破（线索化二叉树与遍历 C++中序线索化二叉树，前序线索二叉树，后序线索二叉树）1. 中序线索化二叉树2. 前序线索二叉树3. 后序线索二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(38)

相关文章

【图解数据结构】二叉树的概念、性质、结构
【图解数据结构】二叉树的概念、性质、结构
面试中的二叉树题目，java描述
面试中的二叉树题目，java描述
面试大总结：Java搞定面试中的二叉树题目
面试大总结：Java搞定面试中的二叉树题目
408数据结构学习笔记-树-①树的逻辑结构①定义②结点间的关系描述③结点路径④结点，树的属性描述⑤有序树和无序树⑥森林⑦树的性质（6个性质）
408数据结构学习笔记-树-①树的逻辑结构①定义②结点间的关系描述③结点路径④结点，树的属性描述⑤有序树和无序树⑥森林⑦树的性质（6个性质）
数据结构-难点突破（线索化二叉树与遍历 C++中序线索化二叉树，前序线索二叉树，后序线索二叉树）1. 中序线索化二叉树2. 前序线索二叉树3. 后序线索二叉树
数据结构-难点突破（线索化二叉树与遍历 C++中序线索化二叉树，前序线索二叉树，后序线索二叉树）1. 中序线索化二叉树2. 前序线索二叉树3. 后序线索二叉树
（数据结构）已知二叉树的序列求它的形状（用java实现）
（数据结构）已知二叉树的序列求它的形状（用java实现）
数据结构_二叉树_属性-构建-遍历一、二叉树的属性二、二叉树的树节点三、二叉树构建与遍历参考
数据结构_二叉树_属性-构建-遍历一、二叉树的属性二、二叉树的树节点三、二叉树构建与遍历参考
统计叶子结点 21一、题目描述二、解题思路三、完整代码
统计叶子结点 21一、题目描述二、解题思路三、完整代码

评论列表共有 0 条评论

立即
投稿
返回
顶部