CODEWITHSUNDEEP
data-structurestree
Dimitris Dimitriadis
Dimitris Dimitriadis

Reputation: 163

Represent Free Tree to Binary Tree

This exercise is from the book "algorithms in c++". Suppose that there is a free tree like this enter image description here

First Question: Could we represent this free tree as a binary tree?

I think that we cannot represent this free tree as a binary tree because there are some nodes that have more than 2 children.

Second Question: How many ordered trees could we represent from this free tree?

I cannot understand the question. There aren't keys in the nodes in order to decide how to create an ordered tree.

Upvotes: 2

Views: 661

Answers (1)

Codor
Codor

Reputation: 17605

If I understood the question correctly, the task is that of representing a tree as a binary tree, i.e. to use a data structure for binary trees to represent arbitrary trees. Speaking more structurally, the question demands for a method to injectively map arbitrary trees to binary trees.

The technique is described here; the basic idea is to represent the children c_1,...c_nof a node a, which may be more than two, by an arbitrarily chosen child, say c_1, which becomes the left child of a. As the right child of c_1, the next child, c_2 is stored; and so on. This means that for each node, one child is stored in the left subtree, while in the right subtree by chosing always the right child, the 'siblings' of 'alternatives' of the child are stored. The approach can be sketched as follows. Please bear with me for the relatively poor textual representation.

arbitrary tree

       a
   /  | |   \
c_1 c_2 c_3 c-4

binary tree

    a
   /
 c_1
    \
    c_2
       \
       c_3
          \
          c_4

Upvotes: 1

Related Questions