数据结构与算法--线索二叉树及其前序、中序遍历

二叉树如果某个结点没有左孩子或右孩子，则这个域就为空。如node.lChild = null，

而叶子结点两个指针域都是null。我们知道n个结点的二叉树共有2n个指针域，树只有n-1条分支，也就是说还有2n - (n -1) = n + 1个域是空指针。为了充分利用这些空指针，可以存一些有用的信息——比如某结点的前驱和后继结点（按某种次序遍历后的顺序）。这种指向前序后继的指针称为线索，具有前驱后继关系的二叉树叫线索二叉树。线索二叉树的好处是：不仅节约了空间，而且一旦按照某种次序（中序、前序或后序）遍历一次后，线索信息就已经初始化好，下次想要获取某个结点的前驱后继就不用再遍历整棵树了。

具体来说，对于所有空指针域，lChild指向该结点的前驱结点；rChild指向该结点的后继结点。但是lChild和rChild同时也表示某结点的左孩子和右孩子，一个指针有两种意思，对某个结点究竟指代的哪种意思？显然需要一个标志加以区分，我们给每个结点的孩子加上标志，如果是false则表示左/右孩子，如果是true则表示前驱/后继。这棵二叉树中序遍历的结果是HDIBEAFCG，按照遍历所得顺序，H的后继就是D，h.rChild本来是null，现在让其指向D，由于这表示后继，所以相应的标志位应该设置为true。这幅图将所有rChild为空的指针域都指向了其后继。

那么前驱呢？自然是将所有lChild为空的指针域指向该结点的前驱。如下图。

如果将这两幅图结合起来，则每个空指针域都已用上了。这棵二叉树就成了下面这个样子

虚线表示右孩子或者后继，实线表示左孩子或者前驱，具体怎么区分也就是看给结点左右孩子设置的标志位了。仔细观察，把这颗树两头拉直，就成了双向链表！（但又和普通的双向链表不同，这里前驱后继的含义指代比较模糊）

现在来试着实现一下。

package Chap6;

public class ThreadTree<Item> {
    public static class Node<T> {
        private T data;
        private Node<T> lchild;
        private Node<T> rchild;
        private boolean isleftThead;
        private boolean isRightThead;

        public Node(T data) {
            this.data = data;
            isleftThead = false;
            isRightThead = false;
        }

        public T getData() {
            return data;
        }

        public Node<T> getLchild() {
            return lchild;
        }

        public Node<T> getRchild() {
            return rchild;
        }

        @Override
        public String toString() {
            String lchildInfo = lchild == null ? null : lchild.getData().toString();
            String rchildInfo = rchild == null ? null : rchild.getData().toString();

            return "Node{" +
                    "data=" + data +
                    ", lchild=" + lchildInfo +
                    ", rchild=" + rchildInfo +
                    '}';
        }
    }

    private Node<Item> root;
    private Node<Item> preNode;
    private int nodesNum;

    public void setRoot(Item data) {
        root = new Node<>(data);
        nodesNum++;
    }

    public void addLeftChild(Item data, Node<Item> parent) {
        parent.lchild = new Node<>(data);
        nodesNum++;
    }

    public void addRightChild(Item data, Node<Item> parent) {
        parent.rchild = new Node<>(data);
        nodesNum++;
    }

    public Node<Item> root() {
        return root;
    }

    /**
     * 中序遍历线索化二叉树
     */
    public void inOrderThread(Node<Item> node) {
        if (node == null) {
            return;
        }
        inOrderThread(node.lchild);

        if (node.lchild == null) {
            node.lchild = preNode;
            node.isleftThead = true;
        }

        if (preNode != null && preNode.rchild == null) {
            preNode.rchild = node;
            preNode.isRightThead = true;
        }
        // preNode始终表示上一个访问的结点
        preNode = node;
        inOrderThread(node.rchild);
    }

    public void inOrderThread() {
        inOrderThread(root);
    }

    public void inOrderTraversal(Node<Item> node) {
        // 不断深入左子树,只要某个结点左孩子为空，则标志位肯定为true
        while (node != null) {
            while (!node.isleftThead) {
                node = node.lchild;
            }

            System.out.print(node.getData() + " ");
            while (node.isRightThead && node.rchild != null) {
                node = node.rchild;
                System.out.print(node.getData() + " ");
            }
            node = node.rchild;
        }
    }

    public void inOrderTraversal() {
        inOrderTraversal(root);
    }

    /**
     * 前序遍历线索化二叉树
     */
    public void preOrderThread(Node<Item> node) {
        if (node == null) {
            return;
        }

        if (node.lchild == null) {
            node.lchild = preNode;
            node.isleftThead = true;
        }

        if (preNode != null && preNode.rchild == null) {
            preNode.rchild = node;
            preNode.isRightThead = true;
        }
        // preNode始终表示上一个访问的结点
        preNode = node;
        // 这里需要判断，因为node.lchild和node.rchild可能已经被设置了标志。若还递归就会打乱了已设置好的标志位，而且还会StackOverflow
        // 而中序遍历递归是，标志位均未被设置，所以无需判断
        if (!node.isleftThead) {
            preOrderThread(node.lchild);
        }
        if (!node.isRightThead) {
            preOrderThread(node.rchild);
        }
    }

    public void preOrderThread() {
        preOrderThread(root);
    }

    public void preOrderTraversal(Node<Item> node) {
        while (node != null) {
            while (!node.isleftThead) {
                System.out.print(node.getData() + " ");
                node = node.lchild;
            }

            System.out.print(node.getData() + " ");
            node = node.rchild;
        }
    }

    public void preOrderTraversal() {
        preOrderTraversal(root);
    }

    public static void main(String[] args) {
        ThreadTree<String> tree = new ThreadTree<>();
        tree.setRoot("A");
        Node<String> root = tree.root();
        tree.addLeftChild("B", root);
        tree.addRightChild("C", root);
        tree.addLeftChild("D", root.getLchild());

        tree.addLeftChild("E", root.getRchild());
        tree.addRightChild("F", root.getRchild());
        tree.addLeftChild("G", root.getLchild().getLchild());
        tree.addRightChild("H", root.getLchild().getLchild());
        tree.addRightChild("I", root.getRchild().getLchild());

        System.out.println("中序线索化并遍历");
        tree.inOrderThread();
        tree.inOrderTraversal();

        // 线索化只能调用一次！！！一旦设置好，就不要去打乱了。所以想运行上面的需要注释掉下面的
//        System.out.println("前序线索化并遍历");
//        tree.preOrderThread();
//        tree.preOrderTraversal();
    }
}

首先是Node类增加了标志位isleftThead和isRightThread，含义上面解释过了。然后是ThreadTree类除了有个root成员，还新增了preNode成员，专门表示在线索化中上一个刚访问过的结点。部分方法直接使用了普通二叉树的代码。这里着重说一下线索化的代码。前序和后序线索化及遍历都比较简单，后序复杂一点我也懒得去实现了。

中序线索化及中序遍历

之所以称为中序线索化，是因为它和普通二叉树中序遍历的递归实现，代码结构几乎一样。看单独抽取出来的中序线索化实现，只要把中序遍历递归实现中的打印操作换成注释了begin和end之间的代码就OK了。

public void inOrderThread(Node<Item> node) {
    if (node == null) {
        return;
    }
    inOrderThread(node.lchild);
    // begin
    if (node.lchild == null) {
      node.lchild = preNode;
      node.isleftThead = true;
    }

    if (preNode != null && preNode.rchild == null) {
        preNode.rchild = node;
        preNode.isRightThead = true;
    }
    // preNode始终表示上一个访问的结点
    preNode = node;
    // end
    inOrderThread(node.rchild);
}

中间的代码做的事主要是：

• 某结点的左孩子为空，设置标志位为true，且让上一个结点成为当前结点的前驱。
• 某结点的右孩子为空，设置标志位为true，且让当前结点成为前一个结点的后继。这里因为要调用preNode的方法，所以要进行判空操作。
• 当前结点访问完，即将访问下一个结点了，于是当前结点也就成了上一个结点preNode。

这里设置某结点的后继之所以使用preNode，理由很简单，当前结点的后继还没访问到呢，只能用已经访问过的前一个结点，它的后继可能是当前结点。

再来看中序遍历。

public void inOrderTraversal(Node<Item> node) {
    // 不断深入左子树,直到遇见第一个线索
    while (node != null) {
        while (!node.isleftThead) {
            node = node.lchild;
        }

      System.out.print(node.getData() + " ");
      while (node.isRightThead && node.rchild != null) {
          node = node.rchild;
          System.out.print(node.getData() + " ");
      }
      node = node.rchild;
    }
}

先是从根结点开始按照左子树深入，直到遇见第一个左孩子是线索的结点，紧接着就打印它，这次打印的其实是链表头。接下来看它的右孩子是不是后继，如果是就继续打印；直到右孩子不是线索，此时转到右子树，开始和根结点一样的循环...最后一个while中需要判断node.rchild不为空，如果为空，我们打印出来就是null，这不是我们想要看得结果。

前序线索化

把设置标志那一团代码放到递归左右子树之前，就成了前序线索化。特别注意，在递归前判断了是否为线索结点。因为前序线索化中，递归发生在设置标志位之后，所以node.lchild和node.rchild可能已经被设置了标志。若还递归就会打乱了已设置好的标志位，而且还会发生StackOverflow。而中序线索化中无需判断是因为，递归左子树发生在设置左孩子的线索之前，而右孩子的线索的设置是针对上一个结点的，当前结点的右孩子并没有线索化，所以对当前结点的右子树node.rchild的递归并没有影响。

if (!node.isleftThead) {
    preOrderThread(node.lchild);
}
if (!node.isRightThead) {
    preOrderThread(node.rchild);
}

接着看前序遍历的。还是根结点开始，深入左子树，只要没遇到左孩子是线索的结点，就立即打印。然后跳出while循环打印第一个左孩子是线索的结点。然后转向其后继或者是右子树，继续大循坏...

如果我们经常需要遍历二叉树，并且要知道某结点的前驱后继信息，那么使用线索二叉树是个不错的选择。特别注意一点，线索化只能执行一次，已经设置好的标志信息就不要再设置第二次了（除非清空标志位），否则会导致标志位的混乱，导致遍历失败。

---

by @sunhaiyu

2017.9.14