共计 4069 个字符，预计需要花费 11 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、线索化二叉树
1、线索化二叉树
在介绍线索化二叉树之前，咱们先看一个案例，我先画一棵二叉树，如图 1 所示：
图片
如果咱们对图 1 中的二叉树进行中序遍历时，后果为：4 2 5 1 3 6，咱们认真察看图 1 中的二叉树时，发现 4 5 6 节点的左右指针没有用上，3 节点的左指针也没用上；如果咱们心愿利用到各个节点的左右指针，让各个节点能够指向本人的前后节点，那咱们就应用线索化二叉树。
线索化二叉树的根本介绍；
（1）前驱节点：就是以中序遍历形式遍历二叉树，某一个节点的前一个节点，例如图 1 中的 5 节点，看图 1 中的中序遍历后果：4 2 5 1 3 6，5 节点的后面是 2 节点，所以 5 节点的前驱节点是 2 节点；一个节点有前驱节点的前提是该节点的左子节点是空的并且该节点有前一个节点，例如 5 节点的左子节点就为空且中序遍历进去时，5 节点就有前一个节点，而 4 节点没有前一个节点，所以没有前驱节点；通常前驱节点是该节点的父节点或者父节点的父节点，依此类推。
（2）后继节点：就是以中序遍历形式遍历二叉树，某一个节点的后一个节点，例如图 1 中的 5 节点，看图 1 中的中序遍历后果：4 2 5 1 3 6，5 节点的前面是 1 节点，所以 5 节点的后继节点是 1 节点；一个节点有后继节点的前提是该节点的右子节点是空的并且该节点前面有一个节点，例如 5 节点的右子节点就为空且中序遍历进去时，5 节点就有后一个节点，而 6 节点的右子节点尽管为空然而前面没有节点了，所以 6 节点没有后继节点；通常后继节点是该节点的父节点或者父节点的父节点，依此类推。
（3）n 个结点的二叉链表中含有 n +1（公式 2n-(n-1)=n+1）个空指针域；利用二叉链表中的空指针域，寄存指向结点在某种遍历秩序下的前驱和后继结点的指针 (这种附加的指针称为 ” 线索 ”)。
（4）这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树依据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树。
好，咱们将图 1 的二叉树加上指向前驱节点的指针和指向后继节点的指针，而后就失去如下图 2 的中序线索二叉树；
图片
留神：彩色的箭头示意指向前驱节点的指针，橙色的箭头示意指向后继节点的指针。
好了，咱们当初用代码实现一把图 2 中的中序线索二叉树，并打把 4 节点的后继节点、5 节点的前驱节点和后继节点、3 节点的前驱节点、6 节点的前驱节点打印进去，看看是否图 2 所指的一样。
（1）写一个节点类 Node：
public class Node {
private int no;
private Node left;
private Node right;
// 如果为 0，示意左子树；如果为 1，示意前驱节点
private int leftType;
// 如果为 0，示意右子树；如果为 1，示意后继节点
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 Node(int no) {
super();
this.no = no;}
public Node getLeft() {
return left;}
public void setLeft(Node left) {
this.left = left;}
public Node getRight() {
return right;}
public void setRight(Node right) {
this.right = right;}
public int getNo() {
return no;}
}
（2）写一个对二叉树进行中序线索化的类 Test：
public class Test {
private Node root;
static Node[] nodes;
// 创立指向以后节点的前驱节点的指针
private Node pre;
public static void main(String[] args) {
}
// 打印以后节点的前驱节点
private void printPreNode(Node node) {
if (node == null) {System.out.println("该节点为空，所以没有前驱节点");
} else {if (node.getLeft() != null && node.getLeftType() == 1) {Node left = node.getLeft();
System.out.println(node.getNo() + "节点的前驱节点为：" + left.getNo()
+ "节点");
} else {System.out.println("没有前驱节点");
}
}}
// 打印以后节点的后继节点
private void printPostNode(Node node) {
if (node == null) {System.out.println("该节点为空，所以没有后继节点");
} else {if (node.getRight() != null && node.getRightType() == 1) {Node right = node.getRight();
System.out.println(node.getNo() + "节点的后继节点为：" + right.getNo()
+ "节点");
} else {System.out.println("没有后继节点");
}
}}
private void threadedNodes() {
if (root != null) {threadedNodes(root);
} else {System.out.println("根节点为空，不能对二叉树进行中序线索化");
}}
// 创立一棵图 1 的二叉树
private void createBinaryTree() {
nodes = new Node[6];
for (int i = 0; i < nodes.length; i++) {nodes[i] = new Node(i + 1);
}
root = nodes[0];
root.setLeft(nodes[1]);// 根节点的左子节点是 2
root.setRight(nodes[2]);// 根节点的右子节点是 3
nodes[1].setLeft(nodes[3]);// 2 节点的左子节点是 4
nodes[1].setRight(nodes[4]);// 2 节点的右子节点是 5
nodes[2].setRight(nodes[5]);// 3 节点的右子节点是 6 }
// 对二叉树进行中序线索化
private void threadedNodes(Node node) {
// 不能进行线索化
if (node == null) {return;}
// 线索化左子树
threadedNodes(node.getLeft());
// 线索化以后节点
threadedCurrentNodes(node);
// 线索化右子树
threadedNodes(node.getRight());}
// 线索化以后节点
private void threadedCurrentNodes(Node node) {
// 解决以后的左子节点，把以后的左子节点置为前驱节点（如果 pre 不为空）if (node.getLeft() == null) {node.setLeft(pre);
node.setLeftType(1);
}
// 解决后继节点
if (pre != null && pre.getRight() == null) {
// 让前驱节点的右子节点指向以后节点
pre.setRight(node);
pre.setRightType(1);
}
pre = node;}
}
查找 4 节点的后继节点，程序调用如下所示：
public static void main(String[] args) {
Test test = new Test();
// 创立一棵图 2 中的二叉树
test.createBinaryTree();
// 对二叉树进行中序线索化
test.threadedNodes();
// 查找 4 节点的后继节点
test.printPostNode(nodes[3]);}
查找 4 节点的后继节点，日志打印如下所示：
图片
查找 5 节点的前驱节点和后继节点，程序调用如下所示：
public static void main(String[] args) {
Test test = new Test();
// 创立一棵图 2 中的二叉树
test.createBinaryTree();
// 对二叉树进行中序线索化
test.threadedNodes();
// 查找 5 节点的前驱节点
test.printPreNode(nodes[4]);
// 查找 5 节点的后继节点
test.printPostNode(nodes[4]);}
查找 5 节点的前驱节点和后继节点，日志打印如下所示：
图片
查找 3 节点的前驱节点，程序调用如下所示：
public static void main(String[] args) {
Test test = new Test();
// 创立一棵图 2 中的二叉树
test.createBinaryTree();
// 对二叉树进行中序线索化
test.threadedNodes();
// 查找 3 节点的前驱节点
test.printPreNode(nodes[2]);}
查找 3 节点的前驱节点，日志打印如下所示：
图片
查找 6 节点的前驱节点，程序调用如下所示：
public static void main(String[] args) {
Test test = new Test();
// 创立一棵图 2 中的二叉树
test.createBinaryTree();
// 对二叉树进行中序线索化
test.threadedNodes();
// 查找 6 节点的前驱节点
test.printPreNode(nodes[5]);}
查找 6 节点的前驱节点，日志打印如下所示：
图片