四叉树删除

Question

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

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

为了检查兄弟姐妹，我应该存储一个指向父节点的指针，还是有一种方法可以递归地做到这一点？

感谢

Answer 1

对于一个四叉树移除你需要基本做到以下几点：

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

第1步之后，你基本上完成了。如果你想节省内存并保持树效率，那么你应该做的步骤2和3.

是的，你应该保留一个父节点的引用，使反向遍历高效。