# encoding=utf8'''題目：輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。'''class BinaryTreeNode():  def __init__(self, value, left = None, right = None):    self.value = value    self.left = left    self.right = rightdef create_a_tree():  node_4 = BinaryTreeNode(4)  node_8 = BinaryTreeNode(8)  node_6 = BinaryTreeNode(6, node_4, node_8)  node_12 = BinaryTreeNode(12)  node_16 = BinaryTreeNode(16)  node_14 = BinaryTreeNode(14, node_12, node_16)  node_10 = BinaryTreeNode(10, node_6, node_14)  return node_10def print_a_tree(root):  if root is None:return  print_a_tree(root.left)  print root.value, ' ',  print_a_tree(root.right)def print_a_linked_list(head):  print 'linked_list:'  while head is not None:    print head.value, ' ',    head = head.right  print ''def create_linked_list(root):  '''構(gòu)造樹(shù)的雙向鏈表，返回這個(gè)雙向鏈表的最左結(jié)點(diǎn)和最右結(jié)點(diǎn)的指針'''  if root is None:    return (None, None)  # 遞歸構(gòu)造出左子樹(shù)的雙向鏈表  (l_1, r_1) = create_linked_list(root.left)  left_most = l_1 if l_1 is not None else root  (l_2, r_2) = create_linked_list(root.right)  right_most = r_2 if r_2 is not None else root  # 將整理好的左右子樹(shù)和root連接起來(lái)  root.left = r_1  if r_1 is not None:r_1.right = root  root.right = l_2  if l_2 is not None:l_2.left = root  # 由于是雙向鏈表，返回給上層最左邊的結(jié)點(diǎn)和最右邊的結(jié)點(diǎn)指針  return (left_most, right_most)if __name__ == '__main__':  tree_1 = create_a_tree()  print_a_tree(tree_1)  (left_most, right_most) = create_linked_list(tree_1)  print_a_linked_list(left_most)  pass