本文介绍了线索二叉树的概念，以及线索二叉树的Java的实现。如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

1 线索二叉树的概述

如果对二叉树的概念不是很了解，可以先看这篇文章：二叉树的入门以及Java实现案例详解。二叉树的概念在此不做赘述。

对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个引用域，所以一共是2n个引用域。而n个结点的二叉树一共有n-1条分支线数，也就是说，其实是存在2n-(n-1)=n＋1个空引用域。这些空间不存储任何事物，白白的浪费着内存的资源。

如下图：

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的引用，这种方法增加了存储开销，不可取；二是利用二叉树的空链引用。

我们可以考虑利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点的地址，空left存放前驱，空right存放后继。我们把这种指向前驱和后继的引用称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

对二叉树以某种遍历方式（如先序、中序、后序或层序）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

采用中序遍历线索化之后的数据结构如下：

可以看到，它充分利用了空引用域的空间（这等于节省了空间），又保证了创建时的一次遍历就可以终生受用前驱后继的信息（这意味着节省了时间）。所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

2 节点设计

线索二叉树中的线索能记录每个结点前驱和后继信息。为了区别线索引用和孩子引用，在每个结点中设置两个标志ltag和rtag。

当tag和rtag为0时，left和right分别是指向左孩子和右孩子的指针；否则，left是指向结点前驱的线索(pre)，right是指向结点的后继线索(suc)。由于标志只占用一个二进位，每个结点所需要的存储空间节省很多。

现将二叉树的结点结构重新定义如下：

leftltagdatartagright

其中：ltag=0 时left指向左儿子；ltag=1 时left指向前驱；rtag=0 时right指向右儿子；rtag=1 时right指向后继。

3 中序线索二叉树的构建

现提供中序线索二叉树的构建的完整Java代码，先序、后续线索二叉树的构建和中序的构建基本一致，都是在先、中、后序遍历的方法的基础上改进而来的，如果对关于二叉树的4种遍历方式不了解的，可以看这篇文章：二叉树的4种遍历方式详解以及Java代码的完整演示。

publicclassThreadedBinaryTree<E>{/***外部保存根节点的引用*/privateBinaryTreeNode<E>root;/***线索化的时候保存刚刚访问过的前驱节点*/privateBinaryTreeNode<E>pre;/***树节点的数量*/privateintsize;/***内部节点对象**@param<E>数据类型*/publicstaticclassBinaryTreeNode<E>{//数据域Edata;//左子节点/前驱BinaryTreeNode<E>left;//右子节点/后继BinaryTreeNode<E>right;booleanltag;//false：指向左子节点、true：前驱线索booleanrtag;//false：指向右子节点、true：后继线索publicBinaryTreeNode(Edata){this.data=data;}@OverridepublicStringtoString(){returndata.toString();}}/***空构造器*/publicThreadedBinaryTree(){}/***构造器,初始化root节点**@paramroot根节点数据*/publicThreadedBinaryTree(Eroot){checkNullData(root);this.root=newBinaryTreeNode<>(root);size++;}/***添加子节点**@paramparent父节点的引用*@paramdata节点数据*@paramleft是否是左子节点,true是;false否*/publicBinaryTreeNode<E>addChild(BinaryTreeNode<E>parent,Edata,booleanleft){checkNullParent(parent);checkNullData(data);BinaryTreeNode<E>node=newBinaryTreeNode<>(data);if(left){if(parent.left!=null){thrownewIllegalStateException("该父节点已经存在左子节点,添加失败");}parent.left=node;}else{if(parent.right!=null){thrownewIllegalStateException("该父节点已经存在右子节点,添加失败");}parent.right=node;}size++;returnnode;}/***是否是空树**@returntrue是;false否*/publicbooleanisEmpty(){returnsize==0;}/***返回节点数**@return节点数*/publicintsize(){returnsize;}/***获取根节点**@return根节点;或者null--表示空树*/publicBinaryTreeNode<E>getRoot(){returnroot;}/***获取左子节点**@paramparent父节点引用*@return左子节点或者null--表示没有左子节点*/publicBinaryTreeNode<E>getLeft(BinaryTreeNode<E>parent){returnparent==null?null:parent.left;}/***获取右子节点**@paramparent父节点引用*@return右子节点或者null--表示没有右子节点*/publicBinaryTreeNode<E>getRight(BinaryTreeNode<E>parent){returnparent==null?null:parent.right;}/***数据判null**@paramdata添加的数据*/privatevoidcheckNullData(Edata){if(data==null){thrownewNullPointerException("数据不允许为null");}}/***检查父节点是否为null**@paramparent父节点引用*/privatevoidcheckNullParent(BinaryTreeNode<E>parent){if(parent==null){thrownewNoSuchElementException("父节点不能为null");}}/***将以root为根节点的二叉树线索化中序法**@returntrue线索化成功;false线索化失败*/publicbooleaninThread(){if(isEmpty()){returnfalse;}inThread(getRoot());returntrue;}/***将以root为根节点的二叉树线索化中序法**@paramroot节点,从根节点开始*/privatevoidinThread(BinaryTreeNode<E>root){BinaryTreeNode<E>left=getLeft(root);if(left!=null){//如果左子节点不为null,则继续递归遍历该左子节点inThread(left);}/*相比于中序遍历，中间多了如下步骤*/else{//如果左子节点为null，因为其前驱结点刚刚访问过，将左子节点设置为线索//完成前驱结点的线索化root.ltag=true;root.left=pre;}//如果前驱没有右子节点，那就把当前节点当作前驱结点的后继节点if(pre!=null&&null==pre.right){pre.rtag=true;pre.right=root;}//每次将当前节点设置为pre，下一个节点就把该节点当成前驱结点pre=root;BinaryTreeNode<E>right=getRight(root);if(right!=null){//如果右子节点不为null,则继续递归遍历该右子节点inThread(right);}}/***中序遍历线索二叉树*/publicvoidinThreadList(BinaryTreeNode<E>root){if(root==null){return;}//查找中序遍历的起始节点while(root!=null&&!root.ltag){root=root.left;}while(root!=null){System.out.print(root.data+",");//如果右子节点是线索if(root.rtag){root=root.right;}else{//有右子节点，遍历右子节点root=root.right;//如果右子节点不为null，并且右子节点的左子结点存在while(root!=null&&!root.ltag){root=root.left;}}}}}

3.1 测试

publicclassThreadTreeTest{/***构建二叉树,添加根节点r*/ThreadedBinaryTree<String>integerThreadedBinaryTree=newThreadedBinaryTree<>("r");/***构建二叉树*/@BeforepublicvoidbuildTree(){/*构建二叉树*/ThreadedBinaryTree.BinaryTreeNode<String>r=integerThreadedBinaryTree.getRoot();//添加r根节点的左子结点aThreadedBinaryTree.BinaryTreeNode<String>a=integerThreadedBinaryTree.addChild(r,"a",true);//添加r根节点的右子结点bThreadedBinaryTree.BinaryTreeNode<String>b=integerThreadedBinaryTree.addChild(r,"b",false);//添加a节点的左子结点cThreadedBinaryTree.BinaryTreeNode<String>c=integerThreadedBinaryTree.addChild(a,"c",true);//添加a节点的右子结点dThreadedBinaryTree.BinaryTreeNode<String>d=integerThreadedBinaryTree.addChild(a,"d",false);//添加b节点的左子结点eThreadedBinaryTree.BinaryTreeNode<String>e=integerThreadedBinaryTree.addChild(b,"e",true);//添加b节点的右子结点fThreadedBinaryTree.BinaryTreeNode<String>f=integerThreadedBinaryTree.addChild(b,"f",false);//添加c节点的左子结点gThreadedBinaryTree.BinaryTreeNode<String>g=integerThreadedBinaryTree.addChild(c,"g",true);//添加c节点的右子结点hThreadedBinaryTree.BinaryTreeNode<String>h=integerThreadedBinaryTree.addChild(c,"h",false);//添加d节点的左子结点iThreadedBinaryTree.BinaryTreeNode<String>i=integerThreadedBinaryTree.addChild(d,"i",true);//添加f节点的左子结点jThreadedBinaryTree.BinaryTreeNode<String>j=integerThreadedBinaryTree.addChild(f,"j",true);}/***中序线索二叉树*/@Testpublicvoidtest2(){//线索化System.out.println(integerThreadedBinaryTree.inThread());//线索化之后进行遍历,效率更高integerThreadedBinaryTree.inThreadList(integerThreadedBinaryTree.getRoot());//gchaidrebjf}}

作者：刘Java