插入一连串数据构建BST二叉搜索树（未做平衡），binarytree，Python

矫情吗；* 2023-10-02 01:31 22阅读 0赞

这里仅仅把一连串随机数据插入到BST二叉树中：

import random
    
    import binarytree
    from binarytree import get_parent
    
    
    def app():
        data = []
        for i in range(10):
            data.append(i)
        random.shuffle(data)
    
        my_tree = None
        while len(data) > 0:
            d = data.pop()
            my_tree = insert(my_tree, binarytree.Node(d))
    
        print(my_tree)
    
    
    def insert(my_tree, node):
        if my_tree is None:
            return node
    
        root_node = my_tree
        while True:
            left = root_node.left
            right = root_node.right
    
            if left is None:
                if node.value < root_node.value:
                    root_node.left = node
                    break
    
            if right is None:
                if node.value > root_node.value:
                    root_node.right = node
                    break
    
            if node.value > root_node.value:
                root_node = right
            else:
                root_node = left
    
        return my_tree

模块放入主程序跑几轮结果输出：

__3____
       /       \
      1       __6____
     / \     /       \
    0   2   4         9
             \       /
              5     8
                   /
                  7

0______________
                   \
                ____8
               /     \
              5__     9
             /   \
          __4     7
         /       /
        2       6
       / \
      1   3

2__________
       /           \
      1       ______8
     /       /       \
    0       4         9
           / \
          3   5__
                 \
                  7
                 /
                6

__2________
     /           \
    0           __7
     \         /   \
      1     __5     8
           /   \     \
          3     6     9
           \
            4

显然生成的不是AVL平衡二叉搜索树，因为还没有对树进行平衡。