在线性结构中， 各结点的逻辑关系是顺序的， 寻找某一结点的前趋结点和后继结点很方便。 对于二叉树， 由于它是非线性结构， 所以树中的结点不存在前趋和后继的概念， 但当我们对二叉树以某种方式遍历后， 就可以得到二叉树中所有结点的一个线性序列， 在这种意义下， 二叉树中的结点就有了前趋结点和后继结点。
二叉树通常采用二叉链表作为存储结构， 在这种存储结构下， 由于每个结点有两个分别指向其左儿子和右儿子的指针， 所以寻找其左、 右儿子结点很方便， 但要找该结点的前趋结点和后继结点则比较困难。
为方便寻找二叉树中结点的前趋结点或后继结点， 可以通过一次遍历记下各结点在遍历所得的线性序列中的相对位置。 保存这种信息的一种简单的方法是在每个结点增加两个指针域， 使它们分别指向依某种次序遍历时所得到的该结点的前趋结点和后继结点， 显然这样做要浪费相当数量的存储单元。
如果仔细分析一棵具有 n 个结点的二叉树， 就会发现,当它采用二叉链表作存储结构时， 二叉树中的所有结点共有n+1 个空指针域。 因此， 可以设法利用这些空指针碎来存放结点的前趋结点和后继结点的指针信息， 这种附加的指针称为“ 线索” 。 我们可以作这样的规定， 当某结点的左指针域为空时， 令其指向依某种方式遍历时所得到的该结点的前趋结点， 否则指向它的左儿子； 当某结点的右指针域为空时，令其指向依某种方式遍历时所得到的该结点的后继结点， 否则指向它的右儿子。
增加了线索的二叉链表称为线索链表， 相应的二叉树称为线索二叉树(Threaded Binary Tree)。
为了区分一个结点的指针是指向其儿子的指针还是指向其前趋或者后继的线索， 可以在每个结点上增加两个线索标志域 leftType 和 rightType， 这样线索链表的结点结构为：
一棵二叉树以某种方式遍历并使其变成线索二叉树的过程称为二叉树的线索化。对同一棵二叉树遍历的方式不同， 所得到的线索树也不同， 二叉树主要有前序、 中序和后序 3 种遍历方式， 所以线索树也有前序线索二叉树、 中序线索二叉树和后序线索二叉树3种。
3.2、中序线索二叉树的实现
这一节来实现中序遍历线索二叉树。
3.1.1、线索二叉树节点 /** * @Author 三分恶 * @Date 2020/10/11 * @Description 线索二叉树节点 */ public class ClueBinaryTreeNode { //节点数据 int data; //左儿子 ClueBinaryTreeNode leftNode; //右儿子 ClueBinaryTreeNode rightNode; //标识指针类型,其中0,1分别表示有无线索化，默认为0 int leftType; int rightType; }
3.1.2、创建中序线索二叉树
建立线索二叉树， 或者说， 对二叉树线索化， 实质上就是遍历一棵二叉树， 在遍历的过程中， 检査当前结点的左、 右指针域是否为空， 如果为空， 将它们改为指向前趋结点或后继结点的线索。
以图12的二叉树为例：
定义一个节点pre用来存储当前节点，类似指针。
从根节点1开始递归，如果当前节点为空，返回；遍历到4，此时4的前驱结点为null,结点5的前驱结点为2
遍历到5的时候指向前驱结点2，前驱结点2为上一层递归的指针，因此指向它的前驱结点就行，再把左指针类型置为1
如果当前节点的前驱结点pre的右指针为null,则将它设置为当前节点，此时即4的后继结点为2，并将右指针类型置为1
每处理一个节点，当前节点是下一个节点的前驱节点
来看一下具体实现：
/** * @Author 三分恶 * @Date 2020/10/11 * @Description 中序线索二叉树 */ public class ClueBinaryTree { private ClueBinaryTreeNode root; //根节点 private ClueBinaryTreeNode pre; //每个节点的前趋节点 public ClueBinaryTreeNode getRoot() { return root; } public void setRoot(ClueBinaryTreeNode root) { this.root = root; } /** * 构建中序线索二叉树 */ public void clueBinaryNodes() { clueBinaryNodes(root); } /** * 构建中序线索二叉树 * @param node 起始节点 */ public void clueBinaryNodes(ClueBinaryTreeNode node) { //当前节点如果为null，直接返回 if(node==null) { return; } //递归处理左子树 clueBinaryNodes(node.leftNode); //处理前驱节点 if(node.leftNode==null){ //让当前节点的左指针指向前驱节点 node.leftNode=pre; //改变当前节点左指针的类型 node.leftType=1; } //处理前驱的右指针，如果前驱节点的右指针是null(没有指下右子树) if(pre!=null&&pre.rightNode==null) { //让前驱节点的右指针指向当前节点 pre.rightNode=node; //改变前驱节点的右指针类型 pre.rightType=1; } //每处理一个节点，当前节点是下一个节点的前驱节点 pre=node; //处理右子树 clueBinaryNodes(node.rightNode); } }4、二叉查找树
二叉树的一个重要作用是用作查找。
4.1、二叉查找树的概念和操作二叉查找树定义：
又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树；
没有键值相等的节点。