圖解

代碼實(shí)現(xiàn)

package com.atguigu.tree.threadedbinarytree;/*** @創(chuàng)建人 wdl* @創(chuàng)建時(shí)間 2021/3/25* @描述*/ public class ThreadedBinaryTreeDemo {public static void main(String[] args) {//測(cè)試一把中序線(xiàn)索化二叉樹(shù)的功能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");//二叉樹(shù)，后面我們需要遞歸創(chuàng)建，現(xiàn)在手動(dòng)創(chuàng)建root.setLeft(node2);root.setRight(node3);node2.setLeft(node4);node2.setRight(node5);node3.setLeft(node6);//測(cè)試中序線(xiàn)索化ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();threadedBinaryTree.setRoot(root);threadedBinaryTree.threadedNodes();//測(cè)試:以10號(hào)節(jié)點(diǎn)測(cè)試HeroNode leftNode = node5.getLeft();HeroNode rightNode = node5.getRight();System.out.println("10號(hào)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是"+leftNode);System.out.println("10號(hào)節(jié)點(diǎn)的后繼節(jié)點(diǎn)是"+rightNode);//當(dāng)線(xiàn)索化二叉樹(shù)后System.out.println("使用線(xiàn)索化的方式遍歷 線(xiàn)索化二叉樹(shù)");threadedBinaryTree.threadedList();//8,3,10,1,14,6}}//定義ThreadedBinaryTree實(shí)現(xiàn)了線(xiàn)索化功能的二叉樹(shù) class ThreadedBinaryTree{private HeroNode root;//為了實(shí)現(xiàn)線(xiàn)索化，需要?jiǎng)?chuàng)建一個(gè)指向當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針//在遞歸進(jìn)行線(xiàn)索化是，pre總是保留前一個(gè)節(jié)點(diǎn)private HeroNode pre=null;public void setRoot(HeroNode root){this.root=root;}//重載threadedNodes方法public void threadedNodes(){this.threadedNodes(root);}//遍歷線(xiàn)索化二叉樹(shù)的方法public void threadedList(){//定義一個(gè)變量，存儲(chǔ)當(dāng)前遍歷的節(jié)點(diǎn)，從root開(kāi)始HeroNode node=root;while (node!=null){//循環(huán)的扎到leftType==1的節(jié)點(diǎn)，第一個(gè)找到的就是8節(jié)點(diǎn)//后面會(huì)隨著遍歷而變化，因?yàn)楫?dāng)lefType==1時(shí)，說(shuō)明該節(jié)點(diǎn)是按照線(xià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);}//替換這個(gè)遍歷的節(jié)點(diǎn)node=node.getRight();}}//編寫(xiě)對(duì)二叉樹(shù)進(jìn)行中序線(xiàn)索化的方法/**** @param node 就是當(dāng)前需要線(xiàn)索化的節(jié)點(diǎn)*/public void threadedNodes(HeroNode node){//如果node==null，不能線(xiàn)索化if(node==null){return;}//1.先線(xiàn)索化左子樹(shù)threadedNodes(node.getLeft());//2.線(xiàn)索化當(dāng)前節(jié)點(diǎn)[有難度]//處理當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)//以8節(jié)點(diǎn)來(lái)理解//8節(jié)點(diǎn)的.left=null,8節(jié)點(diǎn)的.leftType=1if(node.getLeft()==null){//當(dāng)前節(jié)點(diǎn)的左指針指向前驅(qū)節(jié)點(diǎn)node.setLeft(pre);//修改當(dāng)前節(jié)點(diǎn)的左指針的類(lèi)型,指向前驅(qū)節(jié)點(diǎn)node.setLeftType(1);}//處理當(dāng)前節(jié)點(diǎn)的后繼節(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)的右指針類(lèi)型pre.setRightType(1);}//!!!每處理一個(gè)節(jié)點(diǎn),讓當(dāng)前節(jié)點(diǎn)是下一個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)pre=node;//3.再線(xiàn)索化右子樹(shù)threadedNodes(node.getRight());}//刪除節(jié)點(diǎn)public void delNode(int no){if(root!=null){//如果只有一個(gè)root接地那，這里立即判斷root是不是就是要?jiǎng)h除的節(jié)點(diǎn)if(root.getNo()==no){root=null;}else {//遞歸刪除root.delNode(no);}}else {System.out.println("空樹(shù)，不能刪除");}}//前序遍歷public void preOrder(){if(this.root!=null){this.root.preOrder();}else {System.out.println("二叉樹(shù)為空，無(wú)法遍歷");}}//中序遍歷public void infixOrder(){if(this.root!=null){this.root.infixOrder();}else {System.out.println("二叉樹(shù)為空，無(wú)法遍歷");}}//后序遍歷public void postOrder(){if(this.root!=null){this.root.postOrder();}else {System.out.println("二叉樹(shù)為空，無(wú)法遍歷");}}//前序查找public HeroNode preOrderSearch(int no){if(root!=null){return root.preOrderSearch(no);}else {return null;}}//中序查找public HeroNode infixOrderSearch(int no){if(root!=null){return root.infixOrderSearch(no);}else {return null;}}//后序查找public HeroNode postOrderSearch(int no){if(root!=null){return root.postOrderSearch(no);}else {return null;}}}//先創(chuàng)建HeroNode節(jié)點(diǎn) class HeroNode{private int no;private String name;private HeroNode left;//默認(rèn)為nullprivate HeroNode right;//默認(rèn)為null//說(shuō)明//1.如果leftType==0表示指向的是左子樹(shù)，如果是1則表示指向前驅(qū)節(jié)點(diǎn)//2.如果rightType==0表示指向的是右子樹(shù)，如果是1則表示指向后繼節(jié)點(diǎn)private int leftType;private int rightType;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;}public HeroNode(int no, String name) {super();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;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +'}';}//遞歸刪除節(jié)點(diǎn)//1.如果刪除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則刪除該節(jié)點(diǎn)//2.如果刪除的節(jié)點(diǎn)是非葉子節(jié)點(diǎn)，則刪除該子樹(shù)public void delNode(int no){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.delNode(no);}if(this.right!=null){this.right.delNode(no);}}//編寫(xiě)前序遍歷的方法public void preOrder(){System.out.println(this);//先輸出父節(jié)點(diǎn)//遞歸向左子樹(shù)前序遍歷if(this.left!=null){this.left.preOrder();}//遞歸向右子樹(shù)前序遍歷if(this.right!=null){this.right.preOrder();}}//中序遍歷public void infixOrder(){//遞歸向左子樹(shù)中序遍歷if(this.left!=null){this.left.infixOrder();}System.out.println(this);//輸出父節(jié)點(diǎn)//遞歸向右子樹(shù)中序遍歷if(this.right!=null){this.right.infixOrder();}}//后序遍歷public void postOrder(){//遞歸向左子樹(shù)后序遍歷if(this.left!=null){this.left.postOrder();}//遞歸向右子樹(shù)后序遍歷if(this.right!=null){this.right.postOrder();}System.out.println(this);//輸出父節(jié)點(diǎn)}/**** @param no 查找no* @return 如果找到就返回該Node，如果沒(méi)有找到返回null*///前序遍歷查找public HeroNode preOrderSearch(int no){System.out.println("進(jìn)入前序查找");//比較當(dāng)前節(jié)點(diǎn)是不是if(this.no==no){return this;}//1.則判斷當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)是否為空，如果不為空，則遞歸前序查找//2.如果左遞歸前序查找，找到節(jié)點(diǎn)，則返回HeroNode resNode=null;if(this.left!=null){resNode=this.left.preOrderSearch(no);}if(resNode!=null){//說(shuō)明我們左子樹(shù)找到return resNode;}//1.左遞歸前序查找，找到節(jié)點(diǎn)，則返回，否則判斷//2.當(dāng)前的節(jié)點(diǎn)的右子節(jié)點(diǎn)是否為空，如果不空，則繼續(xù)向右遞歸前序查找if(this.right!=null){resNode=this.right.preOrderSearch(no);}return resNode;}//中序遍歷查找public HeroNode infixOrderSearch(int no){//判斷當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)是否為空，如果不為空，則遞歸中序查找HeroNode resNode=null;if(this.left!=null){resNode=this.left.infixOrderSearch(no);}if(resNode!=null){//說(shuō)明我們左子樹(shù)找到return resNode;}System.out.println("進(jìn)入中序查找");//如果找到，則返回，如果沒(méi)有找到，就和當(dāng)前節(jié)點(diǎn)比較，如果是則返回當(dāng)前節(jié)點(diǎn)if(this.no==no){return this;}//否則繼續(xù)進(jìn)行右遞歸的中序查找if(this.right!=null){resNode=this.right.infixOrderSearch(no);}return resNode;}//后序遍歷查找public HeroNode postOrderSearch(int no){//判斷當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)是否為空，如果不為空，則遞歸中序查找HeroNode resNode=null;if(this.left!=null){resNode=this.left.postOrderSearch(no);}if(resNode!=null){//說(shuō)明我們左子樹(shù)找到return resNode;}//如果左子樹(shù)沒(méi)有找到，則向右子樹(shù)遞歸進(jìn)行后序遍歷查找if(this.right!=null){resNode=this.right.postOrderSearch(no);}if(resNode!=null){//說(shuō)明我們右子樹(shù)找到return resNode;}System.out.println("進(jìn)入后序遍歷");//如果左右子樹(shù)都沒(méi)有找到，就比較當(dāng)前節(jié)點(diǎn)是不是if(this.no==no){return this;}return resNode;}}

總結(jié)

以上是生活随笔為你收集整理的遍历线索化二叉树+图解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。