【数据结构】69_二叉树的线索化实现

拓朴棱镜
• 阅读 1038

什么是线索化二叉树

  • 将二叉树转换为双向链表的过程（非线性 → 线性）

  • 能够反映某种二叉树的遍历次序（结点的先后访问次序）

    • 利用结点的 right 指针指向遍历中的后继结点
    • 利用结点的 left 指针指向遍历中的前驱结点

如何对二叉树进行线索化

思维过程

【数据结构】69_二叉树的线索化实现

二叉树的线索化

【数据结构】69_二叉树的线索化实现

课程目标

  • 新增功能函数 traversal(order, queue)
  • 新增遍历方式 BTTraversal::LevelOrder
  • 新增公有函数 BTreeNode<T> *thread(BTTraversal order)

新增功能函数

编程实验：新增功能函数

void traversal(BTTraversal order, LinkQueue<BTreeNode<T>*> &queue) const
{
    switch (order)
    {
        case PreOrder:
            PreOrderTraversal(root(), queue);
            break;
        case InOrder:
            InOrderTraversal(root(), queue);
            break;
        case PostOrder:
            PostOrderTraversal(root(), queue);
            break;
    }
}

新增层次遍历

层次遍历算法小结

  • 将根结点压入队列中
  • 访问队头元素指向的二叉树结点
  • 队头元素弹出，将队头元素的孩子结点压入队列
  • 判断队列是否为空（非空：转第2条；空：结束）

层次遍历算法示例

【数据结构】69_二叉树的线索化实现

【数据结构】69_二叉树的线索化实现

编程实验：层次遍历算法

void LevelOrderTraversal(BTreeNode<T> *node, LinkQueue<BTreeNode<T>*> &queue) const
{
    if (node != nullptr)
    {
        LinkQueue<BTreeNode<T>*> tmp;

        tmp.add(node);

        while (tmp.length() > 0)
        {
            BTreeNode<T> *n = tmp.front();

            if (n->left != nullptr)
            {
                tmp.add(n->left);
            }

            if (n->right != nullptr)
            {
                tmp.add(n->right);
            }

            tmp.remove();
            queue.add(n);
        }
    }
}

新增线索化实现

函数接口设计

  • BTreeNode<T> *thread(BTTraversal order)

    • 根据参数 order 选择线索化的次序（先序，中序，后序 ，层次）
    • 返回线索化之后指向链表首结点的指针
    • 线索化执行结束之后对应的二叉树变为空树

线索化流程

【数据结构】69_二叉树的线索化实现

队列中结点的连接算法

【数据结构】69_二叉树的线索化实现

编程实验：二叉树的线索化

BTreeNode<T> *connect(LinkQueue<BTreeNode<T>*> &queue)
{
    BTreeNode<T> *ret = nullptr;

    if (queue.length() > 0)
    {
        ret = queue.front();

        BTreeNode<T> *slider = queue.front();

        queue.remove();

        slider->left = nullptr;

        while (queue.length() > 0)
        {
            slider->right = queue.front();
            queue.front()->left = slider;

            slider = queue.front();
            queue.remove();
        }

        slider->right = nullptr;
    }

    return ret;
}

BTreeNode<T> *thread(BTTraversal order)
{
    BTreeNode<T> *ret = nullptr;

    LinkQueue<BTreeNode<T>*> queue;

    traversal(order, queue);

    ret = connect(queue);

    this->m_root = nullptr;

    m_queue.clear();

    return ret;
}

文件：BTree.h

#ifndef BTREE_H
#define BTREE_H

#include "Tree.h"
#include "BTreeNode.h"
#include "Exception.h"
#include "LinkQueue.h"
#include "DynamicArray.h"

namespace DTLib
{

enum BTTraversal
{
    PreOrder,
    InOrder,
    PostOrder,
    LevelOrder
};

template <typename T>
class BTree : public Tree<T>
{
public:
    BTree() = default;

    bool insert(TreeNode<T> *node) override
    {
        return insert(node, ANY);
    }

    virtual bool insert(TreeNode<T> *node, BTNodePos pos)
    {
        bool ret = true;

        if (node != nullptr)
        {
            if (this->m_root == nullptr)
            {
                node->parent = nullptr;
                this->m_root = node;
            }
            else
            {
                BTreeNode<T> *np = find(node->parent);

                if (np != nullptr)
                {
                    ret = insert(dynamic_cast<BTreeNode<T>*>(node), np, pos);
                }
                else
                {
                    THROW_EXCEPTION(InvalidParameterExcetion, "Invalid parent tree node ...");
                }
            }
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Parameter can not be null ...");
        }

        return ret;
    }

    bool insert(const T &value, TreeNode<T> *parent) override
    {
        return insert(value, parent, ANY);
    }

    virtual bool insert(const T &value, TreeNode<T> *parent, BTNodePos pos)
    {
        bool ret = true;
        BTreeNode<T> *node = BTreeNode<T>::NewNode();

        if (node != nullptr)
        {
            node->value = value;
            node->parent = parent;

            ret = insert(node, pos);

            if (!ret)
            {
                delete node;
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create node ...");
        }

        return ret;
    }

    SharedPointer<Tree<T>> remove(const T &value) override
    {
        BTree<T> *ret = nullptr;

        BTreeNode<T> *node = find(value);

        if (node != nullptr)
        {
            remove(node, ret);

            m_queue.clear();
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Can not find the tree node via value ...");
        }

        return ret;
    }

    SharedPointer<Tree<T>> remove(TreeNode<T> *node) override
    {
        BTree<T> *ret = nullptr;

        node = find(node);

        if (node != nullptr)
        {
            remove(dynamic_cast<BTreeNode<T>*>(node), ret);

            m_queue.clear();
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Parameter node is invalid ...");
        }

        return ret;
    }

    BTreeNode<T>* find(const T &value) const override
    {
        return find(root(), value);
    }

    BTreeNode<T>* find(TreeNode<T> *node) const override
    {
        return find(root(), dynamic_cast<BTreeNode<T>*>(node));
    }

    BTreeNode<T>* root() const override
    {
        return dynamic_cast<BTreeNode<T>*>(this->m_root);
    }

    int degree() const override
    {
        return degree(root());
    }

    int count() const override
    {
        return count(root());
    }

    int height() const override
    {
        return height(root());
    }

    void clear() override
    {
        free(root());

        this->m_root = nullptr;
    }

    bool begin() override
    {
        bool ret = (root() != nullptr);

        if (ret)
        {
            m_queue.clear();
            m_queue.add(root());
        }

        return ret;
    }

    bool end() override
    {
        return (m_queue.length() == 0);
    }

    bool next() override
    {
        bool ret = (m_queue.length() > 0);

        if (ret)
        {
            BTreeNode<T> *node = m_queue.front();

            m_queue.remove();

            if (node->left != nullptr)
            {
                m_queue.add(node->left);
            }

            if (node->right != nullptr)
            {
                m_queue.add(node->right);
            }
        }

        return ret;
    }

    T current() override
    {
        if (!end())
        {
            return m_queue.front()->value;
        }
        else
        {
            THROW_EXCEPTION(InvalidOpertionExcetion, "No value at current position ...");
        }
    }

    SharedPointer<DynamicArray<T>> traversal(BTTraversal order) const
    {
        DynamicArray<T> *ret = nullptr;
        LinkQueue<BTreeNode<T>*> queue;

        traversal(order, queue);

        ret = new DynamicArray<T>(queue.length());

        if (ret != nullptr)
        {
            for (int i=0; i<ret->length(); ++i, queue.remove())
            {
                ret->set(i, queue.front()->value);
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough to create return array ...");
        }

        return ret;
    }

    BTreeNode<T> *thread(BTTraversal order)
    {
        BTreeNode<T> *ret = nullptr;

        LinkQueue<BTreeNode<T>*> queue;

        traversal(order, queue);

        ret = connect(queue);

        this->m_root = nullptr;

        m_queue.clear();

        return ret;
    }

    SharedPointer<BTree<T>> clone() const
    {
        BTree<T> *ret = new BTree<T>();

        if (ret != nullptr)
        {
            ret->m_root = clone(root());
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create new tree ...");
        }

        return ret;
    }

    bool operator == (const BTree<T> &btree) const
    {
        return equal(root(), btree.root());
    }

    bool operator != (const BTree<T> &btree) const
    {
        return !(*this == btree);
    }

    SharedPointer<BTree<T>> add(const BTree<T> &btree) const
    {
        BTree<T> *ret = new BTree<T>();

        if (ret != nullptr)
        {
            ret->m_root = add(root(), btree.root());
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create new tree ...");
        }

        return ret;
    }

    ~BTree()
    {
        clear();
    }

protected:
    LinkQueue<BTreeNode<T>*> m_queue;

    BTree(const BTree<T>&) = default;
    BTree<T>& operator = (const BTree<T>&) = default;

    virtual BTreeNode<T>* find(BTreeNode<T> *node, const T &value) const
    {
        BTreeNode<T> *ret = nullptr;

        if (node != nullptr)
        {
            if (node->value == value)
            {
                ret = node;
            }
            else
            {
                if (ret == nullptr)
                {
                    ret = find(node->left, value);
                }

                if (ret == nullptr)
                {
                    ret = find(node->right, value);
                }
            }
        }

        return ret;
    }

    virtual BTreeNode<T>* find(BTreeNode<T> *node, BTreeNode<T> *obj) const
    {
        BTreeNode<T> *ret = nullptr;

        if (node == obj)
        {
            ret = node;
        }
        else
        {
            if (node != nullptr)
            {
                if (ret == nullptr)
                {
                    ret = find(node->left, obj);
                }

                if (ret == nullptr)
                {
                    ret = find(node->right, obj);
                }
            }
        }

        return ret;
    }

    virtual bool insert(BTreeNode<T> *node, BTreeNode<T> *np, BTNodePos pos)
    {
        bool ret = true;

        if (pos == ANY)
        {
            if (np->left == nullptr)
            {
                np->left = node;
            }
            else if (np->right == nullptr)
            {
                np->right = node;
            }
            else
            {
                ret = false;
            }
        }
        else if (pos == LEFT)
        {
            if (np->left == nullptr)
            {
                np->left = node;
            }
            else
            {
                ret = false;
            }
        }
        else if (pos == RIGHT)
        {
            if (np->right == nullptr)
            {
                np->right = node;
            }
            else
            {
                ret = false;
            }
        }

        return ret;
    }

    virtual void remove(BTreeNode<T> *node, BTree<T> *&ret)
    {
        ret = new BTree<T>();

        if (ret != nullptr)
        {
            if (root() == node)
            {
                this->m_root = nullptr;
            }
            else
            {
                BTreeNode<T> *parent = dynamic_cast<BTreeNode<T>*>(node->parent);

                if (node == parent->left)
                {
                    parent->left = nullptr;
                }
                else if (node == parent->right)
                {
                    parent->right = nullptr;
                }

                node->parent = nullptr;
            }

            ret->m_root = node;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create btree ...");
        }
    }

    virtual void free(BTreeNode<T> *node)
    {
        if (node != nullptr)
        {
            free(node->left);
            free(node->right);

            if (node->flag())
            {
                delete node;
            }
        }
    }

    int count(BTreeNode<T> *node) const
    {
        return (node != nullptr) ? (count(node->left) + count(node->right) + 1) : 0;
    }

    int height(BTreeNode<T> *node) const
    {
        int ret = 0;

        if (node != nullptr)
        {
            int lh = height(node->left);
            int rh = height(node->right);

            ret = ((lh > rh) ? lh : rh) + 1;
        }

        return ret;
    }

    int degree(BTreeNode<T> *node) const
    {
        int ret = 0;

        if (node != nullptr)
        {
            BTreeNode<T> *child[] = {node->left, node->right};
            ret = !!node->left + !!node->left;

            for (int i=0; (i<2) && (ret<2); ++i)
            {
                int d = degree(child[i]);

                if (ret < d)
                {
                    ret = d;
                }
            }
        }

        return ret;
    }

    void traversal(BTTraversal order, LinkQueue<BTreeNode<T>*> &queue) const
    {
        switch (order)
        {
            case PreOrder:
                PreOrderTraversal(root(), queue);
                break;
            case InOrder:
                InOrderTraversal(root(), queue);
                break;
            case PostOrder:
                PostOrderTraversal(root(), queue);
                break;
            case LevelOrder:
                LevelOrderTraversal(root(), queue);
                break;
        }
    }

    void PreOrderTraversal(BTreeNode<T> *node, LinkQueue<BTreeNode<T>*> &queue) const
    {
        if (node != nullptr)
        {
            queue.add(node);
            PreOrderTraversal(node->left, queue);
            PreOrderTraversal(node->right, queue);
        }
    }

    void InOrderTraversal(BTreeNode<T> *node, LinkQueue<BTreeNode<T>*> &queue) const
    {
        if (node != nullptr)
        {
            InOrderTraversal(node->left, queue);
            queue.add(node);
            InOrderTraversal(node->right, queue);
        }
    }

    void PostOrderTraversal(BTreeNode<T> *node, LinkQueue<BTreeNode<T>*> &queue) const
    {
        if (node != nullptr)
        {
            PostOrderTraversal(node->left, queue);
            PostOrderTraversal(node->right, queue);
            queue.add(node);
        }
    }

    void LevelOrderTraversal(BTreeNode<T> *node, LinkQueue<BTreeNode<T>*> &queue) const
    {
        if (node != nullptr)
        {
            LinkQueue<BTreeNode<T>*> tmp;

            tmp.add(node);

            while (tmp.length() > 0)
            {
                BTreeNode<T> *n = tmp.front();

                if (n->left != nullptr)
                {
                    tmp.add(n->left);
                }

                if (n->right != nullptr)
                {
                    tmp.add(n->right);
                }

                tmp.remove();
                queue.add(n);
            }
        }
    }

    BTreeNode<T> *connect(LinkQueue<BTreeNode<T>*> &queue)
    {
        BTreeNode<T> *ret = nullptr;

        if (queue.length() > 0)
        {
            ret = queue.front();

            BTreeNode<T> *slider = queue.front();

            queue.remove();

            slider->left = nullptr;

            while (queue.length() > 0)
            {
                slider->right = queue.front();
                queue.front()->left = slider;

                slider = queue.front();
                queue.remove();
            }

            slider->right = nullptr;
        }

        return ret;
    }

    BTreeNode<T> *clone(BTreeNode<T> *node) const
    {
        BTreeNode<T> *ret = nullptr;

        if (node != nullptr)
        {
            ret = BTreeNode<T>::NewNode();

            if (ret != nullptr)
            {
                ret->value = node->value;
                ret->left = clone(node->left);
                ret->right = clone(node->right);

                if (ret->left != nullptr)
                {
                    ret->left->parent = ret;
                }

                if (ret->right != nullptr)
                {
                    ret->right->parent = ret;
                }
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create new node ...");
            }
        }

        return ret;
    }

    bool equal(BTreeNode<T> *lh, BTreeNode<T> *rh) const
    {
        if (lh == rh)
        {
            return true;
        }
        else if ((lh != nullptr) && (rh != nullptr))
        {
            return (lh->value == rh->value) && equal(lh->left, rh->left) && equal(lh->right, rh->right);
        }
        else
        {
            return false;
        }
    }

    BTreeNode<T> *add(BTreeNode<T> *lh, BTreeNode<T> *rh) const
    {
        BTreeNode<T> *ret = nullptr;

        if ((lh != nullptr) && (rh == nullptr))
        {
            ret = clone(lh);
        }
        else if ((lh == nullptr) && (rh != nullptr))
        {
            ret = clone(rh);
        }
        else if ((lh != nullptr) && (rh != nullptr))
        {
            ret = BTreeNode<T>::NewNode();

            if (ret != nullptr)
            {
                ret->value = lh->value + rh->value;
                ret->left = add(lh->left, rh->left);
                ret->right = add(lh->right, rh->right);

                if (ret->left != nullptr)
                {
                    ret->left->parent = ret;
                }

                if (ret->right != nullptr)
                {
                    ret->right->parent = ret;
                }
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create new node ...");
            }
        }

        return ret;
    }
};

}

#endif // BTREE_H

文件:main.cpp

#include <iostream>
#include "BTreeNode.h"
#include "BTree.h"

using namespace std;
using namespace DTLib;

int main()
{
    BTree<int> bt;
    BTreeNode<int> *n = nullptr;

    bt.insert(1, nullptr);

    n = bt.find(1);
    bt.insert(2, n);
    bt.insert(3, n);

    n = bt.find(2);
    bt.insert(4, n);
    bt.insert(5, n);

    n = bt.find(4);
    bt.insert(8, n);
    bt.insert(9, n);

    n = bt.find(5);
    bt.insert(10, n);

    n = bt.find(3);
    bt.insert(6, n);
    bt.insert(7, n);

    SharedPointer<DynamicArray<int>> sp = bt.traversal(LevelOrder);

    for (int i=0; i<sp->length(); ++i)
    {
        cout << (*sp)[i] << " ";
    }

    cout << endl;

    n = bt.thread(LevelOrder);

    while (n != nullptr)
    {
        cout << n->value << " ";
        n = n->right;
    }

    return 0;
}

输出：

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

小结

  • 线索化是将二叉树转换为双向链表的过程
  • 线索化之后结点间的先后次序符合某种遍历次序
  • 线索化操作将破坏原二叉树结点间的父子关系
  • 线索化之后二叉树不再管理结点的生命周期

以上内容整理于狄泰软件学院系列课程，请大家保护原创！

c++
点赞
收藏
评论区
推荐文章
22 22
•
4年前
线索二叉树的原理及创建
【系列推荐阅读】1.为什么要用到线索二叉树？我们先来看看普通的二叉树有什么缺点。下面是一个普通二叉树（链式存储方式）：乍一看，会不会有一种违和感？整个结构一共有7个结点，总共14个指针域，其中却有8个指针域都是空的。对于一颗有n个结点的二叉树而言，总共会有n1个空指针域，这个规律使用所有的二叉树。这么多的空指针域是不
1864
0
0
Wesley13 Wesley13
•
3年前
PHP安全性防范方式
<h2SQL注入</h2<pSQL注入是一种恶意攻击，用户利用在表单字段输入SQL语句的方式来影响正常的SQL执行。</p<h4防范方式</h4<ul<li使用mysql\_real\_escape\_string()，或者addslashes()过滤数据</li<li手动检查每一数据是否为正确的数据类型</li<li使用
973
0
0
Wesley13 Wesley13
•
3年前
Activiti 工作流入门指南
<divclass"htmledit\_views"id"content\_views"<h1<aname"t0"</a概览</h1<p如我们的介绍部分所述，Activiti目前分为两大类：</p<ul<li<p<ahref"https://activiti.gitbook.io/activiti7deve
1086
0
0
Wesley13 Wesley13
•
3年前
JAVA递归实现线索化二叉树
JAVA递归实现线索化二叉树基础理论首先，二叉树递归遍历分为先序遍历、中序遍历和后序遍历。先序遍历为：根节点左子树右子树中序遍历为：左子树根节点右子树后序遍历为：左子树右子树根节点（只要记住根节点在哪里就是什么遍历，且都是先左再右）线索化现在有这么一棵二叉树，它的数据结
1110
0
0
Stella981 Stella981
•
3年前
ASMSupport教程4.8 生成逻辑运算操作
<p在java中有以下逻辑运算符：</p<ul<li&amp;&amp;：条件与</li<li||：条件或</li<li&amp;:布尔型的逻辑与</li<li|：布尔型的逻辑或</li<li^:布尔型的逻辑异或</li<li!:非操作</li</ul<p那么接下来我们将些段例子
987
0
0
Wesley13 Wesley13
•
3年前
Java 9版本之后Base64Encoder和Base64Decoder无法继续使用解决办法
<divclass"htmledit\_views"id"content\_views"<p在项目开发过程中，因为重装系统，安装了Java10版本，发现sun.misc.Base64Encoder和sun.misc.Base64Decoder无法使用。</p<p<br</p<p<strong原因：</strong</p<p查看
937
0
0
Stella981 Stella981
•
3年前
ASMSupport教程4.11 生成数组操作
<p在任何语言里，数组都是基本的数据类型，我们这一节将讲述如何生成数组操作。</p<p数组操作包括以下几个：</p<ol<li创建数组</li<li获取数组长度</li<li获取数组每个元素的内容</li<li为数组元素赋值</li</ol<p我们接下来对每种操作进行详解。</p<h3<fonts
922
0
0
Stella981 Stella981
•
3年前
IdeaVim
<divid"cnblogs\_post\_body"class"blogpostbodycnblogsmarkdown"<h3id"ideavim简介"IdeaVim简介</h3<pIdeaVim是IntelliJIDEA的一款插件，他提高了我们写代码的速度，对代码的跳转，查找也很友好。</p<ul<li安装位置</
918
0
0
Stella981 Stella981
•
3年前
ASMSupport教程4.12 生成方法调用操作
<p这一节我们讲如何用ASMSupport生成方法调用的操作，方法调用包括下面四种类型：</p<ol<li调用构造方法<li调用静态方法<li调用非静态方法<li调用当前类的方法<li调用父类方法</li</ol<p首先我们需要看我们想要生成的类：</p<p代码1：</p<h3<divid"scid:9D
875
0
0
Wesley13 Wesley13
•
3年前
HTML快捷写法大全
父子用\ \Ulli\3\<ul\    <li\</li\    <li\</li\    <li\</li\</ul\兄弟之间用,也可以省写\pspan\，\ul\<p\</p\<span
898
0
0
Easter79 Easter79
•
3年前
Tomcat安装、配置、优化及负载均衡详解
<divid"cnblogs\_post\_body"class"blogpostbody"<p<strong原文地址：https://www.cnblogs.com/rocomp/p/4802396.html</strong</p<p<strong一、常见JavaWeb服务器</strong</p<div<strong&
802
0
0
拓朴棱镜
拓朴棱镜
Lv1
为了赞美而去修行，有如被践踏的香花美草。
文章
2
粉丝
0
获赞
0
热门文章
css如何实现三角形，箭头，提示框，来一探究竟吧