欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)二叉樹難點(diǎn)解析

 更新時(shí)間:2021年10月25日 15:12:37   作者:pier~呀  
樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu),直觀地看,它是數(shù)據(jù)元素(在樹中稱為結(jié)點(diǎn))按分支關(guān)系組織起來的結(jié)構(gòu),很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存在,如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹形象表示

前言

本章,我們主要需要了解以下內(nèi)容

  • 什么是線索二叉樹
  • 怎么去把二叉樹線索化
  • 怎么通過線索二叉樹查找某個(gè)數(shù)的后繼結(jié)點(diǎn)
  • 二叉樹的查看——二叉樹怎們遍歷

 什么是線索二叉樹

首先我們來了解一下什么是線索二叉樹?

定義:一個(gè)二叉樹通過如下的方法“穿起來”:所有原本為空的右(孩子)指針改為指向該節(jié)點(diǎn)在中序序列中的后繼,所有原本為空的左(孩子)指針改為指向該節(jié)點(diǎn)的中序序列的前驅(qū)。

再看一下為什么要有線索二叉樹?

顧名思義,線索二叉樹,肯定是根據(jù)線索查找,查找速度肯定更快。

  • 線索二叉樹能線性地遍歷二叉樹,從而比遞歸的中序遍歷更快。使用線索二叉樹也能夠方便的找到一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn),這比顯式地使用父親節(jié)點(diǎn)指針或者棧效率更高。這在??臻g有限,或者無法使用存儲(chǔ)父節(jié)點(diǎn)的棧時(shí)很有作用(對(duì)于通過深度優(yōu)先搜索來查找父節(jié)點(diǎn)而言)。

那線索僅僅是這樣嗎?當(dāng)然不,我們都是懶的,能等待解決的問題,為什么會(huì)去想新的辦法。我們要解決的是:

  • 為了解決無法直接找到該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)的問題
  • 但是同時(shí)出現(xiàn)了二叉鏈表找左、右孩子困難的問題,即在構(gòu)建線索二叉樹之后,鏈表的原來遍歷方式會(huì)出問題。

最后看一下什么線索二叉樹的圖解

在我們的線索二叉樹的書上,基本上都有以下這張圖:

線索二叉樹

大家看到上面這張圖還是有點(diǎn)懵的叭,我們一起看一下我下面手畫的圖

怎么去把二叉樹線索化

哦!在著之前獻(xiàn)給大家提一下,二叉樹的遍歷方式,有這樣的幾種

  • 前序遍歷二叉樹的遞歸定義(根左右)
  • 中序遍歷二叉樹的遞歸定義(左根右)
  • 后續(xù)遍歷二叉樹的遞歸意義(左右根)

本博文主要討論的是中序遍歷
它的中序遍歷結(jié)果就是ABCDE F GHI

中序遍歷

它的中序線索二叉樹遍歷如下

先畫線索二叉樹

在這里插入圖片描述

虛線箭頭為線索指針,對(duì)于所有左指針指向空的節(jié)點(diǎn):將該節(jié)點(diǎn)的左指針指向該節(jié)點(diǎn)在中序遍歷中的上一節(jié)點(diǎn);對(duì)于所有右指針指向空的節(jié)點(diǎn),將該節(jié)點(diǎn)的右指針指向該節(jié)點(diǎn)在中序遍歷中的下一結(jié)點(diǎn)。最后一個(gè)末尾結(jié)點(diǎn)除外。
中序圖解線索二叉樹

線索二叉樹

怎么通過線索二叉樹查找某個(gè)數(shù)的后繼結(jié)點(diǎn)

即形成了一個(gè)特殊的雙向鏈表,之所以特殊,以F–>E為例,F(xiàn)–>E并不是直接到達(dá),而是通過F–>B–>D–>E間接到達(dá)。

我們嘗試用Java去構(gòu)建一顆線索二叉樹叭

先申明,我從未使用Java構(gòu)建過樹,二叉樹都沒有,若有錯(cuò)誤,請(qǐng)指出

數(shù)據(jù)結(jié)點(diǎn)類

package com.testtree;

/**
 * @author pier
 */
public class TreeNode {
    /**數(shù)據(jù)域**/
    private int data;
    /**左指針**/
    private TreeNode left;
    /** 左孩子是否為線索,采用布爾類型主要是判斷是否未null足以**/
    private boolean leftIsThread;
    /**右指針**/
    private TreeNode right;
    /** 右孩子是否為線索**/
    private boolean rightIsThread;

    /**根據(jù)數(shù)據(jù)域來確定所在的指針對(duì)應(yīng)位置**/
    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 {
    /** 根節(jié)點(diǎn) **/
    private TreeNode root;
    /** 大小 **/
    private int size;
    /** 線索化的時(shí)候保存前驅(qū) **/
    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;
        // 創(chuàng)建二叉樹
        this.root = createTree(data, 1);
    }

    /**
     * 創(chuàng)建二叉樹
     *
     */
    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() )
            {
                // 將左孩子設(shè)置為線索
                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);
        }
    }
}

測(cè)試類

package com.testtree;

/**
 * @author pier
 */
public class Test {
    public static void main(String[] args) {
    //不要問我為什么設(shè)置這么大,結(jié)尾看我效果截圖
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=i+1;
        }
        //創(chuàng)建一顆二叉樹
        BiTree biTree = new BiTree(arr);
        //中序遍歷二叉樹
        System.out.println("中序遍歷結(jié)果如下:");
        long start1 = System.currentTimeMillis();
        biTree.inList(biTree.getRoot());
        long end1 = System.currentTimeMillis();
        System.out.println();
        System.out.println("普通遍歷時(shí)間為:"+(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("線索二叉樹的遍歷時(shí)間為:"+(end2-start2)+"毫秒");

    }
}

運(yùn)行結(jié)果

結(jié)果


當(dāng)我使用1-10的時(shí)候效果截圖

截圖

完全看不出來差距,所以,哈哈才設(shè)置那么大,能夠?qū)嵺`出來線索二叉樹的遍歷速度確實(shí)更快的。

Ps:看完這篇文章,你不來點(diǎn)個(gè)贊嗎?不來個(gè)三連嗎?重點(diǎn)是,你今天Get到了嗎?別之后ALT+Insert自動(dòng)生成get喲,用你那看起來不聰明的小腦袋瓜想一想。

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)二叉樹難點(diǎn)解析的文章就介紹到這了,更多相關(guān)Java 二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • SpringMvc接收參數(shù)方法總結(jié)(必看篇)

    SpringMvc接收參數(shù)方法總結(jié)(必看篇)

    下面小編就為大家?guī)硪黄猄pringMvc接收參數(shù)方法總結(jié)(必看篇)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-06-06
  • Java抽象定義以及舉例代碼

    Java抽象定義以及舉例代碼

    這篇文章主要給大家介紹了關(guān)于Java抽象定義以及舉例的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-04-04
  • Java?CountDownLatch線程同步源碼硬核解析

    Java?CountDownLatch線程同步源碼硬核解析

    對(duì)于并發(fā)執(zhí)行,Java中的CountDownLatch是一個(gè)重要的類。為了更好的理解CountDownLatch這個(gè)類,本文將通過例子和源碼帶領(lǐng)大家深入解析這個(gè)類的原理,感興趣的可以學(xué)習(xí)一下
    2023-01-01
  • Spring Boot2解決idea console 控制臺(tái)輸出亂碼的問題

    Spring Boot2解決idea console 控制臺(tái)輸出亂碼的問題

    這篇文章主要介紹了Spring Boot2解決idea console 控制臺(tái)輸出亂碼的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-07-07
  • Java獲取任意http網(wǎng)頁源代碼的方法

    Java獲取任意http網(wǎng)頁源代碼的方法

    這篇文章主要介紹了Java獲取任意http網(wǎng)頁源代碼的方法,可實(shí)現(xiàn)獲取網(wǎng)頁代碼以及去除HTML標(biāo)簽的代碼功能,涉及Java正則操作相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下
    2017-09-09
  • Struts2實(shí)現(xiàn)單文件或多文件上傳功能

    Struts2實(shí)現(xiàn)單文件或多文件上傳功能

    這篇文章主要為大家詳細(xì)介紹了Struts2實(shí)現(xiàn)單文件或多文件上傳功能,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-03-03
  • 基于jstl 標(biāo)簽的使用介紹

    基于jstl 標(biāo)簽的使用介紹

    本篇文章小編為大家介紹,基于jstl 標(biāo)簽的使用介紹,需要的朋友參考下
    2013-04-04
  • 貨拉拉大數(shù)據(jù)對(duì)BitMap的探索實(shí)踐詳解

    貨拉拉大數(shù)據(jù)對(duì)BitMap的探索實(shí)踐詳解

    這篇文章主要為大家介紹了貨拉拉大數(shù)據(jù)對(duì)BitMap的探索實(shí)踐詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-09-09
  • Android開發(fā)中實(shí)現(xiàn)用戶注冊(cè)和登陸的代碼實(shí)例分享

    Android開發(fā)中實(shí)現(xiàn)用戶注冊(cè)和登陸的代碼實(shí)例分享

    這篇文章主要介紹了Android開發(fā)中實(shí)現(xiàn)用戶注冊(cè)和登陸的代碼實(shí)例分享,只是實(shí)現(xiàn)基本功能,界面華麗度就請(qǐng)忽略啦XD 需要的朋友可以參考下
    2015-12-12
  • Springboot集成Actuator監(jiān)控功能詳解

    Springboot集成Actuator監(jiān)控功能詳解

    這篇文章主要介紹了Springboot集成Actuator監(jiān)控功能詳解,有時(shí)候我們想要實(shí)時(shí)監(jiān)控我們的應(yīng)用程序的運(yùn)行狀態(tài),比如實(shí)時(shí)顯示一些指標(biāo)數(shù)據(jù),觀察每時(shí)每刻訪問的流量,或者是我們數(shù)據(jù)庫(kù)的訪問狀態(tài)等等,這時(shí)候就需要Actuator了,需要的朋友可以參考下
    2023-09-09

最新評(píng)論