題目：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只調整指針的指向。
比如將二元查找樹
10
/ /
6 14
/ / / /
4 8 12 16
轉換成雙向鏈表
4=6=8=10=12=14=16。
一道微軟的面試題。
二叉查找樹的每個節點都有兩個指針，雙向鏈表的節點也是兩個指針，不創建新節點只調整指針是可以完成轉變的。
對于二叉查找樹的每個節點Node，它的左子樹中所有的關鍵字都小于Node的關鍵字，而右子樹中的所有關鍵字都大于Node的關鍵字。
采用遞歸的思維可以很方便的完成轉變，將節點的左右子樹分別轉變成有序鏈表，然后將節點的指針分別指向這兩個鏈表。
import randomclass Node(object): def __init__(self,key): self.key=key self.left=None self.right=Noneclass 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 randomclass Node(object): def __init__(self,key): self.key=key self.left=None self.right=Noneclass Sorted_LinkedList(object): def __init__(self): self.head=None def travel(self): node=self.head while node: print node.key node=node.rightclass 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()
新聞熱點
疑難解答
