插入一连串数据构建BST二叉搜索树(未做平衡),binarytree,Python

x33g5p2x  于2021-12-30 转载在 Python  
字(0.8k)|赞(0)|评价(0)|浏览(166)

这里仅仅把一连串随机数据插入到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平衡二叉搜索树,因为还没有对树进行平衡。

相关文章