Java數(shù)據(jù)結(jié)構(gòu)二叉樹難點(diǎn)解析
前言
本章,我們主要需要了解以下內(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é)果
當(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)文章希望大家以后多多支持腳本之家!
- Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹的實(shí)現(xiàn)詳解
- 詳解Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹
- Java數(shù)據(jù)結(jié)構(gòu)最清晰圖解二叉樹前 中 后序遍歷
- Java數(shù)據(jù)結(jié)構(gòu)之平衡二叉樹的原理與實(shí)現(xiàn)
- 帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹
- java數(shù)據(jù)結(jié)構(gòu)之搜索二叉樹
- Java 數(shù)據(jù)結(jié)構(gòu)中二叉樹前中后序遍歷非遞歸的具體實(shí)現(xiàn)詳解
- Java?數(shù)據(jù)結(jié)構(gòu)進(jìn)階二叉樹題集下
相關(guān)文章
SpringMvc接收參數(shù)方法總結(jié)(必看篇)
下面小編就為大家?guī)硪黄猄pringMvc接收參數(shù)方法總結(jié)(必看篇)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-06-06Spring Boot2解決idea console 控制臺(tái)輸出亂碼的問題
這篇文章主要介紹了Spring Boot2解決idea console 控制臺(tái)輸出亂碼的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-07-07Struts2實(shí)現(xiàn)單文件或多文件上傳功能
這篇文章主要為大家詳細(xì)介紹了Struts2實(shí)現(xiàn)單文件或多文件上傳功能,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-03-03貨拉拉大數(shù)據(jù)對(duì)BitMap的探索實(shí)踐詳解
這篇文章主要為大家介紹了貨拉拉大數(shù)據(jù)對(duì)BitMap的探索實(shí)踐詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-09-09Android開發(fā)中實(shí)現(xiàn)用戶注冊(cè)和登陸的代碼實(shí)例分享
這篇文章主要介紹了Android開發(fā)中實(shí)現(xiàn)用戶注冊(cè)和登陸的代碼實(shí)例分享,只是實(shí)現(xiàn)基本功能,界面華麗度就請(qǐng)忽略啦XD 需要的朋友可以參考下2015-12-12Springboot集成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