對于n個結點的二叉樹，在二叉鏈存儲結構中有n+1個空鏈域，利用這些空鏈域存放在某種遍歷次序下該結點的前驅結點和后繼結點的指針，這些指針稱為線索，加上線索的二叉樹稱為線索二叉樹。
根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。

注意：線索鏈表解決了無法直接找到該結點在某種遍歷序列中的前驅和后繼結點的問題，解決了二叉鏈表找左、右孩子困難的問題。

? ? 遍歷線索化二叉樹：因為線索化后，各個結點指向有變化，因此原來的遍歷方式不能使用，這時需要使用新的方式遍歷線索化二叉樹，各個節點可以通過線型方式遍歷，因此無需使用遞歸方式，這樣也提高了遍歷的效率。
public class ThreadedBinaryTreeDemo {
? ? public static void main(String[] args) {
? ? ? ? ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
? ? ? ? MyNode a = new MyNode("A");
? ? ? ? MyNode b = new MyNode("B");
? ? ? ? MyNode c = new MyNode("C");
? ? ? ? MyNode e = new MyNode("E");
? ? ? ? MyNode f = new MyNode("F");
? ? ? ? MyNode g = new MyNode("G");
? ? ? ? //手動創建樹
? ? ? ? threadedBinaryTree.setRoot(a);
? ? ? ? a.left=b;
? ? ? ? a.right=c;
? ? ? ? b.left=e;
? ? ? ? b.right=f;
? ? ? ? c.left=g;
? ? ? ? System.out.println("未線索化前e節點的前驅節點和后驅");
? ? ? ? System.out.println("F號結點的前驅結點為："+e.left);//3
? ? ? ? System.out.println("F號結點的后繼結點為："+e.right);//1
? ? ? ? System.out.println("中序線索化后e節點的前驅節點和后驅");
? ? ? ? threadedBinaryTree.infixThreadedNodes();
? ? ? ? System.out.println("F號結點的前驅結點為："+e.left);//3
? ? ? ? System.out.println("F號結點的后繼結點為："+e.right);//1
? ? }
}
//定義能實現線索化的二叉樹
class ThreadedBinaryTree {
? ? MyNode root;
? ? MyNode pre=null;//指向當前節點的前驅節點 ?遞歸過程中pre總是保留前一個節點
? ? //為了實現線索化，需要創建指向當前節點的前驅結點的指針
? ? public void setRoot(MyNode root) {
? ? ? ? this.root = root;
? ? }
? ? public void infixThreadedNodes() {
? ? ? ? this.infixThreadedNodes(root);
? ? }
? ? //編寫對二叉樹進行中序線索化的方法
? ? public void infixThreadedNodes(MyNode node) {
? ? ? ? if (node == null) {//節點為空 不能線索化
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? ? ? //線索化左子樹
? ? ? ? ? ? infixThreadedNodes(node.left);
? ? ? ? ? ? if (node.left==null){
? ? ? ? ? ? ? ? node.left=pre;
? ? ? ? ? ? ? ? node.leftType=1;
? ? ? ? ? ? }
? ? ? ? ? ? //處理后繼節點
? ? ? ? ? ? if (pre!=null && pre.right==null){
? ? ? ? ? ? ? ? pre.right=node;
? ? ? ? ? ? ? ? pre.rightType=1;
? ? ? ? ? ? }
? ? ? ? ? ? //每處理一個節點，讓當前節點是下一個節點的前驅節點
? ? ? ? ? ? pre=node;
? ? ? ? ? ? //線索化右子樹
? ? ? ? ? ? infixThreadedNodes(node.right);
? ? }
}
class ?MyNode{
? ? String name;
? ? MyNode left;
? ? MyNode right;
? ? //說明
? ? //1.如果leftType==0 表示指向的是左子樹，為1 表示指向前驅節點
? ? //2.如果rightType==0 表示指向的是右子樹，為1 表示指向后繼節點
? ? int leftType;
? ? int rightType;
? ? public MyNode(String name) {
? ? ? ? this.name = name;
? ? }
? ? //重寫toString方法
? ? @Override
? ? public String toString() {
? ? ? ? return "Node{" +
? ? ? ? ? ? ? ? "name='" + name + '\'' +
? ? ? ? ? ? ? ? '}';
? ? }
}運行結果：

?