修剪从txt文件构建的树-Java 学习之路

我有一个txt文件，其中包含一系列数字，如下所示：

（这只是解释我的问题的一个例子 . ）文件txt中的每一行有四个由空格分隔的位置 . 第一个和第三个可以假设三个值：1,2或3.其余位置只能假设两个值：1或2 .

每行代表树的路径 . 树由根节点和形成层次结构的附加节点的级别组成：第一级和第三级可以具有三个节点（1,2或3），依此类推，如前所述 .

然后，前面示例描述的树如下：

enter image description here

我会修剪树，如下图所示：

enter image description here

以红色圈出的节点必须减少到只有一个节点，因为圆圈中的每个节点只有一个叶子 .

1 回答

1
您可以通过查看表/矩阵中的每对相邻列来确定哪些节点只有一个子节点，并观察每个数字旁边显示的次数 . 假设您的数据存储在 mat 中：
```
> mat
     [,1] [,2] [,3] [,4]
[1,]    1    1    3    2
[2,]    2    2    1    1
[3,]    3    2    3    1
[4,]    2    2    2    2
[5,]    1    1    1    1
[6,]    3    2    3    2
[7,]    1    1    3    1
[8,]    2    1    1    1
```
对于前两列，我们删除所有重复项（即相同的子路径），我们查看每个数字与其邻居的出现次数，并计算有多少不同的路径：
```
> table(mat[,c(1,2)][!duplicated(mat[,c(1,2)]),1])
1 2 3 
1 2 1
```
正如你所看到的，1有一条路径，因此可以修剪，也可以修剪3.最后，2有2条路径，所以我们不会修剪它 .

下一部分很棘手，因为你只想查看子树（因为例如，1 - > 1可能出现在树的一部分中，1 - > 2可能出现在另一部分但是如果它们不出现分享一个父母，我们可能仍然想要修剪它们） . 就像是：
```
table(mat[mat[,newLevel]==newRoot,c(2,3)][!duplicated(mat[mat[,newLevel]==newRoot,c(2,3)]),1])
```
其中newLevel是您要使用的矩阵的列，newRoot是该级别中将成为子树根的节点的值 . 例如，使用值为2的树的第一级节点作为根：
```
> table(mat[mat[,1]==2,c(2,3)][!duplicated(mat[mat[,1]==2,c(2,3)]),1])
1 2 
1 2
```
正如您所看到的，对于前2个节点正下方的节点，它发现1应该被修剪而2应该不被修剪 . 然后，您将通过树迭代它（例如，您可以递归地实现它） .
回复于 2024-04-20T12:53:56+08:00

修剪从txt文件构建的树

1 回答

相关问题