• 线索二叉树相关由来和总结
  • 中序线索二叉树构造(带头结点)

一、线索二叉树由来

两点由来：

  • 空间的浪费 : 在使用二叉链表的存储结构的过程中，会存在大量的空指针域，为了充分利用这些空指针域，引申出了“线索二叉树”。对于一个有n个节点的二叉链表，每个节点有指向左右节点的2个指针域，整个二叉链表存在2n个指针域。而n个节点的二叉链表有n-1条分支线，那么空指针域的个数=2n-(n-1) = n+1个空指针域，从存储空间的角度来看，这n+1个空指针域浪费了内存资源。
  • 想知道前驱和后继：如果我们想知道按中序方式遍历二叉链表时某一个节点的前驱节点或者后继节点时，必须要按中序方式遍历二叉链表才能够知道结果，每次需要结果时都需要进行一次遍历，所以可以考虑提前存储这种前驱和后继的关系来提高时间效率。

综合上面两点分析，我们可以通过充分利用二叉链表中的空指针域，存放节点在某种遍历方式下的前驱和后继节点的指针。我们把这种指向前驱和后继的指针称为线索(Thread)，加上线索的二叉链表成为线索链表，对应的二叉树就成为“线索二叉树(Threaded Binary Tree)”。

  • 我们按照上面的规定，若一个结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。
  • 为了避免混淆，需要改变普通的二叉树结构，增加两个标记域ltag，rtag，当ltag为true时，表示左边是前驱，为false时，表示是左儿子；同理，当rtag为true时，表示右边是后驱，为false时，表示是右儿子；

线索二叉树 - 图1

线索二叉树 - 图2

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索，加上线索的二叉树成为线索二叉树。例如下面的树进行线索化:

线索二叉树 - 图3

这里给出结点结构：

  1. public class BiThrTree<E>{
  3.     private static final boolean LINK = false;  //指针
  4.     private static final boolean THREAD = true;  //线索
  6.     private class Node{
  7.         public E e;
  8.         public Node left,right;
  9.         public boolean ltag;    //false表示left指向左孩子   true表示left指向前驱
  10.         public boolean rtag;    //false表示right指向右孩子  true表示right指向后继
  12.         public Node(E e, Node left, Node right, boolean ltag, boolean rtag) {
  13.             this.e = e;
  14.             this.left = left;
  15.             this.right = right;
  16.             this.ltag = ltag;
  17.             this.rtag = rtag;
  18.         }
  20.         public Node(E e) {
  21.             this(e,null,null,LINK,LINK); //默认指向左右孩子
  22.         }
  23.         public Node() {
  24.             this(null,null,null,LINK,LINK); //默认指向左右孩子
  25.         }
  26.     }
  28.     private Node dummyHead;  //虚拟头结点
  29.     private Node root;   //根结点
  30.     private Node pre;    //pre指针 指向前一个结点
  31. }

二、线索二叉树的构造

我们这里先讨论中序线索二叉树，看下图的构建过程，实现为指向左右儿子，虚线为线索（指向前驱和后继），对二叉树以某种次序遍历使得其变为线索二叉树的过程叫做线索化。

线索二叉树 - 图4线索二叉树 - 图5

遍历的方法 ：

  • 寻找一个后继的方法是：若其右标志是true(THREAD)，则右边为线索，指示其后继；否则，遍历右子树最先访问的结点(也就是右子树最左下的结点)；
  • 同理，所以寻找一个前驱的方法是：若其左标志是true，则左边为线索，指示其前驱；否则，遍历左子树最后访问的结点(也就是左子树最右下的结点)。

然后就是注意设置双向链表头结点的问题：

线索二叉树 - 图6

线索化的过程:

线索二叉树 - 图7

实现代码如下，其中测试用例就是用的上面图的例子，建树使用下标对应，不懂可以看看这篇博客：

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  4. public class BiThrTree<E>{
  6.     private static final boolean LINK = false;  //指针
  7.     private static final boolean THREAD = true;  //线索
  9.     private class Node{
  10.         public E e;
  11.         public Node left,right;
  12.         public boolean ltag;    //false表示left指向左孩子   true表示left指向前驱
  13.         public boolean rtag;    //false表示right指向右孩子  true表示right指向后继
  15.         public Node(E e, Node left, Node right, boolean ltag, boolean rtag) {
  16.             this.e = e;
  17.             this.left = left;
  18.             this.right = right;
  19.             this.ltag = ltag;
  20.             this.rtag = rtag;
  21.         }
  23.         public Node(E e) {
  24.             this(e,null,null,LINK,LINK); //默认指向左右孩子
  25.         }
  26.         public Node() {
  27.             this(null,null,null,LINK,LINK); //默认指向左右孩子
  28.         }
  29.     }
  31.     private Node dummyHead;  //虚拟头结点
  32.     private Node root;   //根结点
  33.     private Node pre;    //pre指针 指向前一个结点
  35.     public BiThrTree(E[] arr){
  36.         this.dummyHead = null;
  37.         this.pre = null;
  38.         this.root = createTree(arr, 0);   // 创建二叉树，返回创建的结点作为自己的根
  39.     }
  41.     public Node createTree(E arr[],int i) {
  42.         if(i >= arr.length || arr[i] == null)
  43.             return null;
  44.         Node T = new Node(arr[i]);
  45.         T.left = createTree(arr,2*i + 1);
  46.         T.right = createTree(arr,2*i + 2);
  47.         return T;
  48.     }
  50.     /**  中序线索化二叉树 */
  51.     public void inThreading(){
  52.         initPreNode();
  53.     }
  55.     //先初始化pre结点 并开始线索化
  56.     public void initPreNode(){
  57.         dummyHead = new Node(null); //一开始是虚拟的头结点
  59.         dummyHead.ltag = LINK; //左边是连着 root
  60.         dummyHead.rtag = THREAD;  //右边当做线索
  62.         dummyHead.right = dummyHead;  //右指针指向自己
  64.         if(root == null)  //根节点为null 就自己指向自己吧 (此时就只有一个虚拟的头结点，啥也没有)
  65.             dummyHead.left = dummyHead;
  66.         else {
  67.             dummyHead.left = root;   //蓝色矩形的(1)
  69.             pre = dummyHead;  //初始化第一个pre 为dummyHead
  71.             /**此时pre结点已经初始化完毕，可以开始线索化了*/
  72.             process(root); //开始 中序线索化
  74.             /**此时差不多 已经线索化完毕了， 只需要 连成一个双向的链表 ，后续的一些小的操作*/
  75.             pre.right = dummyHead;   //蓝色矩形的 (3)
  76.             pre.rtag = THREAD;
  78.             dummyHead.right = pre; //  虚拟头结点的 right = pre  也就是蓝色矩形的(4)
  80.         }
  81.     }
  83.     //递归线索化
  84.     public void process(Node node){
  85.         if(node == null)
  86.             return;
  87.         process(node.left); //中序  先左
  88.         /**此时已经来到 这次中序的第一个结点, 开始改*/
  90.         //改自己的前驱
  91.         if(node.left == null){  // no left child
  92.             node.ltag = THREAD;
  93.             node.left = pre; // as a thread -->  左孩子指向前序
  94.         }
  95.         //同时改pre的后继  --> 指向当前node
  96.         if(pre.right == null){
  97.             pre.rtag = THREAD;
  98.             pre.right = node;
  99.         }
  100.         pre = node; // 继续下一个
  102.         process(node.right); //递归右子树
  103.     }
  105.     // 通过  线索化 来 中序遍历
  106.     public void inOrderByThread(){
  107.         Node cur = root; //从根节点开始
  109.         while(cur != dummyHead){  //转一圈
  110.             while(cur.ltag == LINK) //如果 LINK就一直往左走 (找到最左下角的开始)
  111.                 cur = cur.left;
  113.             //访问这个结点
  114.             System.out.print(cur.e + " ");
  116.             while(cur.rtag == THREAD && cur.right != dummyHead){ //说明有后继，而且不是最后一个
  117.                 cur = cur.right; //指向后继
  118.                 System.out.print(cur.e + " ");
  119.             }
  121.             cur = cur.right;
  122.         }
  123.         System.out.println();
  124.     }
  127.     public void leverOrder(){
  128.         if(root == null)
  129.             return;
  130.         Queue<Node> que = new LinkedList<>();
  131.         que.add(root);
  132.         while(!que.isEmpty()){
  133.             Node cur = que.poll();
  134.             System.out.print(cur.e + " ");
  135.             if(cur.left != null)
  136.                 que.add(cur.left);
  137.             if(cur.right != null)
  138.                 que.add(cur.right);
  139.         }
  140.         System.out.println();
  141.     }
  144.     public void inOrder(){
  145.         inOrder(root);
  146.     }
  147.     //递归中序遍历
  148.     public void inOrder(Node node ){
  149.         if(node == null)
  150.             return;
  151.         inOrder(node.left);
  152.         System.out.print(node.e + " ");
  153.         inOrder(node.right);
  154.     }
  157.     public static void main(String[] args) {
  158.         Character[] arrStr = {'-','+','/','a','*','e','f',
  159.                 null,null,'b','-',null,null,null,null, //第四层
  161.                 //最后一层
  162.                 null,null,null,null,null,null,'c','d',
  163.                 null,null,null,null, null,null,null,null,
  164.         };
  167.         BiThrTree<Character> biThrTree = new BiThrTree(arrStr);
  169.         //test
  170.         System.out.println("-------层序-------");
  171.         biThrTree.leverOrder();
  173.         System.out.println("-------递归中序-------");
  174.         biThrTree.inOrder();
  175.         System.out.println();
  177.         biThrTree.inThreading(); // 线索化
  179.         System.out.println("-------线索化中序-------");
  180.         // biThrTree.inOrder(); //注意此时不能递归中序遍历了，因为已经线索化了 更改了结构
  181.         biThrTree.inOrderByThread(); //线索中序遍历
  182.     }
  184. }

运行结果:

线索二叉树 - 图8

另外:

线索二叉树 - 图9

没有设置头结点的前，中，后续二叉线索树构造 可以看看这个博客。