高效生成具有 N 个叶节点和深度 D 的随机非对称二叉树

Question

我正在开发一个项目，需要生成随机二叉树。该树应该有 N 个叶子节点，并且在某个指定的深度 D 内。但是，我正在努力寻找一种有效的方法来生成既不对称又分布良好的随机二叉树，同时确保它恰好有 N 个叶子。

我当前的方法涉及在一定范围内重复生成随机树，直到找到具有正确数量的叶节点的树。然而，这种方法似乎效率低下且缓慢。

任何人都可以提出更有效的算法或方法来实现这一目标吗？如果有任何见解或代码示例可以帮助我有效地生成这样一棵树，我将不胜感激。

Answer 1

您可以采取这种方法：

1. 定义一个带有附加

   depth

   字段的 Node 类，以便简化以下算法。

2. 创建根节点，并将其放入集合中

3. 从集合中选择一个随机节点，并将其从集合中删除。该节点将成为新节点的父节点。如果该父节点当前是叶子，则随机选择新节点将成为其左子节点还是右子节点。如果该父节点已经有一个子节点，则使新节点成为该子节点的兄弟节点。新节点的深度将比其父节点的深度大 1。

4. 如果父级现在有两个子级，那么这意味着树中的叶子数量增加了 1 个。如果叶子的数量已经达到，那么从集合中删除所有不是叶子的节点（因为我们不想从现在开始添加new叶子——只通过使它们成为新叶子的父节点来替换叶子）叶）。

5. 如果父级现在只有一个子级，并且叶子数尚未达到，则将其放回集合中。

6. 如果新节点的深度是所需的树高度，那么请注意这一点：这是必须实现的两个目标之一。

7. 如果新节点的深度小于所需的树高度，则将其添加到集合中。

8. 重复步骤 3，直到实现两个目标。

这不会在可能的树之间产生完美的分布，但它可能足以满足您的需要。

这是上述想法在交互式 JavaScript 片段中的实现。您可以调整参数（叶子数量和树高），算法将生成具有这些约束的树：

class Node {
    constructor(depth) {
        this.depth = depth; // ...to ease algorithm
        this.children = [null, null]; // left and right
    }
}

const isLeaf = node => !node.children[0] && !node.children[1];

// Utility to extract a chosen element from an array
function extract(arr, i) {
    const value = arr[i];
    arr[i] = arr.at(-1); // Swap last to this index
    arr.pop(); // Reduce array length
    return value;
}

const randInt = (n) => Math.floor(Math.random() * n);

// Main algorithm
function createTree(numLeaves, height) {
    if (numLeaves > 2**height || numLeaves < 0 || height < -1) {
        throw Error(`There's no binary tree with height ${height} and ${numLeaves} leaves`);
    }
    if (numLeaves == 0) return null; // Empty tree
    let choices = [];
    let hasHeight = !height;
    const root = new Node(0);
    choices.push(root);
    numLeaves--;
    while (numLeaves > 0 || !hasHeight) {
        const parent = extract(choices, randInt(choices.length));
        let childIndex = randInt(2);
        if (parent.children[childIndex]) childIndex = 1 - childIndex;
        const node = parent.children[childIndex] = new Node(parent.depth + 1);
        if (parent.children[1 - childIndex]) { // Has two children?
            numLeaves--;
            if (!numLeaves) {
                // Don't allow the creation of more leaves
                choices = choices.filter(isLeaf);
            }
        } else if (numLeaves > 0) { // Has one child and we need more leaves?
            choices.push(parent);
        }
        hasHeight ||= node.depth == height;
        if (node.depth < height) {
            choices.push(node);
        }
    }
    return root;
}

// Utility for rendering the tree in a readable format
function treeString(root, trace="") {
    if (!root) return "";
    let tab = " ".repeat(root.depth.toString().length);
    return treeString(root.children[1], trace.replaceAll("┌", " ").replaceAll("└", "│") 
                                        + tab + "┌")
         + trace + root.depth + " ┐┘┤"[2*!!root.children[1] + !!root.children[0]] + "\n"
         + treeString(root.children[0], trace.replaceAll("┌", "│").replaceAll("└", " ")
                                        + tab + "└");
}

function rotateString(s) {  // Used to get the root at the top
    const lines = s.split("\n");
    const result = [];
    const len = Math.max(...lines.map(({length}) => length));
    for (const line of lines) {
        Array.from(line.padEnd(len), (ch, i) => (result[i] ??= []).push(ch))
    }
    return result.map(row => row.join("")).join("\n")
            .replace(/[│┌└┤┘┐]/g, c => "─┌┐┴┘└"["│┌└┤┘┐".indexOf(c)]);
}

// I/O handling
const [inpLeaveCount, inpHeight, btnGo, output] = document.querySelectorAll("input, button, pre");

function refresh() {
    const numLeaves = +inpLeaveCount.value;
    const height = +inpHeight.value;
    try {
        const root = createTree(numLeaves, height);
        output.textContent = rotateString(treeString(root));
    } catch(e) {
        output.textContent = e.message;
    }
}

(document.oninput = btnGo.onclick = refresh)();

input { width: 3em }

Number of leaves: <input type="number" value="10" min="1">
Height of tree: <input type="number" value="5" min="0"> 
<button>Generate</button><br>
<pre></pre>