c – 我应该将父指针存储在树/图节点中吗？
发布时间：2020-12-16 07:48:56 所属栏目：百科 来源：网络整理
导读：我正在开发一个像数据结构的树/图. 它应该更像是有向无环图. 其中一个要求是找到从根到特定节点的路径,这意味着当用户选择一个节点时,将突出显示来自根的路径. 那么,问题是我应该在每个节点中存储父指针吗？ 或者更普遍的问题是我应该何时在每个节点中存储父
|
我正在开发一个像数据结构的树/图.
它应该更像是有向无环图. 其中一个要求是找到从根到特定节点的路径,这意味着当用户选择一个节点时,将突出显示来自根的路径. 那么,问题是我应该在每个节点中存储父指针吗？ 提前致谢！ PS.父指针==指向父节点的指针. 解决方法
通常,只有在要使用需要它的算法时才将指针存储回父级.否则,在用于存储指针的内存和在插入节点或重新平衡/重新组织树时更新这些指针的额外复杂性方面都是不必要的开销.
与树一起使用的典型算法(广度优先和深度优先搜索和遍历)不需要父指针,这就是为什么普通的普通树实现通常不包括它们. 您的“从根突出显示路径”要求可能会使父指针变得有用,尽管还有其他方法可以实现它.通常,应该避免将冗余信息放入数据结构中,直到证明它们是出于性能原因而必需的. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |