Java数据结构二叉树难点解析

前言

本章,我们主要需要了解以下内容

  • 什么是线索二叉树
  • 怎么去把二叉树线索化
  • 怎么通过线索二叉树查找某个数的后继结点
  • 二叉树的查看——二叉树怎们遍历

什么是线索二叉树

首先我们来了解一下什么是线索二叉树?

定义:一个二叉树通过如下的方法“穿起来”:所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继,所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。

再看一下为什么要有线索二叉树?

顾名思义,线索二叉树,肯定是根据线索查找,查找速度肯定更快。

  • 线索二叉树能线性地遍历二叉树,从而比递归的中序遍历更快。使用线索二叉树也能够方便的找到一个节点的父节点,这比显式地使用父亲节点指针或者栈效率更高。这在栈空间有限,或者无法使用存储父节点的栈时很有作用(对于通过深度优先搜索来查找父节点而言)。

那线索仅仅是这样吗?当然不,我们都是懒的,能等待解决的问题,为什么会去想新的办法。我们要解决的是:

  • 为了解决无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题
  • 但是同时出现了二叉链表找左、右孩子困难的问题,即在构建线索二叉树之后,链表的原来遍历方式会出问题。

最后看一下什么线索二叉树的图解

在我们的线索二叉树的书上,基本上都有以下这张图:

大家看到上面这张图还是有点懵的叭,我们一起看一下我下面手画的图

怎么去把二叉树线索化

哦!在着之前献给大家提一下,二叉树的遍历方式,有这样的几种

  • 前序遍历二叉树的递归定义(根左右)
  • 中序遍历二叉树的递归定义(左根右)
  • 后续遍历二叉树的递归意义(左右根)

本博文主要讨论的是中序遍历
它的中序遍历结果就是ABCDE F GHI

它的中序线索二叉树遍历如下

先画线索二叉树

虚线箭头为线索指针,对于所有左指针指向空的节点:将该节点的左指针指向该节点在中序遍历中的上一节点;对于所有右指针指向空的节点,将该节点的右指针指向该节点在中序遍历中的下一结点。最后一个末尾结点除外。
中序图解线索二叉树

怎么通过线索二叉树查找某个数的后继结点

即形成了一个特殊的双向链表,之所以特殊,以F–>E为例,F–>E并不是直接到达,而是通过F–>B–>D–>E间接到达。

我们尝试用Java去构建一颗线索二叉树叭

先申明,我从未使用Java构建过树,二叉树都没有,若有错误,请指出

数据结点类

package com.testtree;

/**
 * @author pier
 */
public class TreeNode {
    /**数据域**/
    private int data;
    /**左指针**/
    private TreeNode left;
    /** 左孩子是否为线索,采用布尔类型主要是判断是否未null足以**/
    private boolean leftIsThread;
    /**右指针**/
    private TreeNode right;
    /** 右孩子是否为线索**/
    private boolean rightIsThread;

    /**根据数据域来确定所在的指针对应位置**/
    public TreeNode(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 TreeNode getLeft()
    {
        return left;
    }

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

    public boolean isLeftIsThread()
    {
        return leftIsThread;
    }

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

    public TreeNode getRight()
    {
        return right;
    }

    public void setRight(TreeNode 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 TreeNode )
        {
            TreeNode temp = (TreeNode) obj;
            if (temp.getData() == this.data)
            {
                return true;
            }
        }
        return false;
    }

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

二叉树类

package com.testtree;
/*author:pier
2021/10/12
*/

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

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

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

    /**
     * 创建二叉树
     *
     */
    public TreeNode createTree(int[] data, int index)
    {
        if (index > data.length)
        {
            return null;
        }
        TreeNode node = new TreeNode(data[index - 1]);
        TreeNode left = createTree(data, 2 * index);
        TreeNode right = createTree(data, 2 * index + 1);
        node.setLeft(left);
        node.setRight(right);
        return node;
    }
    /**中序遍历**/
    public void inList(TreeNode root)
    {
        if (root != null)
        {
            inList(root.getLeft());
            System.out.print(root.getData() + ",");
            inList(root.getRight());
        }
    }

    public TreeNode getRoot()
    {
        return root;
    }

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

    public int getSize()
    {
        return size;
    }

    public void setSize(int size)
    {
        this.size = size;
    }
    /**线索化二叉树**/
    public void inThread(TreeNode 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(TreeNode 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);
        }
    }
}

测试类

package com.testtree;

/**
 * @author pier
 */
public class Test {
    public static void main(String[] args) {
    //不要问我为什么设置这么大,结尾看我效果截图
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=i+1;
        }
        //创建一颗二叉树
        BiTree biTree = new BiTree(arr);
        //中序遍历二叉树
        System.out.println("中序遍历结果如下:");
        long start1 = System.currentTimeMillis();
        biTree.inList(biTree.getRoot());
        long end1 = System.currentTimeMillis();
        System.out.println();
        System.out.println("普通遍历时间为:"+(end1-start1)+"毫秒");
        System.out.println("\n");
        //中序遍历将二叉树线索化
        biTree.inThread(biTree.getRoot());
        System.out.println("线索二叉树中序遍历如下:");
        long start2 = System.currentTimeMillis();
        biTree.inThreadList(biTree.getRoot());
        long end2 = System.currentTimeMillis();
        System.out.println();
        System.out.println("线索二叉树的遍历时间为:"+(end2-start2)+"毫秒");

    }
}

运行结果

当我使用1-10的时候效果截图

完全看不出来差距,所以,哈哈才设置那么大,能够实践出来线索二叉树的遍历速度确实更快的。

Ps:看完这篇文章,你不来点个赞吗?不来个三连吗?重点是,你今天Get到了吗?别之后ALT+Insert自动生成get哟,用你那看起来不聪明的小脑袋瓜想一想。

到此这篇关于Java数据结构二叉树难点解析的文章就介绍到这了,更多相关Java 二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java中关于二叉树层序遍历深入了解

    前言 大家好,我是bigsai,在数据结构与算法中,二叉树无论是考研.笔试都是非常高频的考点内容,在二叉树中,二叉树的遍历又是非常重要的知识点,今天给大家讲讲二叉树的层序遍历. 这部分很多人可能会但是需要注重一下细节. 前面介绍了二叉排序树的构造和基本方法的实现,遍历也是比较重要的一环,并且二叉树的层序遍历也是bfs的最简单情况,这里我就将二叉树的层序遍历以及常考问题给大家分享一下. 在了解二叉树的遍历之前,需要具备数据结构与算法有队列.递归.栈.二叉树,这些内容咱们前面都有讲过,有这方面知识欠

  • Java二叉树的四种遍历(递归与非递归)

    目录 一.先序遍历与后序遍历 二.中序遍历 三.层序遍历 一.先序遍历与后序遍历 先序遍历根节点,再遍历左子树,再遍历右子树. 后序遍历先遍历左子树,再遍历右子树,再遍历根节点. 先序遍历递归实现: public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right); } 先序遍历的非递归

  • java二叉树的遍历方式详解

    目录 一.前序遍历(递归和非递归) 二.中序遍历(递归和非递归) 三.后序遍历(递归和非递归) 四.层序遍历 总结 一.前序遍历(递归和非递归) 前序遍历就是先遍历根再遍历左之后是右 根左右 递归实现: public List<Integer> preorderTraversal(TreeNode root) { List <Integer> list=new ArrayList<>(); pre(root,list); return list; } public vo

  • Java实现红黑树(平衡二叉树)的详细过程

    目录 前言 红黑二叉查找树 2-3树 2-3树的插入操作 实现红黑二叉树 结尾 前言 在实现红黑树之前,我们先来了解一下符号表. 符号表的描述借鉴了Algorithms第四版,详情在:https://algs4.cs.princeton.edu/home/ 符号表有时候被称为字典,就如同英语字典中,一个单词对应一个解释,符号表有时候又被称之为索引,即书本最后将术语按照字母顺序列出以方便查找的那部分.总的来说,符号表就是将一个键和一个值联系起来,就如Python中的字典,JAVA中的HashMap

  • java非递归实现之二叉树的前中后序遍历详解

    二叉树的前中后序遍历 核心思想:用栈来实现对节点的存储.一边遍历,一边将节点入栈,在需要时将节点从栈中取出来并遍历该节点的左子树或者右子树,重复上述过程,当栈为空时,遍历完成. 前序遍历 //非递归 //根 左 右 class Solution { public List<Integer> preorderTraversal(TreeNode root) { //用数组来存储前序遍历结果 List<Integer> list = new ArrayList<>(); i

  • Java中关于二叉树的概念以及搜索二叉树详解

    目录 一.二叉树的概念 为什么要使用二叉树? 树是什么? 树的相关术语! 根节点 路径 父节点 子节点 叶节点 子树 访问 层(深度) 关键字 满二叉树 完全二叉树 二叉树的五大性质 二.搜索二叉树 插入 删除 hello, everyone. Long time no see. 本期文章,我们主要讲解一下二叉树的相关概念,顺便也把搜索二叉树(也叫二叉排序树)讲一下.我们直接进入正题吧!GitHub源码链接 一.二叉树的概念 为什么要使用二叉树? 为什么要用到树呢?因为它通常结合了另外两种数据结

  • Java数据结构二叉树难点解析

    前言 本章,我们主要需要了解以下内容 什么是线索二叉树 怎么去把二叉树线索化 怎么通过线索二叉树查找某个数的后继结点 二叉树的查看--二叉树怎们遍历 什么是线索二叉树 首先我们来了解一下什么是线索二叉树? 定义:一个二叉树通过如下的方法"穿起来":所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继,所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱. 再看一下为什么要有线索二叉树? 顾名思义,线索二叉树,肯定是根据线索查找,查找速度肯定更快. 线索二叉树能线性地遍历二

  • java 数据结构二叉树的实现代码

    1. 二叉树接口 public interface BinaryTreeInterface<T> { public T getRootData(); public int getHeight(); public int getNumberOfRoot(); public void clear(); public void setTree(T rootData); // 用rootData设置树 public void setTree(T rootData,BinaryTreeInterface

  • java数据结构之树基本概念解析及代码示例

    Java中树的存储结构实现 一.树 树与线性表.栈.队列等线性结构不同,树是一...节点与节点之间的父子关系,可以为每个节点增加一个parent域,用以记录该节点的父点 树是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点组成一个具有层次关系的集合.把 它叫做"树"是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. 树定义和基本术语 定义 树(Tree)是n(n≥0)个结点的有限集T,并且当

  • Java数据结构专题解析之栈和队列的实现

    目录 1. 栈 1.1 概念 1.2 助解图题 1.3 栈的数组实现 1.4 问题 1.5 栈的单链表实现 2. 队列 2.1 概念 2.2 问题 2.3 队列的单链表实现 2.4 数组实现队列 2.5 循环队列 2.6 双端队列 3. 栈和队列练习题 3.1 有效的括号 3.2 用队列实现栈 3.3 用栈实现队列 3.4 实现一个最小栈 3.5 设计循环队列 1. 栈 1.1 概念 栈:是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作. 特点:栈中的数据元素遵循先进后出的原则,但

  • Java数据结构学习之二叉树

    1 背景知识:树(Tree) 在之前的笔记中,我们介绍的链表.栈.队列.数组和字符串都是以线性结构来组织数据的.本篇笔记要介绍的树采用的是树状结构,这是一种非线性的数据组织形式. 树结构由节点和边构成,且不存在环.我们曾在线性表型的数据结构中介绍过循环链表和循环队列,这两种数据结构使得存储容器中的元素形成一个闭环,具体可参看"数据结构学习笔记"系列的相关博文,链接贴在下面: 链表:https://www.jb51.net/article/215278.htm 队列:https://ww

  • Java程序结构与常量变量难点解析

    目录 前言 一.java程序结构 二.java程序的运行 1.运行过程 2.JVM是什么? 三.常量与变量 1. 计算机工作原理 2.变量和类型 3.变量的命名规则 4.变量的作用范围 总结 前言 新征程,进入java的学习. 给自己定下一个铁律: 学习,刷题. 一.java程序结构 下面先上一个最简单的java程序: public class HelloWorld{ public static void main(String[] args){ System.out.println("hell

  • Java数据结构最清晰图解二叉树前 中 后序遍历

    目录 一,前言 二,树 ①概念 ②树的基础概念 三,二叉树 ①概念 ②两种特殊的二叉树 ③二叉树的性质 四,二叉树遍历 ①二叉树的遍历 ②前序遍历 ③中序遍历 ④后序遍历 五,完整代码 一,前言 二叉树是数据结构中重要的一部分,它的前中后序遍历始终贯穿我们学习二叉树的过程,所以掌握二叉树三种遍历是十分重要的.本篇主要是图解+代码Debug分析,概念的部分讲非常少,重中之重是图解和代码Debug分析,我可以保证你看完此篇博客对于二叉树的前中后序遍历有一个新的认识!!废话不多说,让我们学起来吧!!

  • java数据结构之搜索二叉树

    本文实例为大家分享了java数据结构之搜索二叉树的具体代码,供大家参考,具体内容如下 搜索二叉树的定义是:在一个二叉树上,左节点一定比父节点小,右节点一定比父节点大,其他定义跟二叉树相同. 代码实现: public class node {     int data;     public node left, right=null;       public node(int data) {         this.data = data;       }       public node

  • 剑指Offer之Java算法习题精讲二叉树专项解析

    题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * t

  • Java 数据结构进阶二叉树题集下

    目录 1.对称二叉树 2.创建并遍历二叉树 3.二叉树中两节点最近公共祖先 4.二叉搜索树与双向链表 5.根据前序和中序遍历结果创建二叉树 6.二叉树创建字符串 7.非递归实现二叉树前序遍历 8.非递归实现二叉树后序遍历 1.对称二叉树 [OJ链接] 分为以下几种情况: 二叉树为空,是对称二叉树 二叉树不为空,其左子树或者右子树为空,不是对称二叉树 二叉树不为空,左右子树都为空,是对称二叉树 二叉树不为空,左右子树不为空,左右子节点值不同,不是对称二叉树 二叉树不为空,左右子树不为空,左右子节点

随机推荐