美文网首页
二叉查找树

二叉查找树

作者: MoonMonsterss | 来源:发表于2018-10-21 19:03 被阅读0次
    
    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)
    

    相关文章

      网友评论

          本文标题:二叉查找树

          本文链接:https://www.haomeiwen.com/subject/uvwbzftx.html