二叉查找树

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


class SearchTree(object):
   """
   二叉查找树
   """

   def __init__(self):
      self.root = None

   def add(self, node):
      # 如果只传入数据，那么创建Node对象
      if not isinstance(node, Node):
         node = Node(node)

      # 设置根节点
      if self.root is None:
         self.root = node
         return

      item = self.root
      while True:
         # 小于节点数据的，放到节点的左子树上
         if node.data < item.data:
            # 判断是否需要添加节点
            if not item.left:
               item.left = node
               break
            else:
               # 如果节点有左子树，则将指针移动到左子树继续判断
               item = item.left
         # 大于等于节点数据的，放到节点的右子树上
         elif node.data >= item.data:
            if not item.right:
               item.right = node
               break
            else:
               item = item.right

   def preorder(self, root):
      if root:
         print(root.data)
         self.preorder(root.left)
         self.preorder(root.right)

   def inorder(self, root):
      """
      中序遍历的话，会按大小顺序打印
      """
      if root:
         self.inorder(root.left)
         print(root.data)
         self.inorder(root.right)


if __name__ == '__main__':
   st = SearchTree()
   import random

   nums = [random.randint(0, 100) for _ in range(10)]
   print(nums)
   for num in nums:
      st.add(num)
   st.inorder(st.root)