在内存有限的二叉树中查找第一个 null

发布于 2024-07-25 11:07:40 字数 320 浏览 9 评论 0原文

我有一个二叉树，其中每个节点都可以有一个值。

我想找到树中值为空并且最接近根的节点。如果有两个节点到根的距离相同，则任意一个都可以。我需要最小化对二叉树的读取访问次数。假设工作内存仅限于 k 个节点。

深度 k 的 DFS 是详尽的，但除非我首先遍历整个树，否则不会找到最近的节点。 BFS 会找到最接近的值，但可能会失败，因为 DFS 可以使用相同的内存找到更深的空值。

我希望对树进行最少的读取访问并找到最近的空节点。

（我最终也需要在 n 路树中实现这一点，所以通用的解决方案会很好。没有对树的写访问权限，只需读取。）

原文

分享到QQ

分享到微博

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

发布评论

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

柳絮泡泡 2024-08-01 11:07:40

您可能需要查看迭代加深深度优先搜索。它会自动找到最近的节点，但能够达到与 DFS 相同的深度。但它将使用更多的读取访问。

您还可以从 BFS 开始，如果在允许的内存中找不到空值，则运行 DFS。

回复收藏 0 原文

撩发小公举 2024-08-01 11:07:40

我将通过简单的树修剪来实现 DFS。因此，您必须运行整个树是不正确的。

例如，如果您在高度 h 处找到了空值，则可以跳过位于相同或更深的位置。

回复收藏 0 原文

﹏雨一样淡蓝的深情 2024-08-01 11:07:40

如果您无法更改数据结构，那么您将必须读取每个节点 - 广度优先。

如果您可以更改数据结构，那么每个节点都可以记录第一个空子节点的相对深度。（每个都从其子级的等效值中计算出来）。

然后你就知道在寻找最早的空值时要追踪树中的哪一行。

回复收藏 0 原文

猫弦 2024-08-01 11:07:40

如果您愿意将树存储在数组中，则有一种简单的方法。与每个节点都有指向其左子节点和右子节点的指针不同，节点 n 的子节点在数组中是 2n + 1 和 2n + 2。（如果 n != 0，则节点 n 的父节点为 (n-1)/2。）

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

简单地线性迭代数组相当于 BFS，但空间要求为 O(1)。

这可以很容易地扩展到n叉树。例如，在三叉树中，左孩子为 3n+1，中心为 3n+2，右孩子为 3n+3，如果 n !=0，则父孩子为 (n-1)/3。

There is a simple way, if you're willing to store your tree in an array. Rather than each node having pointers to its left and right children, the children of node n are 2n + 1 and 2n + 2 in the array. (And node n's parent is (n-1)/2, if n != 0.)

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

Simply iterating through the array linearly is equivalent to a BFS, but with space requirements of O(1).

This can easily be extended to n-ary trees. e.g., in a ternary tree, the left child is 3n+1, center is 3n+2, right is 3n+3, and parent is (n-1)/3 if n !=0.

回复收藏 0 原文

~没有更多了~