networkx构建BST二叉搜索树，Python

import random

from matplotlib import pyplot as plt
import networkx as nx

LEFT = 'left'
RIGHT = 'right'

def app():
    SIZE = 10
    data = []
    for i in range(SIZE):
        data.append(i)
    random.shuffle(data)
    # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    print('data', data)

    G = nx.DiGraph()

    while len(data) > 0:
        print('-----')
        d = data.pop()
        insert(G, d)

    print(G.nodes(data=True))
    print(G.edges(data=True))

    pos = nx.spiral_layout(G)
    nx.draw(G, pos,
            node_color='red',
            node_size=300,
            font_size=10,
            font_color='green',
            with_labels=True)

    plt.show()

def get_node_by_value(G, v):
    node = None
    for n in G.nodes(data=True):
        if n[0] == v:
            node = n
            break
    return node

def get_root_node(G):
    node = None
    for n in G.nodes(data=True):
        predecessors = G.predecessors(n[0])
        if len(list(predecessors)) == 0:
            node = n
            break
    return node

def insert(G, d):
    if G.number_of_nodes() == 0:
        G.add_node(d)
        G.nodes[d][RIGHT] = None
        G.nodes[d][LEFT] = None
        return

    print('开始插入', d)
    root_node = get_root_node(G)
    print('根节点', root_node)

    while True:
        left = root_node[1][LEFT]
        right = root_node[1][RIGHT]

        if right is None:
            if d > root_node[0]:
                root_node[1][RIGHT] = d
                G.add_node(d)
                G.nodes[d][LEFT] = None
                G.nodes[d][RIGHT] = None
                G.add_edge(root_node[0], d)
                break

        if left is None:
            if d < root_node[0]:
                root_node[1][LEFT] = d
                G.add_node(d)
                G.nodes[d][LEFT] = None
                G.nodes[d][RIGHT] = None
                G.add_edge(root_node[0], d)
                break

        if d > root_node[0]:
            val = root_node[1][RIGHT]
            root_node = get_node_by_value(G, val)
        else:
            val = root_node[1][LEFT]
            root_node = get_node_by_value(G, val)

if __name__ == '__main__':
    app()

输出：

data [3, 5, 9, 2, 1, 6, 7, 0, 8, 4]
-----
-----
开始插入 8
根节点 (4, {'right': None, 'left': None})
-----
开始插入 0
根节点 (4, {'right': 8, 'left': None})
-----
开始插入 7
根节点 (4, {'right': 8, 'left': 0})
-----
开始插入 6
根节点 (4, {'right': 8, 'left': 0})
-----
开始插入 1
根节点 (4, {'right': 8, 'left': 0})
-----
开始插入 2
根节点 (4, {'right': 8, 'left': 0})
-----
开始插入 9
根节点 (4, {'right': 8, 'left': 0})
-----
开始插入 5
根节点 (4, {'right': 8, 'left': 0})
-----
开始插入 3
根节点 (4, {'right': 8, 'left': 0})
[(4, {'right': 8, 'left': 0}), (8, {'left': 7, 'right': 9}), (0, {'left': None, 'right': 1}), (7, {'left': 6, 'right': None}), (6, {'left': 5, 'right': None}), (1, {'left': None, 'right': 2}), (2, {'left': None, 'right': 3}), (9, {'left': None, 'right': None}), (5, {'left': None, 'right': None}), (3, {'left': None, 'right': None})]
[(4, 8, {}), (4, 0, {}), (8, 7, {}), (8, 9, {}), (0, 1, {}), (7, 6, {}), (6, 5, {}), (1, 2, {}), (2, 3, {})]