如何使用Python在二叉树中插入数据？

Question

我有一个数据集是从

import numpy as np            
dataset = np.random.normal(50,10,100)

记录此数据集的min和max。让[min， max]作为根节点。然后它有100个点。让[min， min d）和[max-d， max]（其中d=（max-min）/2）分别是左右子节点。继续这样做。当节点小于或等于5个点（在数据集中）时停止。如何找到每个节点的点数？

我已经用节点构造了原始树（1,2,3......从上到下，从左到右），现在我想插入每个节点的数据。我还编写了拆分每个区间的函数。它只需要一个递归算法来完成。但是如何将它们组合在一起呢？

import numpy as np
dataset = np.random.normal(50,10,100)

def split_L(l):
    d = (max(l)-min(l)) / 2
    print('max=', max(l))
    print('min=', min(l))
    print('d=', d)
    j = 0
    m = []

    for i in dataset:
        if i in l:
            j=j+1
    print('Number of points=',j)

    for k in l:
        if k < min(l)+d:
            m.append(k)

    while j > 5:
        return m

def split_R(l):
    d = (max(l)-min(l)) / 2
    print('max=', max(l))
    print('min=', min(l))
    print('d=', d)
    j = 0
    m = []

    for i in dataset:
        if i in l:
            j=j+1
    print('Number of points=',j)

    for k in l:
        if k >= max(l)-d:
            m.append(k)

    while j > 5:
        return m

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

class Tree:
    def __init__(self):
        self.list = [self.root_node()]

    def root_node(self):
        root_node = Node(1)
        return root_node


    def add_node(self, data):
        new_node = Node(data)
        self.list.append(new_node)
        if len(self.list) % 2==0:
            self.list[len(self.list) // 2].left = new_node
        else:
            self.list[len(self.list) // 2].right = new_node

    def output_tree(self):
        for i in range(len(self.list)):
            print(self.list[i].data)


if __name__ == '__main__':
    tree = Tree()
    for i in range(2,100):
        tree.add_node(i)

    tree.output_tree()

Answer 1

一些建议。

1. 您应该有一个manger类，因为数据集范围决定根节点，点的密度决定深度。当向数据集中添加新点时，树可能会完全改变
2. 如果你不想在数据集中添加新的点，你的“插入数据”只意味着构造阶段，你不需要解析树的每一层，你只需要处理叶节点并为它们的祖先定义一个属性
3. 你不必用这种方法构造原点树，你可以计算出排序数据集中每五个相邻点的最小长度，然后直接得到深度