#二叉排序樹
class BTree():
? ? def __init__(self,data):
? ? ? ? self.left = None
? ? ? ? self.right = None
? ? ? ? if type(data) == list:
? ? ? ? ? ? self.data = data[0]
? ? ? ? ? ? for d in data[1:]:
? ? ? ? ? ? ? ? self.insert(d)
? ? ? ? else:
? ? ? ? ? ? self.data = data
? ? def insert(self,data):
? ? ? ? bt = self
? ? ? ? while True:
? ? ? ? ? ? if data <= bt.data:
? ? ? ? ? ? ? ? if bt.left == None:
? ? ? ? ? ? ? ? ? ? bt.left = BTree(data)
? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? bt = bt.left
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? if bt.right == None:
? ? ? ? ? ? ? ? ? ? bt.right = BTree(data)
? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? bt = bt.right
? ? def mid_order(self):
? ? ? ? res = []
? ? ? ? stack = []
? ? ? ? node = self?
? ? ? ? while node or stack:
? ? ? ? ? ? while node:
? ? ? ? ? ? ? ? stack.append(node)?
? ? ? ? ? ? ? ? node = node.left
? ? ? ? ? ? node = stack.pop()
? ? ? ? ? ? res.append(node.data)
? ? ? ? ? ? node = node.right
? ? ? ? return res

data = [5,1,2,3,6,8,9]
bt = BTree(data)
print(bt.mid_order())

class TreeNode(object):
? ? def __init__(self,data):
? ? ? ? self.data = data
? ? ? ? self.left = None
? ? ? ? self.right = None

class BinaryTree(object):
? ? def insert(self,root, node):
? ? ? ? if root is None:
? ? ? ? ? ? return node
? ? ? ? if node.data < root.data:
? ? ? ? ? ? root.left = self.insert(root.left, node)
? ? ? ? else:
? ? ? ? ? ? root.right = self.insert(root.right, node)
? ? ? ? return root
? ? def mid_order(self,root):
? ? ? ? node = root
? ? ? ? stack = []
? ? ? ? res = []
? ? ? ? while node or stack:
? ? ? ? ? ? while node:
? ? ? ? ? ? ? ? stack.append(node)
? ? ? ? ? ? ? ? node = node.left
? ? ? ? ? ? node = stack.pop()
? ? ? ? ? ? res.append(node.data)
? ? ? ? ? ? node = node.right
? ? ? ? return res
? ??
data = [5,1,2,3,6,8,9]
root = TreeNode(data[0])
tree = BinaryTree()
for i in data[1:]:
? ? tree.insert(root,TreeNode(i))
print(tree.mid_order(root))