<p>一种简单的迭代方法:</p>
<pre><code>import random
# start with root node and no children
tree = [[-1, -1]]
free_edges = [(0, 0), (0, 1)]
n = 4 # how many nodes do you want?
while len(tree) < n:
e = random.choice(free_edges) # select a free edge
node, child = e
assert tree[node][child] == -1 # make sure we made no mistake
k = len(tree) # index of new node
tree.append([-1, -1]) # add new node
tree[node][child] = k # set new node as child of an old node
free_edges.extend([(k, 0), (k, 1)]) # new node has two free edges
free_edges.remove(e) # edge is no longer free
print(tree)
# [[1, 2], [-1, 3], [-1, -1], [-1, -1]]
</code></pre>
<p>在树中随机插入新节点,直到达到节点总数。在</p>
<p><a href="https://i.stack.imgur.com/ZwkXx.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ZwkXx.png" alt="enter image description here"/></a>
自由边用红色表示。在每个步骤中,随机选择一个自由边。在该边上放置一个节点,该节点将向树中添加两个新的自由边。在</p>
<p>此过程不会生成特定顺序的节点。可以先将左子对象或右子对象插入树中。一、 你可能会得到一个类似<code>[(2, 1), (-1, -1), (-1, -1)]</code>的序列。如果这是一个问题,可能需要重新排序节点。在</p>
<hr/>
<p>我认为这种方法平均来说会产生比不平衡树更平衡的树,因为老的边被更多地考虑。您可以选择不插入新节点,而只在一定概率下移除自由边。这会使树木向更深的方向发展。只需确保在完成前不要移除所有边缘:)</p>