共计 3334 个字符，预计需要花费 9 分钟才能阅读完成。
概述
-
一般的二叉树，有左右子节点，如下图
- 对于叶子节点，它的左右子节点为空，有的非叶子节点可能只有一个子节点，而每一个节点又会占据一个空间，这样就会节约了这些创立进去的空间
- 线索化二叉树，利用了这些空间
线索化二叉树
-
线索化二叉树
- 如果节点的左子节点为空，则指向该节点的前驱节点
- 如果节点的右子节点为空，则指向该节点的后继节点
-
前驱和后继：
- 前驱：一个节点的前一个节点
- 后继：一个节点的后一个节点
- 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();}
}因为算法如果用字数可能不太分明，倡议还是联合代码和图片本人走一遍流程
正文完