CODEWITHSUNDEEP
treeintegerbinary-treebinary-search-tree
Bob
Bob

Reputation: 1396

Building a Binary Tree from Given Data

I'm having trouble understanding how to build a binary tree from the given set of numbers...

30
15
4
NULL
NULL
20
18
NULL
19
NULL
NULL
NULL
35
32
NULL
NULL
38
NULL
NULL

I've gone through my book and notes and can't seem to figure it out. What do the NULL's mean? If you could show me a correct built tree it'd be most helpful, I'm a very visual person. I've changed the value's and NULL order from my homework, so don't worry about me not learning from it!

Upvotes: 2

Views: 1434

Answers (3)

lrleon
lrleon

Reputation: 2648

Very probably your question deals with Łukasiewicz codes.

Given a binary tree, a Łukasiewicz code is the sequence generated by the full preorder traversal where the internal nodes are labeled witn a and the external ones (the NULL pointers) are labeled with b. The use of 'a/b` is matter of convention. You could use any other symbols; bits, for instance.

For example, this tree

enter image description here

which should be the tree corresponding to your problem, has as Łukasiewicz code the following sequence:

aaabbaababbbaabbabb

Consider drawing the same tree but with the external nodes. Some such as

enter image description here

In this figure, each external node is drawn with a horizontal bar. Each external node would be a NULL pointer.

Now perform a preorder traversal. When you find an external node (that is a NULL pointer) you print NULL and eol. When you find a internal node (that is anything different than NULL) you print the key value plus eol.

You will obtain exactly the sequence that you have provided.

So, the task would be to reconstruct the original tree from this sort of Łukasiewicz traversal. Such task could be accomplished by a routine such as this:

Node * to_tree(istream & input)
{
  string val;
  input >> val;
  if (val == "NULL")
    return nullptr;

  Node * p = new Node;
  p->get_key() = atoi(val.c_str());
  p->left  = to_tree(input);
  p->right = to_tree(input);

  return p;
}

If the sequence was correctly generated, then you could safely call this function without any risk; it will finish. If you are interested in validate the input, then you could do a preprocessing. You initialize a counter at zero. Each time you find a key you add 1 and when you find a NULL you subtract 1. A correct sequence must result at the end in -1. This is thus because all binary tree of n nodes has n + 1 external nodes (or NULL pointers). The last visited node is external and this is the only and last time that the counter reaches -1.

You could adapt his routine to you tree implementation and write a program:

int main(int, char **)
{
  Node * root = to_tree(cin);
  return 0;
}

You compile it and then you execute:

./my-program < my-input

et voila!

Upvotes: 1

EkcenierK
EkcenierK

Reputation: 1439

I would assume that the first node indicates the root node of the tree.

The following two nodes in the list are the immediate leaves.

I would presume that the NULL values indicate that the preceding node in the list has either only one leaf or no leaf nodes.

As for the node ordering in the tree structure, for it to be a binary search tree, each pair of leaf nodes should be either greater or smaller than the parent node, and typically the smaller value should be the left hand leaf node. This means that you can search the tree by starting at the root and choosing the higher or lower leaf node, traversing down the tree until you find the node you want.

Upvotes: 0

tekan
tekan

Reputation: 216

If you only consider the numbers here is how the binary tree should look like:

                +--+
                |30|
          +------------------+
          |                  |
       +--+                 ++-+
       |15|                 |35|
  +------------+         +----------+
  |            |       +--+       +--+
+-+          +-++      |32|       |38|
|4|          |20|      +--+       +--+
+-+          +--+
       +-----+
       |18|
       +---+
           |
           +----+
             |19|
             +--+

Now, If you go through the list again, you will see that the NULL denote when to stop. 30 has a child, 15, 15 has a child 4, 4 does not have a child (followed by two NULLs), going one up, 15 has a second child 20, 20 has a children: 18. 18 does not have left children (denoted by a NULL after), but has a right children 19. It does not have any children (two NULLs). 20 also don't have any more children: NULL leading to 15's other child: 35, etc.

Upvotes: 2

Related Questions