Trees: Unlike Arrays, Linked Lists, Stack, and queues, which are linear data structures, trees are hierarchical data structures.
Tree Vocabulary: The topmost node is called the root
of the tree. The elements that are directly under an element are called its
children. The element directly above something is called its parent. For
example, ‘a’ is a child of ‘f’, and ‘f’ is the parent of ‘a’. Finally, elements
with no children are called leaves.
tree
----
j
<-- root
/
\
f
k
/
\ \
An h
z <-- leaves
Why Trees?
1. One reason to use trees might be because you
want to store information that naturally forms a hierarchy. For example, the
file system on a computer:
file system
-----------
/
<-- root
/
\
... home
/
\
ugrad
course
/
/ | \
...
cs101 cs112 cs113
2. Trees
(with some ordering e.g., BST) provide moderate access/search (quicker than
Linked List and slower than arrays).
3. Trees provide moderate insertion/deletion
(quicker than Arrays and slower than Unordered Linked Lists).
4. Like Linked Lists and unlike Arrays, Trees
don’t have an upper limit on several nodes as nodes are linked using pointers.
Main applications of trees include:
1. Manipulate hierarchical data.
2. Make information easy to search (see tree
traversal).
3. Manipulate sorted lists of data.
4. As a workflow for compositing digital images
for visual effects.
5. Router algorithms
6. Form of multi-stage decision-making (see
business chess).
Binary Tree: A tree whose elements have at most 2
children is called a binary tree. Since each element in a binary tree can have
only 2 children, we typically name them the left and right children.
Binary Tree Representation in C: A tree is
represented by a pointer to the topmost node in the tree. If the tree is empty,
then the value of the root is NULL.
A Tree node contains the following parts.
1. Data
2. Pointer to left child
3. Pointer to the right child
In C, we can represent a tree node using structures. Below is an example of a
tree node with integer data.
|
struct node { int data; struct node* left; struct node* right; }; |
First Simple Tree in C
Let us create a simple tree with 4 nodes in C. The created tree would be as follows.
tree
----
1
<-- root
/
\
2
3
/
4
|
#include
<bits/stdc++.h> using namespace std; struct Node { int data; struct Node* left; struct Node* right; //
Val is the key or the value that //
has to be added to the data part Node(int value) { data
= val; //
Left and right child for node //
will be initialized to null left
= NULL; right
= NULL; } }; int main() { /*create
root*/ struct Node* root = new Node(1); /*
following is the tree after above statement 1 /
\ NULL
NULL */ root->left
= new Node(2); root->right
= new Node(3); /*
2 and 3 become left and right children of 1 1 /
\ 2
3 /
\ / \ NULL
NULL NULL NULL */ root->left->left
= new Node(4); /*
4 becomes left child of 2 1 /
\ 2
3 /
\ / \ 4
NULL NULL NULL /
\ NULL
NULL */ return 0; } |
Summary: A tree is a hierarchical data structure. The main
uses of trees include maintaining hierarchical data, providing moderate access,
and insert/delete operations. Binary trees are special cases of the tree where
every node has at most two children.