0
$\begingroup$

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...

Improve this question
$\endgroup$
2
  • $\begingroup$ You have shown that these two are not equivalent, the number of children does not match. Well, the tree is an acyclic graph, doubly linked list may be circular. The standard Binary Tree (afaik) does not store the parent and is directed. But even this extended version is not equivalent, but probably is similar under your definition. I am a bit lost, what is your question? The problem is that you may think of BT as you wish, it is for sure extended version, but how you draw thinks is not that relevant. Could you rewrite the question? $\endgroup$ – Evil Apr 22 '17 at 16:10
  • $\begingroup$ YOu might want to study about Linear and Non-Linear data structures @Steve Fan $\endgroup$ – Shubham Singh rawat Apr 22 '17 at 17:36
3
$\begingroup$

"[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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Um...binary three? Or Ternary tree? I don't know much about computer science... $\endgroup$ – Steve Fan Apr 22 '17 at 17:07
  • 1
    $\begingroup$ @SteveFan A node in a binary tree has two children + one parent, in total three nodes. A tree is classified by the number of children. $\endgroup$ – SE - stop firing the good guys Apr 22 '17 at 17:14
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.