Notes

Tree node with integer data.
// Structure of each node of the tree

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


Implementation of Binary Tree (Linked Representation):
Let us create a simple tree with 4 nodes. The created tree would be as follows.

#include <stdio.h>
#include <stdlib.h>

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

// newNode() allocates a new node with the given data and NULL left and //right pointers.

struct node* newNode(int data)
{
// Allocate memory for new node
struct node* node = (struct node*)malloc(sizeof(struct node));
// Assign data to this node
node->data = data;
// Initialize left and right children as NULL
node->left = NULL;
node->right = NULL;
return (node);
}

int main()
{ // Create root
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
getchar();
return 0;
}
 
Implementation of Binary Tree (Array Representation):
In order to represent a tree using an array, the numbering of nodes can start either from 0–(n-1) or 1– n, consider the below illustration as follows:
Illustration:
A(0)
/
B(1) C(2)
/
D(3) E(4) F(6) A(1)
/
B(2) C(3)
/
D(4) E(5) F(7)

Case 1: (0—n-1)
if (say)father=p;
then left_son=(2*p)+1;
and right_son=(2*p)+2;
Case 2: 1—n
if (say)father=p;
then left_son=(2*p);
and right_son=(2*p)+1;



// C++ implementation of tree using array
// numbering starting from 0 to n-1.

#include<bits/stdc++.h>
using namespace std;
char tree[10];

int root(char key) {
if (tree[0] != '')
cout << "Tree already had root";
else
tree[0] = key;
return 0;
}

int set_left(char key, int parent) {
if (tree[parent] == '')
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] == '')
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] != '')
cout << tree[i];
else
cout << "-";
}
return 0;
}

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

Output
ABCDE-F---