遇到一道有趣的问题：把二叉搜索树转换成排序的双向链表。分享下思路，感受转换过程的优雅。先前写过二叉树的遍历和二叉树迭代器和二叉搜索树的原理、实现和应用。通过这两篇文章马上可以得到思路。

思路：建立二叉搜索树，为其添加中序遍历迭代器，迭代二叉树，树结点以键有序输出，把结点的left指针看做是链表结点prev指针，类似地，结点right指针看做是链表结点next指针，依次修改prev，next指针的指向使其建立双向链表即可。

首先是二叉树的中序遍历的非递归形式，这里写成生成器形式，

1
2
3
4
5
6
7
8
9
10
11
12
def traversal(root):
    # 中序遍历的非递归形式
    stack = []
    cur = root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        # 直接yield当前node
        yield cur
        cur = cur.right

通过代码来阐述具体思路。

1
2
3
4
5
6
7
8
9
10
def tree_to_sorted_list(root):
    node_iter = root.inorder_traverse()
    p_node = next(node_iter)
    head = p_node
    for node in node_iter:
        p_node.right = node
        p_node.left = None
        node.left = p_node
        p_node = node
    return head

我们写一个简单的测试。打乱一序列插入BST中，然后调用tree_to_sorted_list函数转换为排序双向链表，检查链表的有序性。

1
2
3
4
5
6
7
8
9
10
11
12
13
def test():
    import random
    
    nums = list(range(1, 11))
    t = Dict()
    random.shuffle(nums)
    for v in nums:
        t.insert(v, v)

    head = tree_to_sorted_list(t)
    while head:
        print(head)
        head = head.right

二叉树的访问迭代器和BST树的实现参考本文开头提及的文章。Dict是使用BST实现的字典。

最后提一个问题，如果要求排序的双向链表是逆序，那么怎么处理呢？

有两种思路：

（1）对BST实现镜像化，中序遍历时输出的时倒序的结点
（2）由于双向链表时对称的，以最大值结点（也就是BST树最大结点）作为head结点输出

第一种思路的实现方式如下：

1
2
3
4
5
6
7
8
9
10
11
def mirror_tree(root):
    if root is None:
        return
    if root.left is None and root.right is None:
        return
    root.left, root.right = root.right, root.left
    if root.left:
        mirror_tree(root.left)
    if root.right:
        mirror_tree(root.right)
    return root

第二种思路就是修改输出点，此处省略。

完。