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

Question

二叉树中的节点保持对父节点的引用是“传统的”（或“道德的”）吗？

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

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

我问是因为我遇到了一个问题，即在树中找到两个给定节点的最低共同父节点。如果每个节点都有对其父节点的引用，那么问题将非常容易解决，但这感觉就像在作弊！

谢谢

Answer 1

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

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

我发现最好使数据结构适合您的需求，而不是尝试使用其他逻辑来解决问题。毕竟，为什么树必须是有向图？使其定向是一个特定的实现，就像一个列表及其作为单链表或双链表的特定实现。

Answer 2

它仍然可以是所有权的有向图。考虑以下节点：

template <typename T>
struct node
{
    T data_;
    std::unique_ptr<node> left_child_;  // I own my children.
    std::unique_ptr<node> right_child_;
    node* parent_; // Just lookin' at my parent.
};

正如 Steven Meyer 上面所说，这真的不是作弊：构建数据结构来解决您的问题，不要担心它的道德问题 :-)

Answer 3

来自软件工程堆栈交换的交叉发布。

维基百科的定义说“例如，将一棵树作为一个整体来看，可以谈论给定节点的“父节点”，但一般来说，作为一种数据结构，给定节点只包含其子节点的列表，但不包含对其父级的引用（如果有）。 ”