首页 > 数据结构 > 树形结构 > 二分查找树转化为排序的循环双链表
2014
06-02

二分查找树转化为排序的循环双链表

题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。

例如对于下面的二分查找树:

ordered binary tree

small pointer 其实也就是指向左孩子,large pointer指向右孩子,转化为双链表之后 small pointer应该指向前一个元素,large pointer应该指向后一个元素。转化为排序的循环双链表则为:

circular doubly linked list

分析

二分查找树的中序遍历即为升序排列,问题就在于如何在遍历的时候更改指针的指向。一种简单的方法时,遍历二分查找树,讲遍历的结果放在一个数组中,之后再把该数组转化为双链表。如果题目要求只能使用O(1)内存,则只能在遍历的同时构建双链表,即进行指针的替换:

tree changed to list 2

我们需要用递归的方法来解决,假定每个递归调用都会返回构建好的双链表,可把问题分解为左右两个子树。

由于左右子树都已经是有序的,当前节点作为中间的一个节点,把左右子树得到的链表连接起来即可。

java代码:TreeList.java

//二叉树节点 或 双链表节点
class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

/*
 -append() -- 合并两个链表
 -treeToList() -- 递归的解决二叉树转换为双链表
 -treeInsert() -- 构建二叉树
*/
public class TreeList {

    //辅助方法,合并两个双链表
    public static Node append(Node a, Node b) {
        if (a==null) return(b);
        if (b==null) return(a);

        // 分别得到两个链表的最后一个元素
        Node aLast = a.left;
        Node bLast = b.left;

        // 将两个链表 头尾相连
        aLast.right = b;
        b.left = aLast;

        bLast.right = a;
        a.left = bLast;

        return(a);
    }

    //递归调用
    public static Node treeToList(Node root) {
        // 基本情况
        if (root==null) return(null);

        // 递归解决子树 ( 就相信他们一定会返回正确的结果 )
        Node aList = treeToList(root.left);
        Node bList = treeToList(root.right);

        // 把根节点转换为一个节点的双链表。方便后面的链表合并
        root.left = root;
        root.right = root;

        //合并之后即为升序排列,顺序为 (aList, root, bList)
        aList = append(aList, root);
        aList = append(aList, bList);

        return(aList);
    }

    //二分查找树的插入
    public static void treeInsert(Node root, int newData) {
        if (newData<=root.data) {
            if (root.left!=null) treeInsert(root.left, newData);
            else root.left = new Node(newData);
        }
        else {
            if (root.right!=null) treeInsert(root.right, newData);
            else root.right = new Node(newData);
        }
    }

    //线序遍历,打印二叉树
    public static void printTree(Node root) {
        if (root==null) return;
        printTree(root.left);
        System.out.print(Integer.toString(root.data) + " ");
        printTree(root.right);
    }

    // 打印双链表
    public static void printList(Node head) {
        Node current = head;

        while (current != null) {
            System.out.print(Integer.toString(current.data) + " ");
            current = current.right;
            if (current == head) break;
        }

        System.out.println();
    }

    // 测试
    public static void main(String[] args) {

        Node root = new Node(4);
        treeInsert(root, 2);
        treeInsert(root, 1);
        treeInsert(root, 3);
        treeInsert(root, 5);

        System.out.println("tree:");
        printTree(root);   // 1 2 3 4 5
        System.out.println();

        System.out.println("list:");
        Node head = treeToList(root);
        printList(head);   // 1 2 3 4 5   yay!
    }
}

参考:http://cslibrary.stanford.edu/109/TreeListRecursion.html