树生成算法

Question

我想生成一棵具有以下结构的树，它需要一个输入 'n' 来生成树。有什么算法可以用吗

                            0
            0                                 1
    0       1          2            0         1         2
 0 1 2 3  0 1 2 3   0 1 2 3      0 1 2 3   0 1 2 3   0 1 2 3
 .
 .
 .
 .
 n

Answer 1

分支相互独立，因此您可以使用包含参数 current_depth 和 n

的递归函数相当容易地做到这一点

示例代码

def tree(current_depth, n):
   if current_depth == n:
     return {i:i for i in range(n)}
   return {i:tree(current_depth + 1, n) for i in range(current_depth + 1)}


print(tree(1,1))
print(tree(1,2))
print(tree(1,3))

# Output
# {0: 0}
# {0: {0: 0, 1: 1}, 1: {0: 0, 1: 1}}
# {0: {0: {0: 0, 1: 1, 2: 2}, 1: {0: 0, 1: 1, 2: 2}, 2: {0: 0, 1: 1, 2: 2}}, 1: {0: {0: 0, 1: 1, 2: 2}, 1: {0: 0, 1: 1, 2: 2}, 2: {0: 0, 1: 1, 2: 2}}}

Answer 2

你可以使用递归。这是 JavaScript 中的一个可运行片段，它定义了一个 Node class 和一个将创建树的静态方法。当您为 n 输入一个值时，相应的树将以 JSON 格式显示：

class Node {
    constructor(value, children=[]) {
        this.value = value;
        this.children = children;
    }
    static createTree(n, level=1, value=0) {
        return new Node(value, Array.from({length: (level+1) % (n+1)}, (_, i) =>
            this.createTree(n, level+1, i)
        ));
    }
}

// I/O handling

let input = document.querySelector("input");
let output = document.querySelector("pre");

input.addEventListener("input", refresh);
refresh();

function refresh() {
    let n = +input.value;
    if (n >= 1 && n <= 8) {
        let tree = Node.createTree(n);
        output.textContent = JSON.stringify(tree, null, 4);
    } else {
        output.textContent = "Please enter a value between 1 and 8";
    }
}

n: <input type="number" value="3" min="1" max="8" size="4"><br>
<pre></pre>

该代码段不接受大于 8 的值，因为树的大小呈指数增长。

Answer 3

另一种递归方法：

function to_tree(n, w = 1){
   var d = {}
   for (var i = 0; i < w; i++){
      d[i] = n > 0 ? to_tree(n-1, w+1) : null;
   }
   return d
}
console.log(to_tree(3))

树生成算法

Tree Generation Algorithm

javascript

algorithm

tree

data-structures