Is binary tree just a two-dimension-doubly-linked-list?

Question

We all know the structure of a binary tree:

struct binary_tree {
  binary_tree *parent;
  int          data;
  binary_tree *left;
  binary_tree *right;
};

So a doubly linked list has the following structure:

struct linked_list {
  linked_list *prev;
  int          data;
  linked_list *next;
};

But a binary tree can also be manipulated like this:

struct my_linked_list {
  my_linked_list *prev;
  int             data;
  my_linked_list *next0;

  my_linked_list *next1;
} binary_tree;

By that, I have "proven" that binary tree shares a similarity to doubly linked list. (with the addition of another next element)

So my question is here: Is binary tree really a vertically-descending graph, or just an extension to the linked list, that can be drawn horizontally?

I know this is a kind of stupid and meaningless question but it was confusing me for years and years. I am just an apprentice to the computer science...

Answer 1

"[A] binary tree shares a similarity to doubly linked list"

Why, yes, it does, but the doubly linked list format you have made is really just a way to represent a connected graph, with the one limitation that a node can be connected to at most 3 other nodes. A lot of structures could fit into that format, for instance a binary tree or many cyclic structures in addition to lists.

You have made one limitation to a general graph, of which binary trees are a subset. The reason we care about more restricted versions of graphs is that it allows for many useful optimizations. Your two dimensional doubly linked list has many redundant properties regarding use as a binary tree, for instance it allows for cyclic structures, which a binary tree can not be, and it includes information about the parent node, which is also unnecessary as such trees are used for descending searches.

Answer 2

Well, No. I think you have observed similarity in the use of pointers in both of these data structures. But there are some differences. I think you should think these data structures a bit more abstract manner $-$ think them as the set of objects and relationships between those objects.

For doubly linked list, there is a set of nodes containing data and there are two relations defined on these nodes $-$ Predecessor and Successor.

For binary tree, you observe that you can also define two relations $-$ LeftChild and RightChild which are analogous to Predecessor and Successor. But there is additional relationship between noded called Parent. The corresponding couterpart is not there for doubly linked list.