二叉查找树转变为有序双向链表

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

比如将二元查找树
10
/    \
6       14
/  \     /　 \
4     8  12   16
转换成双向链表

4=6=8=10=12=14=16。

一道微软的面试题。

二叉查找树的每个节点都有两个指针，双向链表的节点也是两个指针，不创建新节点只调整指针是可以完成转变的。

对于二叉查找树的每个节点Node，它的左子树中所有的关键字都小于Node的关键字，而右子树中的所有关键字都大于Node的关键字。

采用递归的思维可以很方便的完成转变，将节点的左右子树分别转变成有序链表，然后将节点的指针分别指向这两个链表。

import random
class Node(object):
    def __init__(self,key):
        self.key=key
        self.left=None
        self.right=None
class BSTree(object):
    def __init__(self):
        self.root=None
    def put(self,key):
        if not self.root:
            self.root=Node(key)
        else:
            self.root=self._put(self.root,key)
    def _put(self,node,key):
        if node is None:
            node=Node(key)
        elif key<node.key:
            node.left=self._put(node.left,key)
        elif key>node.key:
            node.right=self._put(node.right,key)
        return node 
    def convert(self):
        if self.root:
            return self._convert(self.root)
    def _convert(self,node,asright=True):
        if not node:
            return None
        else:
            left=self._convert(node.left,False)
            if left:
                left.right=node
                node.left=left
            right=self._convert(node.right)
            if right:
                right.left=node
                node.right=right
            cur=node
            if asright:
                while cur.left:
                    cur=cur.left
            if not asright:
                while cur.right:
                    cur=cur.right
            return cur
                 
             
if __name__=='__main__':
    t=BSTree()  
    for i in range(10):
        t.put(random.randint(0,100))   
    cur=t.convert()
    if cur:
        print cur.key
        while cur.right:
            cur=cur.right
            print cur.key
        while cur.left:
            cur=cur.left
            print cur.key

另一种思路是采用中序遍历的方法。二叉查找树中序遍历的话就是从小到大排列。将遍历过的节点转为有序链表，然后将下一个要遍历的节点加到链表结尾。

import random
class Node(object):
    def __init__(self,key):
        self.key=key
        self.left=None
        self.right=None
class Sorted_LinkedList(object):
    def __init__(self):
        self.head=None
    def travel(self):
        node=self.head
        while node:
            print node.key
            node=node.right
class BSTree(object):
    def __init__(self):
        self.root=None
        self.list=Sorted_LinkedList()
        self.curNode=None
    def put(self,key):
        if not self.root:
            self.root=Node(key)
        else:
            self.root=self._put(self.root,key)
    def _put(self,node,key):
        if node is None:
            node=Node(key)
        elif key<node.key:
            node.left=self._put(node.left,key)
        elif key>node.key:
            node.right=self._put(node.right,key)
        return node 
    def convert(self):
        self._travel(self.root)
        return self.list
    def _travel(self,node):
        if node:
             self._travel(node.left)
             if self.curNode:
                 self.curNode.right=node
                 node.left=self.curNode
             else:
                 self.list.head=node
             self.curNode=node
             self._travel(node.right)
                         
if __name__=='__main__':
    t=BSTree()  
    for i in range(100):
        t.put(random.randint(0,100))
    l=t.convert()
    l.travel()