本篇內(nèi)容主要講解“什么是Java線索化二叉樹”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“什么是Java線索化二叉樹”吧!
為紅河哈尼等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù),及紅河哈尼網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、紅河哈尼網(wǎng)站設(shè)計(jì),以傳統(tǒng)方式定制建設(shè)網(wǎng)站,并提供域名空間備案等一條龍服務(wù),秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求,就會得到認(rèn)可,從而選擇與我們長期合作。這樣,我們也可以走得更遠(yuǎn)!
將數(shù)列{1,3,6,8,10,14}構(gòu)建成一顆二叉樹.n+1=7,如下圖所示
問題分析:
當(dāng)我們對上面的二叉樹進(jìn)行中序遍歷時,數(shù)列為{8,3,10,1,14,6}
但是6,8,10,14這幾個節(jié)點(diǎn)的左右指針,并沒有完全的利用上。
如果我們希望充分的利用各個節(jié)點(diǎn)的左右指針,讓各個節(jié)點(diǎn)指向自己的前后節(jié)點(diǎn)怎么辦?
解決方案-線索二叉樹
n 個節(jié)點(diǎn)的二叉鏈表中含有n+1【公式 2n-(n-1)=n+1】個空指針域。利用二叉鏈表中的空指針域,存放該節(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼點(diǎn)的指針(這種附加的指針稱為線索)。
這種加了線索的二叉鏈表稱為線索鏈表,相應(yīng)的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據(jù)線索的性質(zhì)不同,線索二叉樹可分為前序線索二叉樹、中序線索二叉樹、后序線索二叉樹三種。
一個節(jié)點(diǎn)的前一個節(jié)點(diǎn),稱為前驅(qū)節(jié)點(diǎn)。
一個節(jié)點(diǎn)的后一個節(jié)點(diǎn),稱為后繼節(jié)點(diǎn)。
中序遍歷的結(jié)果{8,3,10,1,14,6}
說明:當(dāng)線索化二叉樹后,Node節(jié)點(diǎn)的屬性left和right,有如下情況:
left指向的值左子樹,也可能是指向的前驅(qū)節(jié)點(diǎn),比如①節(jié)點(diǎn)left指向的左子樹,而⑩節(jié)點(diǎn)的left指向的就是前驅(qū)節(jié)點(diǎn)。
right指向的右子樹,也可能是指向后繼節(jié)點(diǎn),比如①節(jié)點(diǎn)right指向的是右子樹,而⑩節(jié)點(diǎn)的right指向的是后繼節(jié)點(diǎn)。
package com.xie.tree.threadedbinarytree; public class ThreadedBinaryTreeDemo { public static void main(String[] args) { //測試中序線索二叉樹 HeroNode root = new HeroNode(1, "tom"); HeroNode node2 = new HeroNode(3, "jack"); HeroNode node3 = new HeroNode(6, "smith"); HeroNode node4 = new HeroNode(8, "mary"); HeroNode node5 = new HeroNode(10, "king"); HeroNode node6 = new HeroNode(14, "dim"); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(); threadedBinaryTree.setRoot(root); threadedBinaryTree.threadedNodes(); //測試:以10號節(jié)點(diǎn)測試 HeroNode left = node5.getLeft(); System.out.println("10號節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是:" + left); HeroNode right = node5.getRight(); System.out.println("10號節(jié)點(diǎn)的后繼節(jié)點(diǎn)是:" + right); System.out.println("使用線索化的方式遍歷 線索二叉樹"); threadedBinaryTree.threadedBinaryTreeList(); /** * 10號節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是:HeroNode{no=3, name=jack} * 10號節(jié)點(diǎn)的后繼節(jié)點(diǎn)是:HeroNode{no=1, name=tom} * 使用線索化的方式遍歷 線索二叉樹 * HeroNode{no=8, name=mary} * HeroNode{no=3, name=jack} * HeroNode{no=10, name=king} * HeroNode{no=1, name=tom} * HeroNode{no=14, name=dim} * HeroNode{no=6, name=smith} */ } } //實(shí)現(xiàn)了線索化功能的二叉樹 class ThreadedBinaryTree { private HeroNode root; //為了實(shí)現(xiàn)線索化,需要創(chuàng)建一個指向當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針 //在遞歸進(jìn)行線索化時,pre總是保留前一個節(jié)點(diǎn) private HeroNode pre; public void setRoot(HeroNode root) { this.root = root; } /** * 遍歷線索化二叉樹的方法。 */ public void threadedBinaryTreeList() { //定義一個變量,存儲當(dāng)前遍歷的節(jié)點(diǎn),從root開始 HeroNode node = root; while (node != null) { //循環(huán)找到leftType==1的節(jié)點(diǎn),第一個找到就是8節(jié)點(diǎn) //后面隨著遍歷而變化,因?yàn)楫?dāng)leftType==1時,說明該節(jié)點(diǎn)是按照線索化處理后的有效節(jié)點(diǎn) while (node.getLeftType() == 0) { node = node.getLeft(); } //打印當(dāng)前節(jié)點(diǎn) System.out.println(node); //如果當(dāng)前節(jié)點(diǎn)的右指針指向的是后繼節(jié)點(diǎn),就一直輸出 while (node.getRightType() == 1) { //獲取到當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) node = node.getRight(); System.out.println(node); } //替換這個遍歷的節(jié)點(diǎn) node = node.getRight(); } } /** * 重載threadedNodes方法 */ public void threadedNodes() { threadedNodes(root); } /** * 編寫對二叉樹進(jìn)行線索化的方法 * * @param node 當(dāng)前需要線索化的節(jié)點(diǎn) */ public void threadedNodes(HeroNode node) { if (node == null) { return; } //先線索化左子樹 threadedNodes(node.getLeft()); //線索化當(dāng)前節(jié)點(diǎn)【有難度】 //處理當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn) //以8節(jié)點(diǎn)來理解,8節(jié)點(diǎn).left=null if (node.getLeft() == null) { //讓當(dāng)前節(jié)點(diǎn)的左指針指向前驅(qū)節(jié)點(diǎn) node.setLeft(pre); //修改當(dāng)前節(jié)點(diǎn)的左指針類型 node.setLeftType(1); } //處理后繼節(jié)點(diǎn) if (pre != null && pre.getRight() == null) { //讓前驅(qū)節(jié)點(diǎn)的右指針指向當(dāng)前節(jié)點(diǎn) pre.setRight(node); //修改前驅(qū)節(jié)點(diǎn)的右指針類型 pre.setRightType(1); } //每處理一個節(jié)點(diǎn)后,讓當(dāng)前節(jié)點(diǎn)是下一個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn) pre = node; //再線索化右子樹 threadedNodes(node.getRight()); } } //創(chuàng)建HeroNode節(jié)點(diǎn) class HeroNode { static int preCount = 0; static int infoxCount = 0; static int postCount = 0; private int no; private String name; private HeroNode left; private HeroNode right; //0 表示指向的是左子樹,1 表示指向的是前驅(qū)節(jié)點(diǎn) private int leftType; //0 表示指向右子樹,1 表示指向的是后繼節(jié)點(diǎn) private int rightType; public HeroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } public int getLeftType() { return leftType; } public void setLeftType(int leftType) { this.leftType = leftType; } public int getRightType() { return rightType; } public void setRightType(int rightType) { this.rightType = rightType; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name=" + name + '}'; } //前序遍歷 public void preOrder() { System.out.println(this); //遞歸向左子樹前序遍歷 if (this.left != null) { this.left.preOrder(); } //遞歸向右子樹前序遍歷 if (this.right != null) { this.right.preOrder(); } } //中序遍歷 public void infixOrder() { //遞歸向左子樹中序遍歷 if (this.left != null) { this.left.infixOrder(); } System.out.println(this); //遞歸向右子樹中序遍歷 if (this.right != null) { this.right.infixOrder(); } } //后序遍歷 public void postOrder() { //遞歸向左子樹后序遍歷 if (this.left != null) { this.left.postOrder(); } //遞歸向右子樹后序遍歷 if (this.right != null) { this.right.postOrder(); } System.out.println(this); } //遞歸刪除節(jié)點(diǎn) //1.如果刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn),則刪除該節(jié)點(diǎn)。 //2.如果刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn),則刪除該樹。 public void delNo(int no) { /** * 1.因?yàn)槲覀兊亩鏄涫菃蜗虻?,所以我們是判斷?dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否是需要刪除的節(jié)點(diǎn),而不能去判斷當(dāng)前節(jié)點(diǎn)是否是需要刪除的節(jié)點(diǎn)。 * 2.如果當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空,并且左子節(jié)點(diǎn)就是需要刪除的節(jié)點(diǎn),就將this.left = null;并且返回(結(jié)束遞歸)。 * 3.如果當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空,并且右子節(jié)點(diǎn)就是需要刪除的節(jié)點(diǎn),將將this.right = null;并且返回(結(jié)束遞歸)。 * 4.如果第2步和第3步?jīng)]有刪除節(jié)點(diǎn),那么就要向左子樹進(jìn)行遞歸刪除。 * 5.如果第4步也沒有刪除節(jié)點(diǎn),則應(yīng)當(dāng)向右子樹進(jìn)行遞歸刪除。 */ if (this.left != null && this.left.no == no) { this.left = null; return; } if (this.right != null && this.right.no == no) { this.right = null; return; } if (this.left != null) { this.left.delNo(no); } if (this.right != null) { this.right.delNo(no); } } //前序遍歷查找 public HeroNode preOrderSearch(int no) { HeroNode res = null; preCount++;//這里必須放在this.no == no 判斷之前,才進(jìn)行實(shí)際的比較 //若果找到,就返回 if (this.no == no) { return this; } //沒有找到,向左子樹遞歸進(jìn)行前序查找 if (this.left != null) { res = this.left.preOrderSearch(no); } //如果res != null 就直接返回 if (res != null) { return res; } //如果左子樹沒有找打,向右子樹進(jìn)行前序查找 if (this.right != null) { res = this.right.preOrderSearch(no); } //如果找到就返回 if (res != null) { return res; } return res; } //中序遍歷查找 public HeroNode infixOrderSearch(int no) { HeroNode res = null; if (this.left != null) { res = this.left.infixOrderSearch(no); } if (res != null) { return res; } infoxCount++;//這里必須放在this.no == no 判斷之前,才進(jìn)行實(shí)際的比較 if (this.no == no) { return this; } if (this.right != null) { res = this.right.infixOrderSearch(no); } if (res != null) { return res; } return res; } //后序遍歷查找 public HeroNode postOrderSearch(int no) { HeroNode res = null; if (this.left != null) { res = this.left.postOrderSearch(no); } if (res != null) { return res; } if (this.right != null) { res = this.right.postOrderSearch(no); } if (res != null) { return res; } postCount++;//這里必須放在this.no == no 判斷之前,才進(jìn)行實(shí)際的比較 if (this.no == no) { return this; } return res; } }
到此,相信大家對“什么是Java線索化二叉樹”有了更深的了解,不妨來實(shí)際操作一番吧!這里是創(chuàng)新互聯(lián)網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
網(wǎng)站題目:什么是Java線索化二叉樹
文章位置:http://muchs.cn/article46/jpeieg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供軟件開發(fā)、網(wǎng)站制作、品牌網(wǎng)站建設(shè)、云服務(wù)器、網(wǎng)站建設(shè)、手機(jī)網(wǎng)站建設(shè)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)