二叉搜索樹(shù)與雙向鏈表

題目：輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。

比如輸入圖 4.12 中左邊的二叉搜索樹(shù)，則輸出轉(zhuǎn)換之后的排序現(xiàn)向鏈表。

http://wiki.jikexueyuan.com/project/for-offer/images/38.png" alt="" />

結(jié)點(diǎn)定義：

public static class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

解題思路：

在二叉樹(shù)中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指向子結(jié)點(diǎn)的指針。在雙向鏈表中，每個(gè)結(jié)點(diǎn)也有兩個(gè)指針，它們分別指向前一個(gè)結(jié)點(diǎn)和后一個(gè)結(jié)點(diǎn)。由于這兩種結(jié)點(diǎn)的結(jié)構(gòu)相似，同時(shí)二叉搜索樹(shù)也是一種排序的數(shù)據(jù)結(jié)構(gòu)，因此在理論上有可能實(shí)現(xiàn)二叉搜索樹(shù)和排序的雙向鏈表的轉(zhuǎn)換。在搜索二叉樹(shù)中，左子結(jié)點(diǎn)的值總是小于父結(jié)點(diǎn)的值，右子結(jié)點(diǎn)的值總是大于父結(jié)點(diǎn)的值。因此我們?cè)谵D(zhuǎn)換成排序雙向鏈表時(shí)，原先指向左子結(jié)點(diǎn)的指針調(diào)整為鏈表中指向前一個(gè)結(jié)點(diǎn)的指針，原先指向右子結(jié)點(diǎn)的指針調(diào)整為鏈表中指向后一個(gè)結(jié)點(diǎn)指針。接下來(lái)我們考慮該如何轉(zhuǎn)換。

由于要求轉(zhuǎn)換之后的鏈表是排好序的，我們可以中序遍歷樹(shù)中的每一個(gè)結(jié)點(diǎn)， 這是因?yàn)橹行虮闅v算法的特點(diǎn)是按照從小到大的順序遍歷二叉樹(shù)的每一個(gè)結(jié)點(diǎn)。當(dāng)遍歷到根結(jié)點(diǎn)的時(shí)候，我們把樹(shù)看成三部分：值為 10 的結(jié)點(diǎn)、根結(jié)點(diǎn)值為 6 的左子樹(shù)、根結(jié)點(diǎn)值為 14 的右子樹(shù)。根據(jù)排序鏈表的定義，值為 10 的結(jié)點(diǎn)將和它的左子樹(shù)的最大一個(gè)結(jié)點(diǎn)（即值為 8 的結(jié)點(diǎn)）鏈接起來(lái)，同時(shí)它還將和右子樹(shù)最小的結(jié)點(diǎn)（即值為 12 的結(jié)點(diǎn)）鏈接起來(lái)，如圖 4.13 所示。

http://wiki.jikexueyuan.com/project/for-offer/images/39.png" alt="" />

按照中序遍歷的順序， 當(dāng)我們遍歷轉(zhuǎn)換到根結(jié)點(diǎn)（值為 10 的結(jié)點(diǎn)）時(shí)，它的左子樹(shù)已經(jīng)轉(zhuǎn)換成一個(gè)排序的鏈表了， 并且處在鏈表中的最后一個(gè)結(jié)點(diǎn)是當(dāng)前值最大的結(jié)點(diǎn)。我們把值為 8 的結(jié)點(diǎn)和根結(jié)點(diǎn)鏈接起來(lái)，此時(shí)鏈表中的最后一個(gè)結(jié)點(diǎn)就是 10 了。接著我們?nèi)サ貧v轉(zhuǎn)換右子樹(shù)， 并把根結(jié)點(diǎn)和右子樹(shù)中最小的結(jié)點(diǎn)鏈接起來(lái)。至于怎么去轉(zhuǎn)換它的左子樹(shù)和右子樹(shù)，由于遍歷和轉(zhuǎn)換過(guò)程是一樣的，我們很自然地想到可以用遞歸。

代碼實(shí)現(xiàn)：

public class Test27 {
    /**
     * 二叉樹(shù)的樹(shù)結(jié)點(diǎn)
     */
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }
    /**
     * 題目：輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。
     * 要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。
     *
     * @param root 二叉樹(shù)的根結(jié)點(diǎn)
     * @return 雙向鏈表的頭結(jié)點(diǎn)
     */
    public static BinaryTreeNode convert(BinaryTreeNode root) {
        // 用于保存處理過(guò)程中的雙向鏈表的尾結(jié)點(diǎn)
        BinaryTreeNode[] lastNode = new BinaryTreeNode[1];
        convertNode(root, lastNode);
        // 找到雙向鏈表的頭結(jié)點(diǎn)
        BinaryTreeNode head = lastNode[0];
        while (head != null && head.left != null) {
            head = head.left;
        }
        return head;
    }
    /**
     * 鏈表表轉(zhuǎn)換操作
     *
     * @param node     當(dāng)前的根結(jié)點(diǎn)
     * @param lastNode 已經(jīng)處理好的雙向鏈表的尾結(jié)點(diǎn)，使用一個(gè)長(zhǎng)度為1的數(shù)組，類似C++中的二級(jí)指針
     */
    public static void convertNode(BinaryTreeNode node, BinaryTreeNode[] lastNode) {
        // 結(jié)點(diǎn)不為空
        if (node != null) {
            // 如果有左子樹(shù)就先處理左子樹(shù)
            if (node.left != null) {
                convertNode(node.left, lastNode);
            }
            // 將當(dāng)前結(jié)點(diǎn)的前驅(qū)指向已經(jīng)處理好的雙向鏈表（由當(dāng)前結(jié)點(diǎn)的左子樹(shù)構(gòu)成）的尾結(jié)點(diǎn)
            node.left = lastNode[0];
            // 如果左子樹(shù)轉(zhuǎn)換成的雙向鏈表不為空，設(shè)置尾結(jié)點(diǎn)的后繼
            if (lastNode[0] != null) {
                lastNode[0].right = node;
            }
            // 記錄當(dāng)前結(jié)點(diǎn)為尾結(jié)點(diǎn)
            lastNode[0] = node;
            // 處理右子樹(shù)
            if (node.right != null) {
                convertNode(node.right, lastNode);
            }
        }
    }
    public static void main(String[] args) {
        test01();
        test02();
        test03();
        test04();
        test05();
    }
    private static void printList(BinaryTreeNode head) {
        while (head != null) {
            System.out.print(head.value + "->");
            head = head.right;
        }
        System.out.println("null");
    }
    private static void printTree(BinaryTreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.print(root.value + "->");
            printTree(root.right);
        }
    }
    //            10
    //         /      \
    //        6        14
    //       /\        /\
    //      4  8     12  16
    private static void test01() {
        BinaryTreeNode node10 = new BinaryTreeNode();
        node10.value = 10;
        BinaryTreeNode node6 = new BinaryTreeNode();
        node6.value = 6;
        BinaryTreeNode node14 = new BinaryTreeNode();
        node14.value = 14;
        BinaryTreeNode node4 = new BinaryTreeNode();
        node4.value = 4;
        BinaryTreeNode node8 = new BinaryTreeNode();
        node8.value = 8;
        BinaryTreeNode node12 = new BinaryTreeNode();
        node12.value = 12;
        BinaryTreeNode node16 = new BinaryTreeNode();
        node16.value = 16;
        node10.left = node6;
        node10.right = node14;
        node6.left = node4;
        node6.right = node8;
        node14.left = node12;
        node14.right = node16;
        System.out.print("Before convert: ");
        printTree(node10);
        System.out.println("null");
        BinaryTreeNode head = convert(node10);
        System.out.print("After convert : ");
        printList(head);
        System.out.println();
    }
    //               5
    //              /
    //             4
    //            /
    //           3
    //          /
    //         2
    //        /
    //       1
    private static void test02() {
        BinaryTreeNode node1 = new BinaryTreeNode();
        node1.value = 1;
        BinaryTreeNode node2 = new BinaryTreeNode();
        node2.value = 2;
        BinaryTreeNode node3 = new BinaryTreeNode();
        node3.value = 3;
        BinaryTreeNode node4 = new BinaryTreeNode();
        node4.value = 4;
        BinaryTreeNode node5 = new BinaryTreeNode();
        node5.value = 5;
        node5.left = node4;
        node4.left = node3;
        node3.left = node2;
        node2.left = node1;
        System.out.print("Before convert: ");
        printTree(node5);
        System.out.println("null");
        BinaryTreeNode head = convert(node5);
        System.out.print("After convert : ");
        printList(head);
        System.out.println();
    }
    // 1
    //  \
    //   2
    //    \
    //     3
    //      \
    //       4
    //        \
    //         5
    private static void test03() {
        BinaryTreeNode node1 = new BinaryTreeNode();
        node1.value = 1;
        BinaryTreeNode node2 = new BinaryTreeNode();
        node2.value = 2;
        BinaryTreeNode node3 = new BinaryTreeNode();
        node3.value = 3;
        BinaryTreeNode node4 = new BinaryTreeNode();
        node4.value = 4;
        BinaryTreeNode node5 = new BinaryTreeNode();
        node5.value = 5;
        node1.right = node2;
        node2.right = node3;
        node3.right = node4;
        node4.right = node5;
        System.out.print("Before convert: ");
        printTree(node1);
        System.out.println("null");
        BinaryTreeNode head = convert(node1);
        System.out.print("After convert : ");
        printList(head);
        System.out.println();
    }
    // 只有一個(gè)結(jié)點(diǎn)
    private static void test04() {
        BinaryTreeNode node1 = new BinaryTreeNode();
        node1.value = 1;
        System.out.print("Before convert: ");
        printTree(node1);
        System.out.println("null");
        BinaryTreeNode head = convert(node1);
        System.out.print("After convert : ");
        printList(head);
        System.out.println();
    }
    // 沒(méi)有結(jié)點(diǎn)
    private static void test05() {
        System.out.print("Before convert: ");
        printTree(null);
        System.out.println("null");
        BinaryTreeNode head = convert(null);
        System.out.print("After convert : ");
        printList(head);
        System.out.println();
    }
}

運(yùn)行結(jié)果：

http://wiki.jikexueyuan.com/project/for-offer/images/40.png" alt="" />