Non-Linear Data Structures & Basics
Trees are non-linear; data branches out instead of sitting in a sequence, drastically speeding up searches.
A tree contains a root node, and remaining nodes partition into disjoint sets (subtrees).
Terminology & Properties
Leaf nodes have no successors. Level = distance from root. Height = total levels. Depth = edges from root.
Binary trees have utmost 2 children. Nodes at level 'L' = 2^L. Total edges 'e' = n - 1.
1.0.0 Array Implementation Theory
0-Indexed Rule: Left child is at 2k+1. Right child is at 2k+2. Parent is at (k-1)/2.
Array representation saves space (no pointers) but is terrible for skewed trees due to massive memory wastage.
2.0.0 Includes & Globals
// Implementation of tree using array
// numbering starting from 0 to n-1.
#include<bits/stdc++.h>
using namespace std;
char tree[10];
2.0.1 Root Init
int root(char key) {
if (tree[0] != '\0')
cout << "Tree already had root";
else
tree[0] = key;
return 0;
}
2.0.2 Set Left Child
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;
}
2.0.3 Set Right Child
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;
}
2.0.4 Main Driver
// 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;
}
2.0.5 Full Code
// 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] != '\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;
}
// 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;
}
Logical Breakdown
Click the ➔ arrow on any line to reveal the underlying logic here.