1
$\begingroup$

Why sometimes we would want to convert generic trees or forests into a binary tree? And what's the main principle behind this convertion?

$\endgroup$
5
  • $\begingroup$ what kind of conversion are you thinking of? $\endgroup$ Jan 11, 2023 at 11:30
  • $\begingroup$ @user253751 how many conversions are there? I know just one kind of conversion that converts a generic tree (or a forest) to equivalent binary tree. $\endgroup$ Jan 11, 2023 at 12:19
  • $\begingroup$ equivalent in what sense? I could say the binary tree is not equivalent to the non-binary tree because they have different degrees at their vertices, and this makes them different. Perhaps one is a minimal spanning tree and the other one isn't. And a forest may be unconnected while a tree (binary or not) is connected which is also a very big difference. $\endgroup$ Jan 11, 2023 at 12:20
  • $\begingroup$ @user253751 that's exactly what I'm asking. When converting one tree to another, there must be something that should remain the same. $\endgroup$ Feb 13, 2023 at 6:15
  • $\begingroup$ and that depends on the application! $\endgroup$ Feb 13, 2023 at 11:39

2 Answers 2

1
$\begingroup$

Such a conversion can occur when trying to represent an abstract tree on a computer.

If you consider an edge between a node and one of its children, it is natural to implement it as a memory pointer. However, on a generic tree, that would mean that each node could contain any number of memory pointers. This is not acceptable.

In an usual representation, each node $x$ contains a linked-list containing all children $[y_1, y_2, …, y_k]$ of the node $x$. However, in terms of memory pointers, that means that $x$ contains a pointer to its first child $y_1$, and each $y_i$ contains a pointer to the next sibling $y_{i+1}$.

In such an implementation, each node contains exactly 2 pointers: one to its first child and one to its next sibling. This is a binary tree.

When considering a forest, the idea is exactly the same, since the forest could be seen as a linked-list of the roots of the trees in the forest.

As an example, you could use the following structures:

  • In C:
struct node{
     int value;
     struct node* first_child;
     struct node* next_sibling;
};
  • In OCaml (here, the next_sibling pointer is not explicit, since we are using the list type):
type tree = Node of int * tree list
type forest = tree list
$\endgroup$
2
  • $\begingroup$ When you say, "this is not acceptable", is it because the static nature of arrays in languages like C? Can't we implement it with dynamic array? $\endgroup$ Feb 13, 2023 at 6:12
  • $\begingroup$ You are right that this is possible, but that would potentially use a lot of memory per node. $\endgroup$
    – Nathaniel
    Feb 13, 2023 at 10:08
0
$\begingroup$

Binary trees have nodes of constant size, using two links: to the first descendant and to the sibling. This makes allocation easier.

$\endgroup$
2
  • $\begingroup$ A sibling link allows any arity of tree to be represented. A binary tree has a left descendant and a right descendant. $\endgroup$ Feb 13, 2023 at 11:46
  • $\begingroup$ @user253751: yes of course. I don't know why I made this answer ?! $\endgroup$
    – user16034
    Feb 13, 2023 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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