问题标签 [multiway-tree]

我已经实现了一种方法来对树进行前序遍历，这不是二叉树。这棵树的每个父节点都有一个子节点数组，所以这是我正在使用的方法：

将子节点链接到父节点“tnAA”的示例

但是它只输出根节点，这个方法有什么问题？

解决方案：将子数组链接到每个父数组： tnAA.setChildern(AA_childern);

我无法理解如何将元素插入 ab*-tree，尤其是在涉及根节点时。

假设您有 9 阶的 ab*-tree，并且您要将以下项目插入树中，0、1、2、5、7、9、10 和 12 我认为您开始插入根然后当你插入 12 时它会被填满，所以它会溢出，因此它会导致根被分割并有一个包含 7 的根节点，一个包含 0、1、2、5 和右的左子节点包含 9、10 和 12 的孩子。我的想法是正确的还是有其他方法可以做到这一点。

PS：请注意我使用 b-tree 作为标签，因为我不能使用 b*-tree 任何帮助将不胜感激：）

I am currently about to implement a multi-way tree in c++, but I am still not sure about what exactly they are. I have read a few documentations, but I am still confused because of the lack of pictures or visualization provided.

Lets say I want a 3 way tree, according to online web notes it means each node can have at most 3-1 = 2 elements and each node can have at most 3 children. Below I have drawn some trees that I am not sure if they are 3-way trees, can someone please verify I am understanding this correctly? Thank you!

Also, if I have a 2 way tree, does that mean I have a binary tree as well? O.o?

我在应用数学中有一个问题，几乎可以完美地映射到在多路树中找到最长的路径。

我有一个函数 child() 给出子节点（空间中的点满足条件）。唯一需要注意的是 child() 需要连接到它的所有先前节点，包括根节点。正是在这里，我正在努力递归地编写我的代码。到目前为止，我有类似下面的东西。

但在这一点上，我不确定要返回什么。我基本上想映射整个多路树，直到我找到所有东西的叶子。有什么想法或提示吗？多谢你们。

编辑：

更新 1：为了完整起见，我勾勒出输入 child() 需要什么的粗略概念：https ://i.imgur.com/3MkfsYc.png基本上是为了找到箭头 child() 标记的节点的子节点需要根节点和节点本身之间的节点列表，即用红点标记的节点。

更新 2：

我已经写了 child(node) 如下，我目前正在处理它——

我在 documentdb 中有以下 JSON 数据，我想将其解析为 F# 多路树区分联合

F# 多路可区分联合

其中 CommentMultiTreeDatabaseModel 定义为

我在 f# 中广泛引用折叠/递归多路树。我不确定从哪里开始将这样的 JSON 结构解析为 F# 多路树。任何建议将不胜感激。谢谢

是否有关于如何在 2-3-4 树中拆分节点的规则？

例如，如果我将 3、7、4、9 插入到 2-3-4 树中：

它会像这样（黄色）还是那样（绿色）被拆分，如下所示：

两者都有效吗？

我必须通过将多个列表合并在一起来构建多路树。我正在尝试找到一种有效的算法来做到这一点。

• 可以有相同的列表
• 列表元素不是唯一的。这些元素的路径是
• 树以空根元素开始

列表包含不唯一的元素。每个元素的路径是一个键，

例如，使用列表：

• ABCDE
• ABCB
• FBCC
• AEF
• ACD
• ABCDE

可以构建以下树：

我实现的第一个算法通过创建根节点并将列表一个接一个地添加到它来构建树：

1. 创建根节点
2. 选择第一个列表
3. 如果列表的第一个元素已经是根节点的子节点，则选择它。否则，将该元素作为子元素插入。
4. 如果列表的下一个元素已经是先前选择或插入的子元素，则选择它。否则，将该元素作为子元素插入。
5. 重复步骤 4 直到列表为空
6. 选择下一个数组并转到步骤 3。如果没有其他列表，则停止。

我发现用于构建或合并树的大部分资源都是指二叉树。因此，我想知道在我的情况下是否有更好的算法来构建多路树？

我有以下类型的数据表：

id parent_id child_id 级别
1 53987 52548 1
2 60764 52548 2
3 60764 53987 1
4 60764 59695 2
5 63457 59695 1
6 60764 63457 1

那么，我如何通过递归级别获取数据并将数据存储到数组中，如 ['child_id','parent_id',level]。我需要编写查询和生成树的帮助。

树应该是这样的：

注意：我无法更改数据库的表结构。我必须需要基于给定表结构的树。

我想展平一棵看起来像这样的树：

可能的例子：

应该成为

解释原因：我尝试构建一种排列树。我编写了一个函数permute :: String -> Tree Char来将字符串的所有可能排列可视化为树。但我不知道如何把这种树弄平。谢谢你的帮助。

我正在使用以下类型的树版本：

我的目标是获得一个函数，该函数返回一个对列表，[(Event,[Int])]其中[Int]包含每个事件的坐标（在树中到达它的路径），即如果树是：

然后我希望它返回[event,[0]]。我想忽略树的任何空头。

所以我的功能看起来像

然后对于拆分它需要递归地在每个子树上应用该函数。我想过这样做：

但这会给我提供任意长度的嵌套列表，以及其他几个问题。有任何想法吗？