从数据列表构建树

Question

假设我有如下数字列表，

a = [1,23,5,72,3,5,15,7,78,1,5,77,23]

现在我需要根据这些数据构建一棵树。

Divide the dataset into two parts according to the self-defined function par. Let's call these two parts a0, a1.

Apply the function par on a0, a1 respectively, and get a00, a01, a11, a12.

Repeat the process until there is only one number left at the end node.

For each end node, we have a "binary code" like "0010100", where 0 represents left, and 1 represents right at each specific step.

我试图像下面那样使用树class，但我被困在了第一个地方。

class Node(input):
    def __init__(self, data):
        self.data = data
        self.left = '*'
        self.right = '*'

Answer 1

class Node(input):
    def __init__(self, data, path='0'):
        self.path = path # 0 means left, 1 means right
        if len(data) = 1:
            self.value = data[0] # this assumes the leaf is a list with single data, rather than the data itself
        else:
            left, right = par(data)
            left = Node(left, side+'0')
            right = Node(right, side+'1')

Node.path 给你二进制代码。

Answer 2

尚不清楚内部节点会有哪些值。这可能并不重要，但您可以始终分配属于该特定子树的数据数组中的 first 值。

“二进制代码”就像是从根到节点的导航路径。因此，对于您提供的数据，我们期望像这样的树：

value:                                   1
path:                       ____________ "" ________ 
                           /                        \
value:                    1                         15
path:                  __ 0 __                 _____ 1 _______
                      /       \               /               \
value:              1         72             15                1
path:               00        01             10             __ 11 __
                   /  \      /  \           /  \           /        \
value:            1   23    72   3         15   7         1          77
path:            000  001   010  011      100  101       110         111
                     /  \       /  \          /  \       /  \       /   \
value:              23   5     3    5        7    78    1    5     77   23
path:              0010 0011  0110 0111    1010  1011  1100 1101  1110 1111

你可以使用一个简单的Node class，它既可以存储值也可以存储路径：

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

par 函数会做这样的事情：

def par(data):
    i = len(data) // 2
    return (data[:i], data[i:]) if i else ()

当只有一个数据元素时，if..else 运算符用于 return 一个空列表。这在主函数中很有用：

def maketree(data, path=""):
    return Node(data[0], path, *(
        maketree(part, path + str(i)) for i, part in enumerate(par(data))
    ))

这枚举了 return 由 par 编辑的部分，并将这些部分传递给递归调用（如果有任何部分被 return 编辑）。同时，递归调用得到一个用 0 或 1 扩展的路径字符串（即枚举的索引）。

调用示例：

a = [1,23,5,72,3,5,15,7,78,1,5,77,23]
root = maketree(a)

# Output the properties of one particular node:
node = root.left.left.right.left
print("value: {}, path: {}".format(node.value, node.path))
# Outputs: "value: 23, path: 0010"

从数据列表构建树

Construct a tree from a list of data

python

python-3.x

tree

hierarchical-clustering