binary-tree - 二叉树节点保持对其父节点的引用

Question

二叉树中的节点保留对其父节点的引用是“传统的”(或“道德的”)吗？

通常，我不会这么认为，仅仅因为树是有向图，因此定义了 PARENT-->CHILD 链接的事实并不意味着也定义了 CHILD --->PARENT。
换句话说，通过保留对父级的引用，我们会以某种方式破坏树的语义。

但我想知道人们是怎么想的？

我问是因为我遇到了在树中找到两个给定节点的最低公共(public)父节点的问题。如果每个节点都有一个对它的父节点的引用，这个问题就 super 容易解决了，但这感觉就像在作弊!

谢谢

Answer 1

您如何实现二叉树应该取决于您的需要。

如果您的应用程序需要在叶子到树干的方向上遍历树，那么最好的方法是实现对父节点的引用。

我发现最好让您的数据结构满足您的需求，而不是尝试使用其他逻辑进行变通。毕竟，为什么树必须是有向图？使其定向是一个特定的实现，很像一个列表，它的特定实现是一个单链表或双链表。