数据结构--线索化二叉树（Java）
<!-- more -->
博客阐明
文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！
阐明
- n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，寄存指向该结点在某种遍历秩序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。依据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 一个结点的前一个结点，称为前驱结点
- 一个结点的后一个结点，称为后继结点
代码
package cn.guizimo.thread.tree;/** * @author guizimo * @date 2020/8/7 11:08 上午 */public class ThreadTree { 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(); //遍历 threadedBinaryTree.threadedList(); }}/** * 二叉树 */class ThreadedBinaryTree { //根节点 private HeroNode root; //辅助节点 private HeroNode pre = null; public void setRoot(HeroNode root) { this.root = root; } public void threadedNodes() { this.threadedNodes(root); } //中序遍历 public void threadedList() { HeroNode node = root; while (node != null) { 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 threadedNodes(HeroNode node) { if(node == null) { return; } threadedNodes(node.getLeft()); if(node.getLeft() == null) { node.setLeft(pre); node.setLeftType(1); } if (pre != null && pre.getRight() == null) { pre.setRight(node); pre.setRightType(1); } pre = node; threadedNodes(node.getRight()); } //删除二叉树的节点 public void delNode(int no) { if (root != null) { if (root.getNo() == no) { root = null; } else { root.delNode(no); } } else { System.out.println("二叉树为空"); } } //前序 public void preOrder() { if (this.root != null) { this.root.preOrder(); } else { System.out.println("二叉树为空"); } } //中序 public void infixOrder() { if (this.root != null) { this.root.infixOrder(); } else { System.out.println("二叉树为空"); } } //后序 public void postOrder() { if (this.root != null) { this.root.postOrder(); } else { System.out.println("二叉树为空"); } } //前序查找 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 this.root.postOrderSearch(no); } else { return null; } }}/** * 节点 */class HeroNode { private int no; private String name; private HeroNode left; private HeroNode 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; } private int leftType; 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; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } //删除节点 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); } } //前序 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); } //前序遍历查找 public HeroNode preOrderSearch(int no) { if (this.no == no) { return this; } HeroNode resNode = null; //判断左子树 if (this.left != null) { resNode = this.left.preOrderSearch(no); } if (resNode != null) { return resNode; } //判断右子树 if (this.right != null) { resNode = this.right.preOrderSearch(no); } return resNode; } //中序遍历查找 public HeroNode infixOrderSearch(int no) { HeroNode resNode = null; if (this.left != null) { resNode = this.left.infixOrderSearch(no); } if (resNode != null) { return resNode; } if (this.no == no) { return this; } if (this.right != null) { resNode = this.right.infixOrderSearch(no); } return resNode; } //后序遍历查找 public HeroNode postOrderSearch(int no) { HeroNode resNode = null; if (this.left != null) { resNode = this.left.postOrderSearch(no); } if (resNode != null) { return resNode; } if (this.right != null) { resNode = this.right.postOrderSearch(no); } if (resNode != null) { return resNode; } if (this.no == no) { return this; } return resNode; }}感激
尚硅谷万能的网络
以及勤奋的本人