線索二叉樹

1. 基本概念

在鏈式存儲中，發現二叉鏈表中存在大量的空指針，如果利用這些空指針指向其直接前驅或後繼的指針，則可以更方便地運用某些二叉樹操作算法。二叉樹的線索化，是為了加快查找結點前驅和後繼的速度。

在有N個結點的二叉樹中，存在N+1個空指針。每個葉結點有2個空指針，度為1的結點有1個空指針，總的空指針為2N₀+N₁，又有N₀=N₂+1，所以總的空指針為N₀+N₁+N₂+1=N+1。

二叉樹線索化規則：若無左子樹，令lchild指向其前驅結點；若無右子樹，令rchild指向其後繼結點。如圖，增加兩個標志域，用來表明當前指針指向左右結點還是前驅後繼結點。

其中標志位含義為：

線索二叉樹的結點：

private class Node{
    int data;
    Node lchild, rchild;
    int ltag = 0, rtag = 0;
}

以這種結點構成的二叉鏈表作為二叉樹的存儲結構，叫做線索鏈表，其中指向前驅和後繼的指針，叫做線索，加上線索的二叉樹叫做線索二叉樹，對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。

2. 二叉樹的構造及線索化

構造：直接使用完全二叉樹序列遞歸創建二叉樹，不存在的使用0，這裡不再贅述。直接給出代碼。

public class ThreadTree {
    
    private Integer[] nodes; // 存儲完全二叉樹序列
    private int n; // 樹結點數
    Node root; // 根結點
    Node pre; // 前一個訪問的結點
    private class Node{
        int data;
        Node lchild, rchild;
        int ltag = 0, rtag = 0;
    }
    
    public ThreadTree(){
        System.out.println("輸入一個完全二叉樹序列，不存在的結點用0代替，使用逗號隔開：");
//        String[] ins = StdIn.readString().split(",");
        String[] ins  = "1,2,3,0,4,0,5".split(",");
        nodes = new Integer[ins.length];
        for (int i = 0; i < ins.length; i++) {
            nodes[i] = Integer.valueOf(ins[i]);
        }
        n = ins.length;
        root = build(1);
        TreeUtil.print(depth(root), n, nodes);
    }
    
    /**
     * 遞歸創建一棵二叉樹
     * <p>
     * 使用完全二叉樹序列
     */
    public Node build(int index){
        if(index > n) {
            return null;
        }
        if(nodes[index-1]==0){
            return null;
        }
        Node node = new Node();
        node.data = nodes[index-1];
        node.lchild = build(2 * index);
        node.rchild = build(2 * index + 1);
        return node;
    }
}

線索化一個二叉樹其實就是遍歷一次二叉樹，遍歷過程中，檢查當前結點左右指針是否為空，若為空，將它們改為指向前驅或後繼結點。

以中序遍歷為例，那麼結點的前驅和後繼的結點就是二叉樹中序遍歷序列中的前後結點。

算法描述：node指向當前結點，pre指向前一個訪問的結點

（1）若node的左孩子為空，則修改左指針指向pre，置ltag為1

（2）若pre不為空，且不存在右孩子，則修改右指針指向node，置rtag為1

（3）使pre指向剛剛訪問過的結點node，即pre = node

public void inThreaded(){
    inThreaded(root);
    pre.rchild = null; // 單獨處理下最後一個結點
    pre.rtag = 1;
}
/**
 * 中序線索化一個二叉樹
 */
public void inThreaded(Node node){
    if (node != null) {
        inThreaded(node.lchild); // 線索化左子樹，找到左側一個沒有左孩子的結點
        if(node.lchild == null){ // 左孩子為空
            node.lchild = pre; // 修改指向其前驅結點
            node.ltag = 1; // 修改標志位
        }
        if(pre != null && pre.rchild == null){ // 如果前一個訪問的結點不為空，且沒有右孩子
            pre.rchild = node; // 修改指向其後繼結點
            pre.rtag = 1; // 修改標志位
        }
        pre = node;
        inThreaded(node.rchild); // 線索化右子樹
    }
}

3. 線索化的遍歷

中序線索化二叉樹主要目的就是加快訪問前驅和後繼的速度，這種遍歷就不需要借助棧，因為結點中隱含了前驅和後繼結點的信息。不含頭結點的線索二叉樹遍歷算法如下：

（1）首先找到中序線索二叉樹中的第一個結點，左側沒有左孩子的結點，不一定是葉結點，根據ltag標志為判斷

（2）找結點的後繼結點，根據rtag判斷

/**
 * 中序線索二叉樹遍歷，非遞歸
 * @param node
 */
public void inOrder(Node node){
    Node tmp = firstNode(node);
    while(tmp != null){
        System.out.print(tmp.data+" ");
        tmp = nextNode(tmp);
    }
}
/**
 * 求第一個結點
 * @param node
 * @return
 */
public Node firstNode(Node node){
    while(node.ltag == 0){ // 最左下結點，不一定是葉子結點
        node = node.lchild;
    }
    return node;
}
/**
 * 求後繼結點
 * @param node
 * @return
 */
public Node nextNode(Node node){
    if(node.rtag == 0){ // 存在右孩子
        return firstNode(node.rchild); // 以此結點為根找最左下結點
    }
    return node.rchild; // rtag = 1 直接返回後繼
}
/**
 * 倒序非遞歸遍歷
 * @param node
 */
public void inOrderO(Node node){
    Node tmp = lastNode(node);
    while(tmp != null){
        System.out.print(tmp.data+" ");
        tmp = preNode(tmp);
    }
}
/**
 * 求最後一個結點
 * @return
 */
public Node lastNode(Node node){
    while(node.rtag == 0){
        node = node.rchild;
    }
    return node;
}
/**
 * 求前驅結點
 * @return
 */
public Node preNode(Node node){
    if(node.ltag == 0){
        return lastNode(node.lchild);
    }
    return node.lchild;
}

4. 測試

public static void main(String[] args) {
    ThreadTree tree = new ThreadTree();
    System.out.print("二叉樹的結點總數：" + tree.nodes(tree.root));
    System.out.print("\n中序遍歷遞歸：");
    tree.inOrderRecur(tree.root);
    tree.inThreaded();
    System.out.print("\n線索化...\n中序線索化二叉樹遍歷非遞歸：");
    tree.inOrder(tree.root);
    System.out.print("\n非遞歸遍歷（倒序）：");
    tree.inOrderO(tree.root);
}

4.1 輸出結果

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm