Kindly explain this binary tree array

[lost110]

Kindly explain this binary tree with array representation. https://www.geeksforgeeks.org/binary-tree-array-implementation/
My question is why it's printing "Can't set child at 3, no parent found" and also at 4 for "D" AND "E" .

 // C++ implementation of tree using array 
// numbering starting from 0 to n-1. 
#include<iostream> 
using namespace std;
char tree[10];
int root(char key)
{
	if (tree[0] != '\0')
		cout << "Tree already had root";
	else
		tree[0] = key;
	return 0;
}

int set_left(char key, int parent)
{
	if (tree[parent] == '\0')
		cout << "\nCan't set child at"
		<< (parent * 2) + 1
		<< " , no parent found";
	else
		tree[(parent * 2) + 1] = key;
	return 0;
}

int set_right(char key, int parent)
{
	if (tree[parent] == '\0')
		cout << "\nCan't set child at"
		<< (parent * 2) + 2
		<< " , no parent found";
	else
		tree[(parent * 2) + 2] = key;
	return 0;
}

int print_tree()
{
	cout << "\n";
	for (int i = 0; i < 10; i++)
	{
		if (tree[i] != '\0')
			cout << tree[i];
		else
			cout << "-";
	}
	return 0;
}

// Driver Code 
int main()
{
	root('A');
	//set_left('B',0); //commented
	set_right('C', 0);
	set_left('D', 1);
	set_right('E', 1);
	set_right('F', 2);
	print_tree();
	system("pause");
}

Output:
Can't set child at 3, no parent found
Can't set child at 4, no parent found
A-C--F----

[stonedviper]

Because that's not how a binary tree is implemented

it's implemented

as follows

struct node
{
     int el;
     node*left;
     node*right;
}

this is how it is implemented not with an array...

[lost110]

I am talking about this specific code . I have to implement it using an array not a linked list.

[keskiverto]

My question is why it's printing "Can't set child at 3, no parent found"

set_left('D', 1);
// with
int set_left(char key, int parent)
{
	if (tree[parent] == '\0')
		cout << "\nCan't set child at"
		<< (parent * 2) + 1
		<< " , no parent found";
	else
		tree[(parent * 2) + 1] = key;
	return 0;
}

You call set_left(). The parent==1.
IF tree[1] has null, THEN you see
"Can't set child at (1*2+1)==3, no parent found"

Are you surprised that the code does what it should, or can't see why tree[1] is null?

[lost110]

@keskiverto
How does tree[1] has null? Thats my question.

[keskiverto]

char tree[10];

int main()
{
  root('A'); // effectively: tree[0] = 'A';
  // set_left('B',0); // commented out
}

You don't call set_left() with parent==0.
Therefore, you don't set value to tree[(0 * 2) + 1]. That is, to tree[1].

That refines the question to: what values the tree is initialized with?

int foo;
int main()
{
  int bar;
  // XX
}

What can you tell about values of 'foo' and 'bar' on line XX?
See Implicit initialization in https://en.cppreference.com/w/c/language/initialization

[lost110]

@keskiverto
Brother! I am not getting it! The only thing I have got is that A is the root! Why it can set C but not D and E. How parent[1] ==NULL ? And when I uncomment setleft(b,0).All alphabets are set and printed out ?

[lost110]

@Ganado @jonnin Guys can you explain this?

[keskiverto]

when I uncomment setleft(b,0)

What element of the array does setleft( 'b', 0 ); modify?


Seriously, can you answer:

What can you tell about values of 'foo' and 'bar' on line XX?

[dhayden]

The problem is that you're trying to add children to nodes that don't exist yet. This might be clearer if you change set_left() and set_right() to print the index of the parent instead of the child:

int set_left(char key, int parent)
{
        if (tree[parent] == '\0')
            cout << "\nset_left(" << key << "," << parent
                 << "): Can't set child because parent node doesn't exist.";
        else
                tree[(parent * 2) + 1] = key;
        return 0;
}

int set_right(char key, int parent)
{
        if (tree[parent] == '\0')
            cout << "\nset_right(" << key << "," << parent
                 << "): Can't set child because parent node doesn't exist.";
        else
                tree[(parent * 2) + 2] = key;
        return 0;
}

Now when I run the program I get:

set_left(D,1): Can't set child because parent node doesn't exist.
set_right(E,1): Can't set child because parent node doesn't exist.

The problem here is that node #1 represents the left child of the root. Since you haven't set the left child, you can't hang children off of it. It's like trying to place a Christmas tree ornament on a branch and missing the branch. The ornament just falls to the ground.

I think you're actually missing something more fundamental here though. In a binary tree, the code decides where where to add a new node, not the programmer. So you should really have function called add_node(char key). This function descends the tree looking for the proper place to put a new node for key. When it finds the place, it inserts it.

You'll probably also find that set_left() and set_right() are too restrictive. What you really want to know is the index of the left and right children of a node:

int right(int parent) { return parent*2 + 1; }
int left(int parent) { return parent*2 + 2; }

These functions let you find the left and right children for any purpose you need.

[dhayden]

stonedviper wrote:

Because that's not how a binary tree is implemented
it's implemented as follows
struct node
{
int el;
node*left;
node*right;
}

That's a typical way to implement a binary tree, but not the only way. If you know that the tree is balanced then storing it in an array saves the space occupied by the pointers and any overhead for storing the nodes on the heap. On a 64-bit system it could easily total 32 bytes of overhead to store a 4-byte integer.

Dave

[jonnin]

there was a morse code problem on here a few months ago that I can't find anymore where I shoved the code into an array as a BST. Here is that 'tree' shoved into an array. If you have a morse code text, the full class can do a dot left dash right BST traversal to find your char. The init method loop loads the 'tree' and the code2txt traverses it. Dunno if this helps see how to use such a thing or not. This is a little different because its static data loaded to the tree by hand. line 14/15 are a key to the concept.

class mc
{
	
  mctx mct[50]; //left room for numbers later.   	
  string tbl[256];
  public:	
  mc()
  {
	char init[] = "\0etianmsurwdkgohvf\0l\0pjbxcyzq";
	for(int dx = 0; dx < 30; dx++)
	{
	  mct[dx].c = init[dx];	
	  mct[dx].dot = (dx*2)+1;
	  mct[dx].dash = (dx*2)+2;
	}
	  tbl['e'] = ". ";   tbl['t'] = "- ";  tbl['i'] = ".. ";  tbl['a'] = ".- ";
	  tbl['n'] = "-. ";  tbl['m'] = "-- ";  tbl['s'] = "... ";  tbl['u'] = "..- ";
	  tbl['r'] = ".-. ";  tbl['w'] = ".-- ";  tbl['d'] = "-.. ";  tbl['k'] = "-.- ";
	  tbl['g'] = "--. ";  tbl['o'] = "--- ";  tbl['h'] = ".... ";  tbl['v'] = "...- ";
	  tbl['f'] = "..-. ";  tbl['l'] = ".-.. ";  tbl['p'] = ".--. ";  tbl['j'] = ".--- ";
	  tbl['b'] = "-... ";  tbl['x'] = "-..- ";  tbl['c'] = "-.-. ";  tbl['y'] = "-.-- ";
	  tbl['z'] = "--.. ";  tbl['q'] = "--.- ";
	}
		
  string txt2code(string in)
  {
	string out;
    for(int i = 0; i < in.length(); i++)
     out += tbl[in[i]];
    return out; 
  }  

  string code2txt(string in)
  {
	in += ' '; 
    string out = "";
   for(int i=0, dx = 0; dx < in.length(); dx++)
	{      
		switch(in[dx])
		{
		case '.': 
		i = mct[i].dot;
		break;
		case '-': 
		i = mct[i].dash;
		break;
		case ' ': 		
		out += mct[i].c;
		i = 0;
		break;
        default: //reset stream
         i = 0; 		
		}	
	}
    return out;	
  }
};


int main()
{
 mc x;
 string word = "... --- ... ---"; 
 cout << x.code2txt(word)<< endl;
}

[lost110]

Can anyone explain why tree[parent] == '\0' for set_left('D', 1)?

[ne555]

every element of `tree' is initialised to 0 because it is declared global.

[keskiverto]

The page that I posted a link to writes:

If an initializer is not provided:
* objects with automatic storage duration are initialized to indeterminate values (which may be trap representations)
* objects with static and thread-local storage duration are initialized as follows:
- pointers are initialized to null pointer values of their types
- objects of integral types are initialized to unsigned zero
- objects of floating types are initialized to positive zero
- members of arrays, structs, and unions are initialized as described above, recursively, plus all padding bits are initialized to zero

Your char tree[10]; is not inside any function. Therefore, it is at file scope.

Related page https://en.cppreference.com/w/c/language/storage_duration writes:

If no storage-class specifier is provided, the defaults are:
- extern for all functions
- extern for objects at file scope
- auto for objects at block scope

and:

The extern specifier specifies static storage duration and external linkage.

Now we can piece together the logic:
1. The array is at file scope.
2. The array does not have explicit initializer.
3. The array has static storage duration.
4. Members of the array are char, an integral type.
5. Members of the array are initialized to unsigned zero.
6. Unsigned zero, 0, equals character '\0', aka null.