6

我正在为四叉树编写删除方法。

现在,当您删除节点中的项目时,您将需要检查其兄弟节点以查看是否需要折叠节点并将它们合并为一个。

为了检查兄弟姐妹,我应该存储一个指向父节点的指针,还是有办法以递归方式更好地做到这一点?

谢谢

4

1 回答 1

12

要在四叉树中删除,您基本上需要执行以下操作:

  1. 找到对象的叶子,然后从该列表中删除它(包含叶子的节点)
  2. 检查叶子的删除是否使节点为空,如果是,则删除节点本身。
  3. 检查周围的节点是否也为空,如果是,则通过“取消细分”将此节点折叠到父节点中(这可能会递归地做起来很棘手)。诀窍是检查相邻节点是否有任何东西。如果没有,您可以安全地将整个象限扔掉并提升一个级别。递归地执行此操作会将树折叠回存在具有叶子的相邻节点的位置。

完成第 1 步后,您基本上就完成了。如果您想节省内存并保持树的效率,那么您应该执行第 2 步和第 3 步。

是的,您应该保留父节点引用以提高反向遍历的效率。

于 2012-02-22T01:38:14.983 回答