概述
一般的二叉树，有左右子节点，如下图
- 对于叶子节点，它的左右子节点为空，有的非叶子节点可能只有一个子节点，而每一个节点又会占据一个空间，这样就会节约了这些创立进去的空间
- 线索化二叉树，利用了这些空间
线索化二叉树
线索化二叉树
- 如果节点的左子节点为空，则指向该节点的前驱节点
- 如果节点的右子节点为空，则指向该节点的后继节点
前驱和后继：
- 前驱：一个节点的前一个节点
- 后继：一个节点的后一个节点
- n个节点的二叉链表中含有n+1个为空的空间
- 依据遍历秩序的不同（即线索不同），线索二叉树可分为：前序线索二叉树、中序线索二叉树和后序线索二叉树
- 举个例子，将上图的一般二叉树线索化，如下图所示：依据前序遍历的后果，16的前驱节点是20，所以16的左子节点指向了20，16的后继节点是42，所以16的右子节点指向了42，以此类推
创立
基本思路：
- 采纳中序线索化的办法，先线索化左子树，再线索化以后节点，最初线索化右子树
- 1）线索化左子树
- 2）解决大以后节点的前驱节点：判断以后节点的左子节点是否为空，如果为空就把以后节点的左子节点指向前一个节点
- 3）解决以后节点的后继节点：判断以后节点的前驱节点是否为空，如果前一个节点不为空并且前以一个节点的右子节点为空，则把前一个节点的右子节点指向以后节点
- 4）让前驱节点指向以后节点
- 5）线索化右子树
- 留神：每一次递归，只能判断以后节点的左子节点和前驱节点的右子节点，因为没有方法晓得以后节点的下一个节点，只能晓得上一个节点
遍历
基本思路：
- 先从左子树循环的找到线索化节点，而后再从找到的这个节点，循环的去找她的线索化的右子节点
- 最初让以后节点指向后继节点
- 留神：因为咱们是中序线索化二叉树，所以第一个节点肯定是一个左子树的叶节点
代码如下
数据结构：
package 树;public class TreeNode { private Integer val;//序号 private TreeNode left;//左孩子 private TreeNode right;//右孩子 //leftType：0示意指向的左子树,如果1示意指向前驱节点 private int leftType; //rightType：0示意指向的是右子树，如果1示意指向后继节点 private int rightType; public TreeNode(int val){ this.val = val; } public Integer getVal() { return val; } public void setVal(Integer val) { this.val = val; } public TreeNode getLeft() { return left; } public void setLeft(TreeNode left) { this.left = left; } public TreeNode getRight() { return right; } public void setRight(TreeNode 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 "TreeNode{" + "val=" + val + '}'; }}具体算法：
package 树;public class ThreadedBinaryTree { //以后节点的上一个节点 private static TreeNode pre = null; //根节点 private static TreeNode root; private static final int IS_LEFT_CHILD = 0; //0示意是以后节点的左子节点指向的是左子树 private static final int IS_RIGHT_CHILD = 0; //0示意是以后节点的右子节点指向的是右子树 private static final int IS_PRE_NODE = 1; //1示意是以后节点的左子节点指向的是前驱节点 private static final int IS_AFTER_NODE = 1; //1示意是以后节点的右子节点指向的是后继节点 public static void setRoot(TreeNode root) { ThreadedBinaryTree.root = root; } //线索化遍历二叉树 public static void threadedList(){ //设置以后节点 TreeNode node = root; if (node == null) return; while (node != null){ //找到leftType == 1的节点 while (node.getLeftType() == IS_LEFT_CHILD){ node = node.getLeft(); } //打印以后节点 System.out.println(node.getVal()); //如果以后节点的右子节点指向的是后继节点，就统一输入 while (node.getRightType() == IS_AFTER_NODE){ node = node.getRight(); System.out.println(node.getVal()); } //替换这个遍历的节点 node = node.getRight(); } } //对二叉树进行中序线索化的办法 public static void threadedNodes(TreeNode node){ if (node == null) return; //1、先线索化左子树 threadedNodes(node.getLeft()); //2、线索化以后节点 //2.1 解决以后节点的前驱节点 if (node.getLeft() == null){ //批改以后节点的左子节点，指向前驱节点 node.setLeft(pre); node.setLeftType(IS_PRE_NODE); } //2.2 解决以后节点的后继节点 if (pre != null && pre.getRight() == null){ //让前驱节点的右子节点指向以后节点 pre.setRight(node); pre.setRightType(IS_AFTER_NODE); } //每次解决一个节点后，让下一个节点的前驱节点指向以后节点 pre = node; //3、线索化右子树 threadedNodes(node.getRight()); } public static void main(String[] args) { TreeNode node1 = new TreeNode(1); TreeNode node2 = new TreeNode(3); TreeNode node3 = new TreeNode(6); TreeNode node4 = new TreeNode(8); TreeNode node5 = new TreeNode(10); TreeNode node6 = new TreeNode(14); node1.setLeft(node2); node1.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); setRoot(node1); threadedNodes(node1); // TreeNode right = node3.getRight(); // TreeNode preNode = node5.getLeft(); // TreeNode afterNode = node5.getRight(); // System.out.println(right); // System.out.println(preNode); // System.out.println(afterNode); // threadedList(); }}因为算法如果用字数可能不太分明，倡议还是联合代码和图片本人走一遍流程