在 Smalltalk 中构建和查询示例通用树

发布于 2024-11-30 18:25:51 字数 426 浏览 0 评论 0原文

使用 SqueakSource 上的 BTree 包（或您可能知道的任何其他包）并给出以下树，

-Root
|
--Node1
|
--Node2
---Node21
---Node22
---Node23
----Node231
----Node232
-----Node2321
----Node233
|
--Node3

我尝试编写以下内容但没有成功：

构建树
给定 Node23 回答其直接子节点
给定 Node2 回答其所有子节点
给定任何节点，回答它的父级
收集所有子级

这不是家庭作业，我之所以要求一个基本示例是因为在 BTree 的情况下，文档几乎不存在，并且测试不足以弄清楚基本用法，实际上是示例混合有断言并使用便捷方法。

原文

Using the BTree package at SqueakSource (or any other you may know) and given the following tree

-Root
|
--Node1
|
--Node2
---Node21
---Node22
---Node23
----Node231
----Node232
-----Node2321
----Node233
|
--Node3

I've tried to write the following but without success:

Build the tree
Given Node23 answer its direct children
Given Node2 answer all its children
Given any Node, answer its parent
Collect all the children

This is NOT homework, the reason why I'm asking for a basic example is because in the case of BTree, documentation is almost inexistent, and tests are not good enough for figuring out basic usage, actually examples are mixed with asserts and using convenience methods.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

绅刃 2024-12-07 18:25:51

如果您不太关心执行速度，SqueakSource 中有一个用于此目的的广泛记录的包 http:// /www.squeaksource.com/TreeLW.html 最初是为 VisualWorks 发布的。

您可以用来构建树的一个类是 SKPVTreeLW，它支持值、子树、超树和键。您可能会实现这样的示例：

t := SKPVTreeLW
    key: '1'
    value: 'N' 
    subTrees: { 
        ( SKPVTreeLW key: '2' value: 'A' ) .
        ( SKPVTreeLW key: '3' value: 'B' subTrees: { 
            ( SKPVTreeLW key: '31' value: 'C' subTrees: { ( SKPVTreeLW key: '311' name value: 'D' ) } ) .
            ( SKPVTreeLW key: '32' value: 'E' subTrees: Array empty ) } ) .
        ( SKPVTreeLW key: '4' value: 'F' ) .
        ( SKPVTreeLW key: '5' value: 'G' ) .
        ( SKPVTreeLW key: '6' value: 'H' ) }.
" Subtrees of node 'B' "
t recursiveDetect: [ : s | s value = 'B' ] 
        inclusive: true 
        topDown: true 
        breadthFirst: true.
" or searching by key "
t atKey: '3'
" Childrens as nodes "
t recursiveSubTrees: true.
" Direct children "
t values.

If you're not so concerned with execution speed, there is an extensively documented package in SqueakSource for that purpose http://www.squeaksource.com/TreeLW.html which was originally released for VisualWorks.

One class you may use for building your tree is SKPVTreeLW, which supports value, subtrees, supertree, and a key. You may achieve your example implementing something like this:

t := SKPVTreeLW
    key: '1'
    value: 'N' 
    subTrees: { 
        ( SKPVTreeLW key: '2' value: 'A' ) .
        ( SKPVTreeLW key: '3' value: 'B' subTrees: { 
            ( SKPVTreeLW key: '31' value: 'C' subTrees: { ( SKPVTreeLW key: '311' name value: 'D' ) } ) .
            ( SKPVTreeLW key: '32' value: 'E' subTrees: Array empty ) } ) .
        ( SKPVTreeLW key: '4' value: 'F' ) .
        ( SKPVTreeLW key: '5' value: 'G' ) .
        ( SKPVTreeLW key: '6' value: 'H' ) }.
" Subtrees of node 'B' "
t recursiveDetect: [ : s | s value = 'B' ] 
        inclusive: true 
        topDown: true 
        breadthFirst: true.
" or searching by key "
t atKey: '3'
" Childrens as nodes "
t recursiveSubTrees: true.
" Direct children "
t values.

回复收藏 0 原文

标点 2024-12-07 18:25:51

B-Tree 是一种将键与值关联起来的排序数据结构。 B 树允许您处理大量数据并保证在对数时间内搜索、插入和删除。 SqueakSource 上的 BTree 包遵循 Smalltalk Dictionary 协议：

at: 和 at:ifAbsent: 用于搜索给定键的值，
at:put: 用于插入键和值对，以及
removeKey：用于删除一个key。

此外，还支持您从 Dictionary 中了解到的所有迭代器函数（do:、keysDo:、valuesDo:、<代码>keysAndValuesDo:, ...);以及其他一些迭代键范围的方法（from:do:、from:to:do:、upTo:do: ，...）。通常，您的应用程序代码中不需要 B-Tree 集合，除非您的内置 Dictionary 类存在性能问题。

在我看来，你试图修改 B 树的内部工作原理。您不应该这样做，BTree 类会自动重新组织自身以始终提供最有效的表示（这主要是测试验证的）。如果您想管理自己的树，为什么不创建自己的 Node 类，其中包含子节点的 OrderedCollection 和父链接？