数据结构08 线索二叉树

上一篇总结了二叉树,这一篇要总结的是线索二叉树,我想从以下几个方面进行总结。

1、什么是线索二叉树?

2、为什么要建立线索二叉树?

3、如何将二叉树线索化?

4、线索二叉树的常见操作及实现思路?

5、算法实现代码?

1、什么是线索二叉树

线索二叉树:

按照某种方式对二叉树进行遍历,可以把二叉树中所有节点排序为一个线性序列,在该序列中,除第一个节点外每个节点有且仅有一个直接前驱节点;除最后一个节点外每一个节点有且仅有一个直接后继节点;

在N个节点的二叉树中,每个节点有2个指针,所以一共有2N个指针,除了根节点以外,每一个节点都有一个指针从它的父节点指向它,所以一共使用了N-1个指针,所以剩下2N-(N-1)也就是N+1个空指针;

如果能利用这些空指针域来存放指向该节点的直接前驱或是直接后继的指针,则可由此信息直接找到在该遍历次序下的前驱节点或后继节点,从而比递归遍历提高了遍历速度,节省了建立系统递归栈所使用的存储空间;

这些被重新利用起来的空指针就被称为线索(Thread),加上了线索的二叉树就是线索二叉树;如图:

2、为什么要建立线索二叉树

有了二叉树不就足够了吗?那为什么还要弄个线索二叉树出来呢?

在原来的二叉链表中,查找节点的左,右孩子可以直接实现,可是如果要找该节点的前驱和后继节点呢?这就变得非常困难,所以为了实现这个常见的需求,我们要在每个节点中增加两个指针域来存放遍历时得到的前驱和后继节点,这样就可以通过该指针直接或间接访问其前驱和后继节点。

3、如何将二叉树线索化

按某种次序遍历二叉树,在遍历过程中用线索取代空指针即可。

下面是线索二叉树和线索二叉链表的示意图,它可以帮助我们更好地理解线索二叉树。

4、线索二叉树的常见操作及实现思路

4-1、二叉树线索化

实现思路:按某种次序遍历二叉树,在遍历过程中用线索取代空指针即可。

4-2、遍历

实现思路:以中序遍历为例,首先找到中序遍历的开始节点,然后利用线索依次查找后继节点即可。

5、实现代码

代码:

Node.java

public class Node {
    private int data;
    private Node left;
    private boolean leftIsThread; // 左孩子是否为线索
    private Node right;
    private boolean rightIsThread; // 右孩子是否为线索

    public Node(int data) {
        this.data = data;
        this.left = null;
        this.leftIsThread = false;
        this.right = null;
        this.rightIsThread = false;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public boolean isLeftIsThread() {
        return leftIsThread;
    }

    public void setLeftIsThread(boolean leftIsThread) {
        this.leftIsThread = leftIsThread;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public boolean isRightIsThread() {
        return rightIsThread;
    }

    public void setRightIsThread(boolean rightIsThread) {
        this.rightIsThread = rightIsThread;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Node) {
            Node temp = (Node) obj;
            if (temp.getData() == this.data) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int hashCode() {
        return super.hashCode() + this.data;
    }
}

ThreadTree.java

public class ThreadTree {
    private Node root; // 根节点
    private int size; // 大小
    private Node pre = null; // 线索化的时候保存前驱

    public ThreadTree() {
        this.root = null;
        this.size = 0;
        this.pre = null;
    }

    public ThreadTree(int[] data) {
        this.pre = null;
        this.size = data.length;
        this.root = createTree(data, 1); // 创建二叉树
    }

    /**
     * 创建二叉树
     *
     * @param data
     * @param index
     * @return
     */
    public Node createTree(int[] data, int index) {
        if (index > data.length) {
            return null;
        }
        Node node = new Node(data[index - 1]);
        Node left = createTree(data, 2 * index);
        Node right = createTree(data, 2 * index + 1);
        node.setLeft(left);
        node.setRight(right);
        return node;
    }

    /**
     * 将以root为根节点的二叉树线索化
     */
    public void inThread(Node root) {
        if (root != null) {
            inThread(root.getLeft()); // 线索化左孩子
            if (null == root.getLeft()) { // 左孩子为空
                root.setLeftIsThread(true); // 将左孩子设置为线索
                root.setLeft(pre);
            }
            if (pre != null && null == pre.getRight()) { // 右孩子为空
                pre.setRightIsThread(true);
                pre.setRight(root);
            }
            pre = root;
            inThread(root.getRight()); // 线索化右孩子
        }
    }

    /**
     * 中序遍历线索二叉树
     */
    public void inThreadList(Node root) {
        if (root != null) {
            while (root != null && !root.isLeftIsThread()) {
                // 如果左孩子不是线索
                root = root.getLeft();
            }
            do {
                System.out.print(root.getData() + " ");
                if (root.isRightIsThread()) {
                    // 如果右孩子是线索
                    root = root.getRight();
                } else {
                    // 有右孩子
                    root = root.getRight();
                    while (root != null && !root.isLeftIsThread()) {
                        root = root.getLeft();
                    }
                }
            } while (root != null);
        }
    }

    /**
     * 中序递归遍历
     */
    public void inList(Node root) {
        if (root != null) {
            inList(root.getLeft());
            System.out.print(root.getData() + " ");
            inList(root.getRight());
        }
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }
}

ThreadTreeTest.java

public class ThreadTreeTest {
    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        ThreadTree threadTree = new ThreadTree(data); // 创建普通二叉树
        System.out.println("中序递归遍历二叉树");
        threadTree.inList(threadTree.getRoot()); // 中序递归遍历二叉树
        System.out.println();

        threadTree.inThread(threadTree.getRoot()); // 采用中序遍历将二叉树线索化
        System.out.println("中序遍历线索化二叉树");
        threadTree.inThreadList(threadTree.getRoot()); // 中序遍历线索化二叉树
    }
}

运行结果:

6、总结

由于它充分利用了空指针域的空间(等于节省了空间),又保证了创建时的一次遍历就可以终生受用前驱、后继的信息(这意味着节省了时间),所以在实际问题中,如果所使用的二叉树需要经常遍历或查找节点时需要某种遍历中的前驱和后继,那么采用线索二叉链表的存储结构就是不错的选择。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JavaEdge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

91020
来自专栏曾大稳的博客

线性表(ArrayList 和 LinkedList源码分析)

线性表(linear list) 是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。

16420
来自专栏猿人谷

线性表简介

学习数据结构 -> 线性表 -> 线性表的介绍     线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中...

22280
来自专栏算法修养

HOJ 2148&POJ 2680(DP递推,加大数运算)

Computer Transformation Time Limit: 1000MS Memory Limit: 65536K Total S...

304120
来自专栏格子的个人博客

Java源码阅读之ArrayList - JDK1.8

当你对某件事情很感兴趣的时候,时间的流逝在感知中都模糊了(是不是很文艺,绕口得都快听不懂了),通俗来说,就是时间过得很快。

21050
来自专栏趣学算法

数据结构 第4讲 单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

11730
来自专栏haifeiWu与他朋友们的专栏

聊聊ArrayList源码(基于JDK1.8)

打个广告,楼主自己造的轮子,感兴趣的请点[github]: https://github.com/haifeiWu/lightconf

15340
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

551100
来自专栏老付的网络博客

Java中的容器

在Java中有常用的三种类型的容器,分别是List 、Map、Set,基于这个三个基本的类型,派生出很多其它的类型,具体关系如下:

47520
来自专栏小灰灰

JDK容器学习之ArrayList:底层存储和动态扩容

ArrayList 底层存储和动态扩容逻辑 ArrayList 作为最常用的容器之一,通常用来存储一系列的数据对象,O(1)级别的数据读写 I. 底层数据模型...

20570

扫码关注云+社区

领取腾讯云代金券