6

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

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

使用或不使用父节点指针

以下是定义Node数据结构的 2 个典型示例代码。

没有父节点指针

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 容量的限制，我认为我们可以放弃没有父节点的解决方案，不是吗？

也许不相关

就像链表和双链表一样，我们应该使用双链表来实现Stack和Queue吗？

4

7 回答 7

11

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

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

父指针或双向链表的问题在于，不变性突然消失了。对于不可变对象，您必须在创建时指定有关该对象的所有内容。因此，如果要保持不变性，则在创建其子节点之前不能创建节点（因为必须在创建时指定这些子节点），但也不能在子节点上设置父指针父级已创建（因为父级不存在）。换句话说，不变性不能很好地处理循环依赖。同样，你不能创建一个没有一些突变的双向链表，因为没有突变你不能创建第一个节点，直到第二个节点被创建，你可以'

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

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

另外，另一个注意事项：您询问使用链表与堆栈和队列的双向链表。不需要使用双向链表来实现堆栈，因为除了第一个元素（如果堆栈是可变的，第二个元素）之外，您不需要遍历任何元素的效率。有一个可爱的技巧来实现一个带有两个堆栈的队列，它提供了摊销的恒定时间队列操作。但是，如果您不使用它，那么队列对于双向链表或数组也是一个不错的用例。

于 2012-05-03T07:15:57.813 回答
9

树很少需要用于常规/简单操作的父指针。只有当你在做一些奇特的事情（比如从叶子到节点回溯路径）时，才可能需要父指针。

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

还有一些历史原因。此外，内存限制要求您使用最小、最紧凑的结构。即使到今天，也有一些嵌入式系统对内存有严格的要求。此外，您不会真的想弄乱现有的有效代码，所以这些东西会坚持下去。

所以我的问题是为什么有一些基于没有父节点的结构的解决方案？

可能是因为他们的应用程序不需要经常访问父级。请注意，这是典型的时空权衡。

就像链表和双链表一样，我们应该使用双链表来实现堆栈和队列吗？

这取决于您的应用程序以及您的数据结构需要为每个操作提供的保证。此外，您可能有兴趣查找XOR 链表！

于 2012-05-03T07:13:06.837 回答
4

对于许多算法，父指针是多余的。然而，它们确实会产生内存开销和额外的算法复杂性。

就像链表和双向链表一样......

不同之处在于后者可以执行更多具有O(1)时间复杂度的操作。成本是额外的内存开销。换句话说，存在时间-记忆权衡。

我们应该使用双向链表来实现堆栈和队列吗？

两者都可以使用双向链表来实现。然而，对于这两种结构中的一种（我留给你来确定是堆栈还是队列！），双向链表的额外开销绝对不会买任何东西。

于 2012-05-03T07:10:46.197 回答
1

仅当您有直接“跳入树”的代码时，您才需要父节点。例如，在 Web 浏览器中，您总是在事件处理程序中获取 DOM 元素，并且必须从那里向上遍历 DOM 树，以找到一些父 HTML 元素。

但是，在许多数据结构中，您通常从根开始向下走，深度优先或广度优先 - 没关系，您知道从哪里开始，因此不需要父引用。

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search

基本上，您的算法决定了您的数据结构。两者结合在一起，考虑一个没有另一个是没有用的。

于 2012-05-03T07:08:53.603 回答
1

二叉树没有定义需要引用父节点的操作。你总是从上到下遍历。

于 2012-05-03T07:08:56.817 回答
1

大多数平衡树，如红黑树和 AVL 树，确实在其节点结构中嵌入了父指针。它们是具有一些额外属性的二叉搜索树。原因是它使执行必要的重新平衡操作变得更加简单。

还有一些没有父指针的场景非常麻烦。

考虑一棵二叉搜索树，然后从中随机选择一个受害者节点。你怎么把它从树上移走？如果没有父指针，您将不知道它在树中的哪个位置，因此您必须执行搜索以找到其父指针，以便知道要更新的边缘。使用父指针，您可以大致如下进行：

parent = victim->parent;
if (parent) {
    if (parent->left == victim) {
        parent->left = NULL;
    } else {
        parent->right = NULL;
    }
}
... free(victim);

另一个没有父指针的棘手操作是查找节点后继。特别是如果树允许存储具有相同键值的多个对象，如果您正在实现多重集，则需要这样做。但是有了它们，这很容易：

bstree *successor(bstree *node) {
    // If node has a right child, the successor is the minimum 
    // node of that subtree.
    if (node->right) {
        return minimum(node->right);
    }
    // If node hasn't, we look upwards.
    bstree *x = node->parent;
    while (x && node == x->right) {
        node = x;
        x = node->parent;
    }
    return x;
}

父指针带走了数据结构的美感。他们这样做是为了让您不能再将一棵树视为树木的组合，这是一种耻辱。但是在大多数树结构的实际实现中，我已经看到它们存在，因为它们非常有用。

于 2016-11-01T12:47:47.087 回答
0

一些平衡树的实现确实维护了一个指向父级的指针。显然Glib 平衡树的节点包含这样的指针。

但是，当您有一个遍历树的内部递归函数时，您可以对其进行编码，以便它在递归调用期间同时传递树及其直接父级。

于 2012-05-03T07:10:35.740 回答