4


我在一次采访中被问到双向链表和二叉树的节点结构之间的区别。

双向链表结构 

typedef struct
{
int data;
struct node * next;
struct node * prev;
}node;

二叉树结构 

typedef struct
{
int data;
struct node * left;
struct node * right;
}node;
  1. 在双向链表中，我们使用指针在线性排列的列表中前后遍历。
  2. 但是其中左右指针用于访问左右节点。

除了使用方式之外，我没有发现节点结构有任何区别。你能给我一些不同吗？？？

4

3 回答 3

11

我想你已经回答了你自己的问题。除了指针 (next/prev和left/right) 的名称有明显差异外，差异是：

  • 在双向链表中，如果n.next链接到m则m.prev链接到n. 在二叉树中情况并非如此。
  • 在双向链表中，一个节点最多可以有两个链接。在二叉树中，每个节点最多有一个链接。
  • 在双向链表中，可以跟随链接并最终到达您开始的节点。这在二叉树中是不可能的。

如果双向链表也是循环的，则以下也成立：

  • 在具有一个节点的循环双向链表中，n.next链接到n并且n.prev还链接到n。这在二叉树中是不可能的：n.left并且n.right不要链接到同一个节点。
  • 在具有一个节点的二叉树中，n.next可以n.prev不指向任何节点（即，树只是一个叶节点），但在具有一个节点的循环双向链表中，两个链接总是有一个值（尽管指向同一个节点）。
  • 在二叉树中，为n.leftor取值是可选的n.right。如果二叉树不平衡，则可能是所有节点都有值 forn.right而不是 for n.left。对于所有指针都有值的循环双向链表，情况并非如此。

在结构和内容方面，节点是相同的，但不同之处在于指针的使用方式以及它们的值可以是什么。

于 2012-07-09T10:11:59.177 回答
4

您可以概括：双向链表和二叉树都是有向图的示例，其中每个节点最多可以有两个传出边（因为这是结构中有多少指针字段）。

每个数据结构都施加了额外的限制（例如，在这两种情况下，整个图都可以从根节点到达，但只有在双向链表中，整个图才能从每个节点到达）。这些限制表征了不同的数据结构，但对用于表示节点的结构没有影响。

有时你想要一个二叉树，其中每个节点都有一个指向其父节点的指针——在这种情况下，两个结构会不同。

于 2012-07-09T10:15:43.803 回答
3

您是绝对正确的：假设相同的有效负载类型（在您的情况下是int），这两种节点类型的二进制布局是相同的。只有两个指针的使用使两种节点类型不同。

如果您不关心可读性，则可以使用节点

typedef struct node {
    int data;
    struct node *p1;
    struct node *p2;
} node;

表示二叉树和双向链表。不过，这不是一个好主意，因为代码会立即变得难以被其他程序员识别。

于 2012-07-09T10:12:47.880 回答