題目：輸入一棵二進制查找樹，将該二進制查找樹轉換成一個排序的雙向連結清單。要求不能建立任何新的結點，隻調整指針的指向。
比如将二進制查找樹
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()