tree c tutorial
Tree – a Hierarchical Data Structure:
Trees are a non-linear data structure that can be represented in a hierarchical manner.
A tree contains a finite non-empty set of elements.
Any two nodes in the tree are connected with a relationship of parent-child.
Every individual element in a tree can have any number of sub trees.
Tree c tutorial – Terminology:
Root: The basic node of all nodes in the tree. All operations on the tree are performed by passing root node to the functions.( A – is the root node in above example.)
Child: A successor node connected to a node is called a child. A node in the binary tree may have at most two children. (B and C are child nodes to the node A, Like that D and E are child nodes to the node B)
Parent: A node is said to be parent node to all its child nodes. ( A is parent node to B, C and B is parent node to the nodes D and F).
Leaf: A node that has no child nodes.
( D, E, and F are Leaf nodes )
Siblings: Two nodes are siblings if they are children to the same parent node.
Ancestor: A node which is the parent of the parent node ( A is ancestor node to D, E and F ).
Descendant: A node which is child of child node ( D, E, and F are descendant nodes of node A )
Level: The distance of a node from the root node, The root is at level – 0,( B and C are at Level 1 and D, E, F have Level 2 ( highest level of tree is called height of tree )
Degree: The number of nodes connected to a particular parent node.
Subtree: A subtree is a set of nodes and edges
comprised of a parent and all the descendants
of that parent.
Height: The height of a tree is equal to the
maximum level of any node in the tree
tree c tutorial
tree c tutorial an important feature of a tree is that there is a single unique path from the root to any particular node.
The length of the longest path from the root to any node is known as the depth of the tree.
The root is at level 0 and the level of any node in the tree is one more than the level of its parent.
In a tree, any node can be considered to be a root of the tree formed by considering only the descendants of that node. Such a tree is called the subtree that itself is a tree.
Representation of binary tree:
Tree Nodes are stored in a linear data structure like an array.
Root node is stored at index ‘0’
If a node is at a location ‘i’, then its left child is located at 2 * i + 1 and right child is located at 2 * i + 2
This storage is efficient when it is a complete binary tree because a lot of memory is wasted.