java - 给定节点号，如何随机生成二叉树？

//Definition for a binary tree node.

public class TreeNode {
    int key;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { key = x; }
}

给定TreeNode的总数，如何生成一个随机分布的二叉树（我指的是二叉树的随机形状，而不是随机密钥值）可以将treenodes的所有键值设置为1）并返回treenodeint。
这就是如何实现以下API：

public class RandomBinaryTree{
    public TreeNode binaryTreeGenerator(int n){

    }
}

ps：例如，n，我希望算法每次都可以随机生成以下一个root二叉树：

     1      1        1           1          1
    /      /        / \           \          \
   1      1        1   1           1          1
  /        \                      /            \
 1          1                    1              1

是否有生成节点数固定的二叉树的算法？

最佳答案

有偏分布，简单算法
从根开始，随机选择每个子树中的节点数，然后递归：

public class RandomBinaryTree {
    private Random random = new Random();

    public TreeNode binaryTreeGenerator(int n, int key){
        if (n == 0)
            return null;

        TreeNode root = new TreeNode(key);

        // Number of nodes in the left subtree (in [0, n-1])
        int leftN = random.nextInt(n);

        // Recursively build each subtree
        root.setLeft(binaryTreeGenerator(leftN, key));
        root.setRight(binaryTreeGenerator(n - leftN - 1, key));

        return root;
    }
}

此算法不强制结果的均匀分布，并且会非常有利于平衡树。为了简单的证明，考虑情况n = 3并计算5个可能的二叉树中每一个的发生概率（相关的组合数学见Catalan numbers）。
均匀分布，更具挑战性
关于这个问题已经有了一些研究，this可能是最简单和最快的方法之一（in O（n））其思想是生成一个随机单词，包含相等数量的左括号和右括号，然后使用保持均匀分布的转换将其映射到二叉树。
第1步：生成一个随机平衡词：

private static Random random = new Random();

// true means '(', false means ')'
private static boolean[] buildRandomBalancedWord(int n) {
    boolean[] word = new boolean[n * 2];
    List<Integer> positions = IntStream.range(0, 2 * n).boxed()
        .collect(Collectors.toList());
    for (int i = n; i > 0; i--) {
        int index = random.nextInt(n + i);
        word[positions.remove(index)] = true;
    }
    return word;
}

步骤2：生成的单词可能有k“缺陷”，这些缺陷基本上是不匹配的右括号。本文指出，有一种方法可以重新排列生成的词，使得生成的映射是从有k缺陷的词集到有0缺陷的词集（格式良好的词）的双射。程序如下：

private static void rearrange(boolean[] word, int start, int end) {
    int sum = 0;
    int defectIndex = -1;
    for (int i = start; i < end; i++) {
        sum = sum + (word[i] ? 1 : -1);
        if (defectIndex < 0 && sum < 0) {
            defectIndex = i;
        } else if (defectIndex >= 0 && sum == 0) {
            // We now have irreducible u = rtl spanning [defectIndex, i]
            int uLength = i - defectIndex + 1;
            boolean[] flipped = new boolean[uLength - 2];
            for (int j = 0; j < flipped.length; j++)
                flipped[j] = !word[defectIndex + j + 1];

            // Shift the remaining word
            if (i + 1 < end)
                System.arraycopy(word, i + 1, word, defectIndex + 1, end - (i + 1));

            // Rewrite uw as lwrt*, t* being the flipped array
            word[defectIndex] = true;
            System.arraycopy(flipped, 0, word, end - flipped.length, flipped.length);
            word[end - uLength + 1] = false;

            // Now recurse on w, worst case we go (word.length/2)-deep
            rearrange(word, defectIndex + 1, end - uLength + 1);
            break;
        }
    }
}

步骤3：有一对一的映射，从格式良好的括号单词到二叉树：每对匹配的括号是一个节点，里面的都是左子树，后面的都是右子树：

// There is probably a smarter way to do this
public static TreeNode buildTree(boolean[] word, int key) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    boolean insertRight = false;
    TreeNode root = null;
    TreeNode currentNode = null;
    for (int i = 0; i < word.length; i++) {
        if (word[i]) {
            TreeNode previousNode = currentNode;
            currentNode = new TreeNode(key);

            if (root == null) {
                root = currentNode;
            } else if (insertRight) {
                previousNode.setRight(currentNode);
                insertRight = false;
            } else {
                previousNode.setLeft(currentNode);
            }

            stack.push(currentNode);
        } else {
            currentNode = stack.pop();
            insertRight = true;
        }
    }
    return root;
}

一些实用功能：

public static boolean[] buildRandomWellFormedWord(int n) {
    boolean[] word = buildRandomBalancedWord(n);
    rearrange(word, 0, word.length);
    return word;
}

public static String toString(boolean[] word) {
    StringBuilder str = new StringBuilder();
    for (boolean b : word)
        str.append(b ? "(" : ")");
    return str.toString();
}

测试：让我们打印超过1000万次的实际分发第3版：

public static void main(String[] args) throws Exception {
    Map<String, Integer> counts = new HashMap<String, Integer>();
    int N = 10000000, n = 3;
    for (int i = 0; i < N; i++) {
        boolean[] word = buildRandomWellFormedWord(n);
        String str = toString(word);
        Integer count = counts.get(str);
        if (count == null)
            count = 0;
        counts.put(str, count + 1);
    }

    counts.entrySet().stream().forEach(e ->
        System.out.println("P[" + e.getKey() + "] = " + e.getValue().doubleValue() / N));
}

输出应该类似于：

P[()()()] = 0.200166
P[(()())] = 0.200451
P[()(())] = 0.199894
P[((()))] = 0.199006
P[(())()] = 0.200483

因此，在所有可能的树上均匀分布之后，buildTree(buildRandomWellFormedWord(n), key)将产生一个大小为n的二叉树。

关于java - 给定节点号，如何随机生成二叉树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56873764/