双链表和二叉树的节点结构有什么区别？

Question

我在接受采访时被问及双链表和二叉树的节点结构之间的区别.

双重链表结构

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

二叉树结构

typedef struct
{
int data;
struct node * left;
struct node * right;
}node;  

1. 在双向链表中,我们使用指针在线性排列的列表中向后和向前遍历.
   
2. 但是左右指针用于访问左右节点的位置.

我发现节点结构没有任何区别,除了它们的使用方式.你能不能给我一些分歧？

Answer 1

我想你已经回答了自己的问题.除了指针(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.left或者赋值n.right.如果二进制树不平衡,则可能是所有节点都具有值n.right但不是n.left.对于所有指针都具有值的循环双向链表,情况并非如此.

在结构和内容方面,节点是相同的,但不同之处在于如何使用指针以及它们的值是什么.