python生成具有n个顶点的随机二叉树

Question

我正在调试一个算法任务，为了测试的目的，我想生成一个根为0的n个顶点的二叉树，换句话说，生成一个对序列，这样如果序列中的第I对是（a，b），那么第I个节点的左子节点是a，右子节点是b，除非a（或b）=-1，第i个节点没有左（或右）子节点。（例如，序列：（1，2），（-1，-1），（-1，-1）是一棵有根（0）和两个子（1和2）的树） 我编写了下面的python递归函数，其中listAdd是所需的对列表，listDel是尚未生成的所有顶点，n是当前正在查看的节点：

def generateTree(listAdd, listDel, n):
    if not listDel:
        return
    ifLeft = bool(randint(0,1))
    ifRight = bool(randint(0,1))
    if ifLeft:
        chosen = choice(listDel)
        listDel.remove(chosen)
        listAdd[n] = (chosen, listAdd[n][1])
        generateTree(listAdd, listDel, chosen)
    else:
        listAdd[n] = (-1, listAdd[n][1])
    if not listDel:
        return
    if ifRight:
        chosen = choice(listDel)
        listDel.remove(chosen)
        listAdd[n] = (listAdd[n][0], chosen)
        generateTree(listAdd, listDel, chosen)
    else:
        listAdd[n] = (listAdd[n][0], -1)

但是，在编写它时，我注意到这并不正确，因为如果ifLeft和ifRight都是false，那么函数可能会在一个顶点之后停止。在

所以我的问题是，生成这样一棵树的好方法是什么？我不需要它在python中，因为它只用于生成一个输入文件，我只需要一个好的算法，或者另一种表示树的方法，这样它就更容易生成，并且可以转换成所需的格式。在

Answer 1

当你在树的右端仍然有一些自由元素时，你不能得到双零，对吗？在

所以我认为你需要确定什么时候会发生这种情况，并强制重新检查。我可以想出两种方法。在

• 创建一个函数，如果你给它根，它会检查你所在的位置。

• 创建一个数组并用0、1或{}、"R"填充它。如果你有

  • ifLeft == ifRight == 0
  • len(listDel) > 0和
  • 正在检查阵列：
    • If "L" not in check_array
    • if len(check_array) == sum(check_array)

重新装东西。在

顺便说一句，您必须在函数的开头向数组中添加检查，并在末尾删除它。所以它的长度是这样的：

0,1,2,3,4,3,2,3,4,5,4,3,2,1,2,3,2,1,0

check_array = []

def generateTree(listAdd, listDel, n):
    if not listDel:
        return
    ifLeft = bool(randint(0,1))
    ifRight = bool(randint(0,1))

    if (ifLeft + ifRight == 0) and (
        "L" not in checked_array) and (
        len(listDel) > 0):
        // Force a 1, or use randint (you need a while-loop for it)
        ifLeft = 1

    if ifLeft:
        check_array.push("L")
        chosen = choice(listDel)
        listDel.remove(chosen)
        listAdd[n] = (chosen, listAdd[n][1])
        generateTree(listAdd, listDel, chosen)
        check_array = check_array[:-1]
    else:
        listAdd[n] = (-1, listAdd[n][1])
    if not listDel:
        return
    if ifRight:
        check_array.push("R")
        chosen = choice(listDel)
        listDel.remove(chosen)
        listAdd[n] = (listAdd[n][0], chosen)
        generateTree(listAdd, listDel, chosen)
        check_array = check_array[:-1]
    else:
        listAdd[n] = (listAdd[n][0], -1)

Answer 2

一种简单的迭代方法：

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]]

在树中随机插入新节点，直到达到节点总数。在

自由边用红色表示。在每个步骤中，随机选择一个自由边。在该边上放置一个节点，该节点将向树中添加两个新的自由边。在

此过程不会生成特定顺序的节点。可以先将左子对象或右子对象插入树中。一、 你可能会得到一个类似[(2, 1), (-1, -1), (-1, -1)]的序列。如果这是一个问题，可能需要重新排序节点。在

---

我认为这种方法平均来说会产生比不平衡树更平衡的树，因为老的边被更多地考虑。您可以选择不插入新节点，而只在一定概率下移除自由边。这会使树木向更深的方向发展。只需确保在完成前不要移除所有边缘：）