四叉树去除

Question

我正在为四叉树编写一个删除方法.

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

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

谢谢

Answer 1

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

1. 找到对象的叶子,然后从该列表中删除它(包含叶子的节点)
2. 检查叶子的移除是否将节点留空,如果是,则删除节点本身.
3. 检查周围的节点是否也是空的,如果是,则通过"unsubdividing"将此节点折叠到父节点(这可能会递归地执行).诀窍是检查相邻节点中是否有任何内容.如果没有,你可以安全地将整个象限扔掉并提升一级.以递归方式执行此操作会将树折叠回到存在叶子的相邻节点的位置.

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

是的,您应该保留父节点引用以使反向遍历有效.