查找树的每个节点下的叶子数
Find number of leaves under each node of a tree
我有一个用以下格式表示的树：
nodes 是树中节点的列表，按照从顶部开始的高度顺序排列。高度为 0 的节点是节点的第一个元素。高度为1的节点（从左到右读）是节点的下一个元素，依此类推。
n_children 是一个整数列表，使得 n_children[i] = num children of nodes[i]
例如给定一棵像 {1: {2, 3:{4,5,2}}} 这样的树，nodes=[1,2,3,4,5,2], n_children = [2,0,3,0,0,0].
给定一棵树，是否可以只遍历一次树，生成节点和n_children以及节点中每个节点对应的叶子数？
这样的表现是独一无二的吗？或者两个不同的树有可能具有相同的表示吗？
对于第一个问题——创建给定树的表示：
我假设 "a given tree" 是指以 node-objects 形式给出的树，每个树都保存其值和对其 children-[ 的引用列表=151=].
我提出这个算法：
- 从
node=root 开始。
- if
node.children 为空 return {values_list:[[node.value]], children_list:[[0]]}
否则：
3.1。构造两个列表。一个将被称为 values_list 并且那里的每个元素都应该有一个值列表。另一个将被称为 children_list 并且那里的每个元素都应该是一个整数列表。这两个列表中的每个元素将代表 sub-tree 中以 node 开头的级别，包括 node 本身（将在步骤 3.3 中添加）。
所以values_list[1]会变成node的children-nodes的值列表，而values_list[2]会变成grandchildren-nodes的值列表] 的 node。 values_list[1][0] 将是 node 最左边的 child-node 的值。而 values_list[0] 将是一个只有一个元素的列表，values_list[0][0]，这将是 node.
的值
3.2。对于 node 中的每个 child-node（我们通过 node.children 引用）：
3.2.1。从 (2.) 开始，child-node 设置为 node，returned 结果将被分配回（当函数 returns 时）到 child_values_list 和 child_children_list 相应地。
3.2.2。对于列表中的每个索引 i（它们的长度相同）如果 values_list[i] 中已经有一个列表 - 将 child_values_list[i] 连接到 values_list[i] 并连接 child_children_list[i]至 children_list[i]。否则分配 values_list[i]=child_values_list[i] 和 children_list[i]=child.children.list[i]（这将是一个推 - 添加到列表的末尾）。
3.3。使 node.value 成为新列表的唯一元素，并将该列表添加到 values_list 的开头。使 node.children.length 成为新列表的唯一元素，并将该列表添加到 children_list.
的开头
3.4。 return values_list 和 children_list
当上面的return与values_list和children_list为node=root时（来自步骤（1）），我们需要做的就是连接列表的元素（因为它们是列表，每个列表用于树的一个特定级别）。连接 list-elements 后，得到的 values_list_concatenated 和 children_list_concatenated 将是所需的表示形式。
在上面的算法中，我们仅通过开始步骤 (2) 并将其设置为 node 来访问一个节点，并且我们对我们访问的每个节点的每个 child 只执行一次。我们从 root-node 开始，每个节点只有一个 parent => 每个节点只访问一次。
对于每个节点关联的叶子数：（如果我没理解错的话——sub-tree一个节点中的叶子数就是它的根），我们可以添加另一个将生成并 returned: leaves_list 的列表。
在 stop-case（没有 children 到 node - 步骤（2））我们将 return leaves_list:[[1]]。在步骤 (3.2.2) 中，我们将像其他两个列表的 list-elements 一样连接 list-elements。在步骤 (3.3) 中，我们将对第一个 list-element leaves_list[0] 求和，并将该求和作为我们将添加到 leaves_list 开头的新列表中的唯一元素。 （类似于 leaves_list.add_to_eginning([leaves_list[0].sum()])）
对于第二个问题——这个表示是否唯一：
为了证明唯一性，我们实际上想要证明该函数（我们称它为 rep 代表 "representation"）在树的 space 上保持独特性。即它是一个 injection。正如您在链接的 wiki 中看到的那样，它足以表明存在一个函数（我们称它为 tre 代表 "tree"），给定一个表示返回一棵树，并且对于每棵树它认为 tre(rep(t))=t。简而言之——我们可以创建一个方法，该方法接受一个表示并从中构建一棵树，对于每棵树，如果我们制作它的表示并将该表示传递给该方法，我们将得到完全相同的树。
让我们开始吧！
实际上，您已经完成了第一项工作 - 创建该方法（函数 tre） - 顺便说一句，您解释了表示是什么。但是让我们明确一点：
- 如果列表为空 return 空树。否则继续
- 以
values[0]作为根节点，n_children[0]作为其children的数量（尚未创建children节点）。
- 启动一个list-index
i=1和一个级别索引li=1和level-elements索引lei=root.children.length和一个next-level-elements累加器nle_acc=0
- 同时
lei>0：
4.1. lei 次：
4.1.1.以values[i]作为值，n_children[i]作为children的数量创建一个节点。
4.1.2.将新节点添加为li层中最左边的child层尚未填充（从最左边向右遍历树到li层，将新节点赋值给第一个还没有赋值的引用，我们知道上一层已经完成了，所以li-1层中的每个节点都有一个children.length属性我们可以查看是否每个都填了数字children 他们应该有）
4.1.3.添加 nle_acc+=n_children[i]
4.1.4.递增 ++i
4.2. assign lei=nle_acc (level-elements 可以取累加器为 i 收集的内容)
4.3. clear nle_acc=0 (next-level-elements累加器需要从头开始累加下一轮)
现在我们需要证明，通过第一个算法，然后通过第二个算法（这里是这个）的任意树将得到与原来相同的所有结果。
因为我不想证明算法的正确性（尽管我应该），所以我们假设它们按照我的意图进行。即第一个按照您的描述编写表示，第二个生成一棵树 level-by-level、left-to-right，从表示中分配一个值和 children 的数量并填充children在进入下一个级别时根据这些数字进行引用。
所以每个节点根据表示都有正确数量的 children（这就是 children 的填充方式），并且该数字是从树中写入的（在生成表示时).值也是如此，因此它与原始树是同一棵树。
证明实际上应该更加详尽和详细 - 但我想我现在就此打住。如果有详细说明的需求，也许我会把它作为一个实际的证明。
我有一个用以下格式表示的树：
nodes 是树中节点的列表，按照从顶部开始的高度顺序排列。高度为 0 的节点是节点的第一个元素。高度为1的节点（从左到右读）是节点的下一个元素，依此类推。
n_children 是一个整数列表，使得 n_children[i] = num children of nodes[i]
例如给定一棵像 {1: {2, 3:{4,5,2}}} 这样的树，nodes=[1,2,3,4,5,2], n_children = [2,0,3,0,0,0].
给定一棵树，是否可以只遍历一次树，生成节点和n_children以及节点中每个节点对应的叶子数？
这样的表现是独一无二的吗？或者两个不同的树有可能具有相同的表示吗？
对于第一个问题——创建给定树的表示：
我假设 "a given tree" 是指以 node-objects 形式给出的树，每个树都保存其值和对其 children-[ 的引用列表=151=].
我提出这个算法：
- 从
node=root开始。 - if
node.children为空 return{values_list:[[node.value]], children_list:[[0]]} 否则：
3.1。构造两个列表。一个将被称为
values_list并且那里的每个元素都应该有一个值列表。另一个将被称为children_list并且那里的每个元素都应该是一个整数列表。这两个列表中的每个元素将代表 sub-tree 中以node开头的级别，包括node本身（将在步骤 3.3 中添加）。所以
的值values_list[1]会变成node的children-nodes的值列表，而values_list[2]会变成grandchildren-nodes的值列表] 的node。values_list[1][0]将是node最左边的 child-node 的值。而values_list[0]将是一个只有一个元素的列表，values_list[0][0]，这将是node.3.2。对于
node中的每个 child-node（我们通过 node.children 引用）：3.2.1。从 (2.) 开始，child-node 设置为
node，returned 结果将被分配回（当函数 returns 时）到child_values_list和child_children_list相应地。3.2.2。对于列表中的每个索引
i（它们的长度相同）如果values_list[i]中已经有一个列表 - 将child_values_list[i]连接到values_list[i]并连接child_children_list[i]至children_list[i]。否则分配values_list[i]=child_values_list[i]和children_list[i]=child.children.list[i]（这将是一个推 - 添加到列表的末尾）。3.3。使
的开头node.value成为新列表的唯一元素，并将该列表添加到values_list的开头。使node.children.length成为新列表的唯一元素，并将该列表添加到children_list.3.4。 return
values_list和children_list当上面的return与
values_list和children_list为node=root时（来自步骤（1）），我们需要做的就是连接列表的元素（因为它们是列表，每个列表用于树的一个特定级别）。连接 list-elements 后，得到的values_list_concatenated和children_list_concatenated将是所需的表示形式。
在上面的算法中，我们仅通过开始步骤 (2) 并将其设置为 node 来访问一个节点，并且我们对我们访问的每个节点的每个 child 只执行一次。我们从 root-node 开始，每个节点只有一个 parent => 每个节点只访问一次。
对于每个节点关联的叶子数：（如果我没理解错的话——sub-tree一个节点中的叶子数就是它的根），我们可以添加另一个将生成并 returned: leaves_list 的列表。
在 stop-case（没有 children 到 node - 步骤（2））我们将 return leaves_list:[[1]]。在步骤 (3.2.2) 中，我们将像其他两个列表的 list-elements 一样连接 list-elements。在步骤 (3.3) 中，我们将对第一个 list-element leaves_list[0] 求和，并将该求和作为我们将添加到 leaves_list 开头的新列表中的唯一元素。 （类似于 leaves_list.add_to_eginning([leaves_list[0].sum()])）
对于第二个问题——这个表示是否唯一：
为了证明唯一性，我们实际上想要证明该函数（我们称它为 rep 代表 "representation"）在树的 space 上保持独特性。即它是一个 injection。正如您在链接的 wiki 中看到的那样，它足以表明存在一个函数（我们称它为 tre 代表 "tree"），给定一个表示返回一棵树，并且对于每棵树它认为 tre(rep(t))=t。简而言之——我们可以创建一个方法，该方法接受一个表示并从中构建一棵树，对于每棵树，如果我们制作它的表示并将该表示传递给该方法，我们将得到完全相同的树。
让我们开始吧！
实际上，您已经完成了第一项工作 - 创建该方法（函数 tre） - 顺便说一句，您解释了表示是什么。但是让我们明确一点：
- 如果列表为空 return 空树。否则继续
- 以
values[0]作为根节点，n_children[0]作为其children的数量（尚未创建children节点）。 - 启动一个list-index
i=1和一个级别索引li=1和level-elements索引lei=root.children.length和一个next-level-elements累加器nle_acc=0 - 同时
lei>0： 4.1.lei次： 4.1.1.以values[i]作为值，n_children[i]作为children的数量创建一个节点。 4.1.2.将新节点添加为li层中最左边的child层尚未填充（从最左边向右遍历树到li层，将新节点赋值给第一个还没有赋值的引用，我们知道上一层已经完成了，所以li-1层中的每个节点都有一个children.length属性我们可以查看是否每个都填了数字children 他们应该有） 4.1.3.添加nle_acc+=n_children[i]4.1.4.递增++i4.2. assignlei=nle_acc(level-elements 可以取累加器为 i 收集的内容) 4.3. clearnle_acc=0(next-level-elements累加器需要从头开始累加下一轮)
现在我们需要证明，通过第一个算法，然后通过第二个算法（这里是这个）的任意树将得到与原来相同的所有结果。
因为我不想证明算法的正确性（尽管我应该），所以我们假设它们按照我的意图进行。即第一个按照您的描述编写表示，第二个生成一棵树 level-by-level、left-to-right，从表示中分配一个值和 children 的数量并填充children在进入下一个级别时根据这些数字进行引用。
所以每个节点根据表示都有正确数量的 children（这就是 children 的填充方式），并且该数字是从树中写入的（在生成表示时).值也是如此，因此它与原始树是同一棵树。
证明实际上应该更加详尽和详细 - 但我想我现在就此打住。如果有详细说明的需求，也许我会把它作为一个实际的证明。