我们先来看一张之前整理过的一张二叉树的链式存储结构

1、每个数据域，都有2个指针域，分别指向该节点的左孩子、右孩子，但是每个节点前驱、后继，要知道的话需要遍历整棵树，这在时间上耗费很大。

2、另外，在叶子节点中，我们可以看到如图，每个节点都会浪费2块存储空间，N个节点的二叉树，2N个指针域，连接线为2N-1，那么会有2N-(N-1) = N+1个指针域浪费掉。

为了优化以上2个问题，我们引入了线索二叉树。

我们将二叉树中序遍历后。

我们把所有空指针域的右孩子，指向它的后继节点。如图

空指针域的左孩子，指向它的前驱。如图

我们把这种指向前序和后继的指针称为线索，加上线索的链表称为线索链表，相应的二叉树称为线索二叉树。

这样我们的指针域就都被使用上了，但是还存在另外一个问题，我们怎么区分左孩子、右孩子、前驱、后继，这些指针域呢？

所以这里我们要改下存储结构，对每个指针域增加一个标示ltag、rtag，如图

存储结构转化，0代表左孩子、右孩子指针域，1代表前驱、后继指针域，如图。

源码来自：http://www.cnblogs.com/ttltry-air/archive/2012/07/10/2584312.html

package com.test;

class TBTreeNode {
	int data;
	int LTag; // 0,1
	int RTag; // 0,1
	TBTreeNode lchild;
	TBTreeNode rchild;

	public TBTreeNode(int data) {
		this(data, null, null, 0, 0);
	}

	public TBTreeNode(int data, TBTreeNode lchild, TBTreeNode rchild, int LTag,
			int RTag) {
		this.data = http://www.mamicode.com/data;>