?

?

public class ThreadedBinaryTreeDemo {public static void main(String[] args) {// 先創建一棵二叉樹ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();// 創建需要的結點HeroNode root = new HeroNode(1, "宋江");HeroNode node2 = new HeroNode(3, "吳用");HeroNode node3 = new HeroNode(6, "盧俊義");HeroNode node4 = new HeroNode(8, "林沖");HeroNode node5 = new HeroNode(10, "關勝");HeroNode node6 = new HeroNode(14, "武松");binaryTree.setRoot(root);root.setLeft(node2);root.setRight(node3);// 設置父結點node2.setParent(root);node3.setParent(root);node2.setLeft(node4);node2.setRight(node5);// 設置父結點node4.setParent(node2);node5.setParent(node2);node3.setLeft(node6);// 設置父結點node6.setParent(node3);// 測試中序// 測試線索化 // binaryTree.threadedNodes(root); //8,3,10,1,14,6 // // HeroNode leftNode = node5.getLeft(); // HeroNode rightNode = node5.getRight(); // System.out.println(leftNode.getNo()+" "+leftNode.getName()); // System.out.println(rightNode.getNo()+" "+rightNode.getName()); // // // 遍歷線索化二叉樹 // binaryTree.threadedList();// 測試后序// 測試線索化binaryTree.threadedNodesPost(root); //8,10,3,14,6,1HeroNode leftNode = node6.getLeft();HeroNode rightNode = node6.getRight();System.out.println(leftNode.getNo()+" "+leftNode.getName());System.out.println(rightNode.getNo()+" "+rightNode.getName());// 遍歷線索化二叉樹binaryTree.threadedListPost();} }class ThreadedBinaryTree{private HeroNode root;private HeroNode pre; // 線索化使用,總是指向當前結點的前驅結點public void setRoot(HeroNode root) {this.root = root;}// 對二叉樹進行中序線索化public void threadedNodes(HeroNode node){if(null == node) {return;}// 中序線索化,先線索化左子樹,再線索化當前結點,最后線索話右子樹// 1.先線索化左子樹threadedNodes(node.getLeft());// 2.再線索化當前結點if(node.getLeft() == null){node.setLeft(pre);node.setLeftType(1);}// 處理后繼結點if(null != pre && pre.getRight() == null){// 讓前驅結點的右指針指向當前結點pre.setRight(node);// 改變類型pre.setRightType(1);}// 讓當前結點成為下一個結點的前驅結點pre = node;// 3.再線索化右子樹threadedNodes(node.getRight());}// 中序遍歷線索化二叉樹的方法public void threadedList(){// 定義一個變量,存儲當前遍歷的結點,從root開始HeroNode node = root;while(null != node){while(node.getLeftType() == 0){node = node.getLeft();}System.out.println(node);while(node.getRightType() == 1){node = node.getRight();System.out.println(node);}node = node.getRight();}}// 對二叉樹進行后序線索化public void threadedNodesPost(HeroNode node){if(null == node) {return;}// 后序線索化,先線索化左子樹,再線索話右子樹,最后線索化當前結點// 1.先線索化左子樹threadedNodesPost(node.getLeft());// 2.再線索化右子樹threadedNodesPost(node.getRight());// 3.最后線索化當前結點if(node.getLeft() == null){node.setLeft(pre);node.setLeftType(1);}// 處理后繼結點if(null != pre && pre.getRight() == null){// 讓前驅結點的右指針指向當前結點pre.setRight(node);// 改變類型pre.setRightType(1);}// 讓當前結點成為下一個結點的前驅結點pre = node;}//后序遍歷線索化二叉樹可以參考該博客https://www.cnblogs.com/lishanlei/p/10707830.html // 后序遍歷線索化二叉樹的方法, 后序遍歷線索話二叉樹需要利用父結點public void threadedListPost(){// 定義一個變量,存儲當前遍歷的結點,從root開始HeroNode node = root;while(null != node && node.getLeftType() == 0){node = node.getLeft();}while(null != node){//右節點是線索if(node.getRightType() == 1){System.out.println(node);pre = node;node = node.getParent();}else{//如果上個處理的節點是當前節點的右節點if(node.getRight() == pre){System.out.println(node);if(node == root){return;}pre = node;node = node.getParent();}else{node = node.getRight();while(null != node && node.getLeftType() == 0){node = node.getLeft();}}}}} }class HeroNode{private int no;private String name;private HeroNode left; // 默認為nullprivate HeroNode right; // 默認為null//leftType == 0, 表示指向左子樹. leftType == 1, 表示指向前驅結點.//rightType == 0, 表示指向右子樹. rightType == 1, 表示指向后繼結點.private int leftType;private int rightType;public HeroNode getParent() {return parent;}public void setParent(HeroNode parent) {this.parent = parent;}private HeroNode parent; // 父結點的指針public HeroNode(int no, String name) {this.no = no;this.name = name;}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 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 + '\'' +'}';} }

?

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的数据结构: 线索化二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。