Introduction to Trees [Data Structure]
——————————————————-
A tree is a finite set of one or more nodes
There is a specially designated node called the root
Remaining nodes are partitioned into n>=0 disjoint sets T1,…..Tn, where each of these sets is a tree.
The sets T1,…. Tn are called subtrees of the root.
Terminologies in Tree
———————————-
The degree of a node is defined as the number of subtrees of that node.
Nodes that have degree zero are called leaf or terminal nodes.
The other nodes are referred to as non-terminals.
The nodes, which are subtrees of some other node, are called children of that node.
The node, which contains subtrees, are called the parent.
Children of the same parent are said to be siblings.
The degree of a tree is the maximum of degree of the nodes of the tree.
The level of a node is defined by initially letting the root be at level one.
The height or depth of a tree is defined to be the maximum level of any node in that tree.
Application of Trees
——————————-
Trees can be implemented in following applications
Implementing the file systems of several operating systems.
Evaluation of Arithmetic expressions.
Set Representations.
Efficient sorting.
Reduction of the time complexity of some searching operations.
Operations and traversal on trees
—————————————————-
Basically, binary tree traversal can be carried out in 3 ways.
- Inorder
- Preorder
- Postorder
Inorder: In this method of traversal, first the left sub tree is traversed (visited), then the root and finally traversing the right sub tree.
Preorder: In this method, the root is traversed first, then the left sub tree and finally visiting the right sub tree.
Postorder:In this method, left sub tree is traversed first, then right sub tree and finally visiting the root.
Binary Trees
————————–
A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left and right subtrees.
Types of Binary Trees
————————————-
There are two special kinds of binary trees.
- Skewed tree
- Complete Binary tree.
Binary Search Trees
————————————–
A Binary Search Tree is a binary tree. It may be empty. If it is not empty, then it satisfies the following properties.
Every element has a key and no two elements have the same key (i.e., the keys are distinct).
The keys (if any) in the left sub tree are smaller than the key in the root.
The keys (if any) in the right sub tree are greater than the key in the root.
The left and right sub trees are also binary search trees.
Operations on Binary Search Tree
————————————————
Searching a Binary Search Tree
Insertion Into a Binary Search Tree
Deletion from a Binary Search Tree
