|
Haven't you ever
realised how our operating system quietly manages our files? Why do we
have a hierarchical file system? How our files get saved under
hierarchical directories? Well, answer to all that is Trees!
Tree is a data structure which allows you
to associate a parent-child relationship between various pieces of data
and thus allows us to arrange our records, data and files in a
hierarchical fashion.
Assume a Tree representing your family
structure. Let say we start with your Grand parent; then come to your
parent and finally, you and your siblings. Refer this Tree below to
understand better.
 |
As you can see, the top
most element is called the "root". The nodes with
no children are called "Leaf" nodes. Here, if I
say "D" is representing you then "E" becomes
your sibling; "B" becomes your parent; "A"
becomes your ancestor (grand parent) and "C" is sibling
of your parent. If I call A as the root then B onwards is one sub
tree and C onwards is another. A sub-tree can have zero or more
sub-trees in it. |
| Every tree
has a depth and height factor associated. These factors are
associated with every node in the tree. The depth of a particular
node tells you how many generations down, that node is from the
Root. Similarly, height of a particular node tells you its
distance from the deepest leaf (or leaves) in that branch (or sub
tree). For example - D and E are at height = 0; C is at height =
0; and A is at height = 2. The height of a Tree is nothing but the
height of its root. Both of these factors have their own
importance at times.
Any Tree whose nodes can have at
the most two children is called a Binary tree or a tree with order
2. I'll stress on this only, as unlike trees with higher orders,
this has got a definite analysis.
Every node in a Binary tree has a
structure like this -
Struct NODE
{
struct NODE *leftchild;
Int nodevalue;
/*this can be of any
type*/
struct NODE *rightchild;
}
...and it looks like this -
 |
As you can see, 'leftchild'
and 'rightchild' are pointers to another tree-node. The
"leafnode" will have NULL values for these
pointers. |
Note:-
Although there are trees
with more than two children, I have covered mostly the concepts in
Trees which concern a Binary tree only.
|
Related Operations:
Trees – concepts
Binary tree and its creation
Traversals of a binary tree – preorder, inorder and postorder
Binary threaded tree
Non-recursive implementation of traversals
Expressions-to-Trees
Balanced trees / AVL trees – Creation and Balancing of a binary tree
Balanced m-way tree / B-tree – Creation and balancing
|
|
