c - 为什么 C 中的许多二叉树数据结构没有父节点指针？

Question

我是 C 编程的新手，我正在用 C 学习 C 算法。

这是我关于如何定义二叉树节点数据结构的问题。

使用或不使用父节点指针

这里有 2 个典型的示例代码，用于定义 Node 数据结构。

无父节点指针

typedef struct binaryTreeNode_{
  int key;
  void *data;
  binaryTreeNode_ *leftNode;
  binaryTreeNode_ *rightNode;
} binaryTreeNode;

带父节点指针

typedef struct binaryTreeNode_{
  int key;
  void *data;
  binaryTreeNode_ *leftNode;
  binaryTreeNode_ *rightNode;
  binaryTreeNode_ *parentNode;
} binaryTreeNode;

我的问题

显然，使用带有父节点指针的节点结构将使很多工作变得更加容易。像遍历一个节点/一棵树，DFS/BFS 和二叉树。所以我的问题是为什么有一些基于没有父节点的结构的解决方案？。

有什么历史原因吗？如果仅仅因为RAM/DISK容量的限制，我想我们可以放弃没有父节点的解决方案，不是吗？

可能不相关

就像Linked List和Double Linked List一样，我们是否应该使用Double Linked List来实现Stack和队列?

Answer 1

使用没有父指针的树有很好的理由，内存使用不是问题。

在函数式编程世界(想想 Lisp、Scheme、Standard ML、OCaml、Haskell、F# 等等)，树和链表是非常常见的数据结构，所以即使在 C 中也有很多关于树和列表的思考受 FP 的影响。树和列表是递归定义的(树是叶子节点或子节点是树的内部节点，列表是 nil 或带有数据元素和附加列表的节点)，并且它们几乎总是被实现为不可变的数据结构。 Immutability很有帮助，因为它使并行性更清晰(没有程序员可见的锁)，函数之间的数据共享更好(不必复制数据)，并且证明更容易。

父指针或双向链表的问题在于，不变性突然消失了。对于不可变对象(immutable对象)，您必须在创建时指定有关该对象的所有内容。所以，如果你想保持不变性，你不能创建一个节点，直到它的 child 被创建(因为那些 child 必须在创建时指定)，但是你也不能在 child 之前设置父指针已创建父级(因为父级不存在)。换句话说，不变性不能很好地处理循环依赖。类似地，你不能在没有一些突变的情况下创建一个双向链表，因为没有突变你不能创建第一个节点直到第二个节点被创建，并且你不能在第二个节点上设置前一个指针直到第一个节点已创建。

FP 的人们设法用严格不可变的数据结构编写了大量代码，并证明了许多有用的属性。当然，维护父指针会使程序员的生活更加困难，因为一旦更改树中的一个节点，您就必须更改其所有子节点的父指针，这是一种痛苦。

因为很多关于列表和树的思考都受到了 FP 的影响，它不包括父指针或双向链表，并且因为维护父指针是一件很棘手的事情，可能会引入错误，所以许多 C 树实现不使用父指针。

---

另外，还有一个注意事项:您问及使用链表还是双向链表来处理堆栈和队列。不需要使用双向链表来实现堆栈，因为除了第一个(和第二个，如果堆栈是可变的)之外，您不需要遍历任何元素的效率。有一个可爱的技巧可以实现具有两个堆栈的队列，它提供分摊的恒定时间队列操作。不过，如果您不使用它，队列也是双向链表或数组的不错用例。