一、链式存储结构
由于依次存储二叉树的空间利用率很低，所以在二叉树一般都采用链式存储结构中，利用链表的节点存储二叉树的各节点。 在二叉树中，该节点结构包括若干数据字段和若干指针字段，二叉链表至少包含3个域：数据域 data、左指针域 lchild和右指针域 rchild，如下图所示
其中，n 个结点的二叉链表中含有 n+1 [ 2n-(n-1)=n+1 ] 个空指针域
二、线索二叉树
传统的双链表只能表达父子关系，不能直接获得节点遍历中的前驱和后继。 引入有线索的二叉树是为了加快寻找节点前驱和后继的速度。
规定：若无左子树，令 lchild指向其前驱结点；若无右子树，令rchild执行指向其后继结点2添加两个标志字段以标识是指左/右儿童还是指前驱/继承人。
该标志位的含义如下。
我们把给出这种线索的二叉树称为线索链表，把对应的二叉树称为线索二叉树。 根据线索性质，线索二叉树可以分为前序线索二叉树、 中序线索二叉树和后序线索二叉树种。
1.1、中序线索二叉树
1.1.1 中序线索二叉树的构造
节点pre指的是刚才访问的节点，节点node指的是访问的节点，也就是说pre指的是node的前驱体。 在遍历过程中，检查节点的左指针是否为空，如果为空，则指向pre； 检查pre的右指针是否为空，如果为空，则指向node。
publicstaticvoidinthreadnode (node node ) if ) node==null )//节点为空且无法提供线索的返回； (//左子树inthreadnode(node.getleft ) )； //以当前节点if为线索(node.getleft ) )==null ) node.setleft(pre )； //将当前节点的左指针作为前驱节点node.setltag(1)； //修改当前节点的左指针类型，将前置节点(if(pre )！=nullpre.getright(==null ) (pre.setright ) ) node )； //将前驱节点的右指针移动到当前节点pre.setrtag(1)； //修改当前节点的右指针类型并指向后续节点) }pre=node； //每处理一个节点，使当前节点成为刚访问的节点//右部分树inthreadnode(node.getright ) )； } 1.1.2 中序线索二叉树的遍历
由于线索化后各节点的指向会发生变化，不能用传统的遍历方式，需要用新的方式遍历线索二叉树。 中顺序线索二叉树的节点中隐藏着线索二叉树的前驱和后续信息。 要遍历它，需要找到具有前驱节点的第一个左节点，依次寻找节点的后继。 中顺序线索在二叉树中寻找节点后继的法则是，如果其右标志为1，则右链为线索，指示其后继，否则，右部分树中最先访问的节点(右部分树中最左下的节点)为后继。
publicstaticvoidinthreadlist (node node ) {node=root； //保存当前正在遍历的节点，从root输入while(node！=null () while ) node.getltag )==0) ) {node=node.getLeft )； }system.out.println(node )； //打印当前节点while (node.get rtag )==1) ) /作为当前节点的后续节点的node=node.getRight )； system.out.println(node )； }node=node.getRight (； //按顺序更换要扫描的节点}} 1.1.3 中序线索二叉树完整代码
包树； publicclassinthreadedbinarytree { publicstaticvoidmain (string [ ] args ) noderoot=newnode(7，' a ' )； //构造二叉树的nodea=newnode(4，' b ' )； nodeb=newnode(9，' c '； nodec=newnode(2，' d '； noded=newnode(5，' e '； nodee=newnode(8，' f '； nodef=newnode(11，' g '； nodeg=newnode(1，' h '； nodeh=newnode(3，' I '； nodeI=newnode(10，' j '； nodej=newnode(12，' k '； root.setleft(a )； root.setright(b )； a .设置左(c )； a .设置权限(d )； b .设置左(e )； b.setright(f； c.setleft(g； c.setright(h )； f.setleft(I； f.setright(j )； 内部binaryt
ree thread=new inThreadBinaryTree(root);inThreadBinaryTree.inthreadNode(root);//创建中序线索二叉树inThreadBinaryTree.inthreadlist(root);//遍历中序线索二叉树}}class Node{private int data;private String name;private Node left;//默认nullprivate Node right;//默认null//若ltag == 0,说明指向的是左子树;ltag == 1，指向的是前驱结点 //若rtag == 0,说明指向的是右子树;rtag == 1，指向的是后继结点private int ltag;private int rtag;public Node(int data,String name) {this.data=data;this.name=name;}public int getData() {return data;}public void setData(int data) {this.data = data;}public String getName() {return name;}public void setName(String name) {this.name = name;}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 getLtag() {return ltag;}public void setLtag(int ltag) {this.ltag = ltag;}public int getRtag() {return rtag;}public void setRtag(int rtag) {this.rtag = rtag;}@Overridepublic String toString() {//重写toString方法return "Node [data=" + data + ", name=" + name + "]";}}//中序线索化二叉树(左->根->右)class inThreadBinaryTree{private static Node root;private static Node pre=null;//pre表示刚刚访问过的结点，即前一个结点public inThreadBinaryTree(Node root) {//inThreadBinaryTree构造函数this.root=root;}public static void inthreadNode(Node node) {if(node==null) {//结点为空无法线索化return;}//线索化左子树inthreadNode(node.getLeft());//线索化当前结点if(node.getLeft()==null) {node.setLeft(pre);//让当前结点的左指针指向前驱结点node.setLtag(1);//修改当前结点的左指针的类型,指向前驱结点}if(pre!=null&&pre.getRight()==null) {pre.setRight(node);//让前驱结点的右指针指向当前结点pre.setRtag(1);//修改当前结点的右指针的类型,指向后继结点}pre=node;//每处理一个结点后，让当前结点成为刚刚访问过的结点//线索化右子树inthreadNode(node.getRight());}//中序线索化二叉树的遍历(遍历次序和中序遍历保持一致)public static void inthreadlist(Node node) {node=root;//存储当前遍历的结点，从root开始while(node!=null) {while(node.getLtag()==0) {node=node.getLeft();}System.out.println(node);//打印当前结点while(node.getRtag()==1) {//获取到当前结点的后继结点node=node.getRight();System.out.println(node);}node=node.getRight();//依次替换遍历的结点}}}运行结果：
Node [data=1, name=H]Node [data=2, name=D]Node [data=3, name=I]Node [data=4, name=B]Node [data=5, name=E]Node [data=7, name=A]Node [data=8, name=F]Node [data=9, name=C]Node [data=10, name=J]Node [data=11, name=G]Node [data=12, name=K]该实例的二叉树图如下图所示：
2.1、前序线索二叉树和后序线索二叉树