What is a Binary Tree
A tree is a data structure made up of nodes or vertices and edges without having any cycle. A linear list is a type of tree. A tree consists of a root node and many additional nodes that form a hierarchy.
In a binary tree each node is connected to two more node (called as left and the right node) and the data is stored in a sorted manner such that lookup, addition and removal of items more efficiently.
On an average in each comparison the other half of the tree is not operated on and therefore the time taken is proportional to the logarithm of the number of items stored in the tree which is much better than the linear method but slower than the correspinding operations on hash tables
Common terms used in tree are:
root node : The top nose in a tree
leaf : A node with no children
parent : A node directly connected to a node when moving towards root node
child : A node directly connected to another node when moving away from root node
Degree : The number of subtrees of a node
Edge : The connection between one node and another.
Path : A sequence of nodes and edges connecting a node with a descendant
Level : The level of a node is defined by 1 + (the number of connections between the node and the root).
Height of node : The nuber of edges on the longest path between the node and a leaf.
Height of tree : height of root node
Depth : The number of edges from the tree's root node to the node
How to insert elements in a Binary Search Tree
Each element is compared first to the root node isf it is greater than root value than it goes left else it goes right. The same process is now repeated on the next node until a leaf node is found. The element is then stored in leaf node which now becomes parent and gets two leaf nodes.
Traversal is a method of accessing the nodes of the tree. There are basically two types of traversals:
1. Breadth First Search(BFS)
It is also called Level Order search in this traversal each level of the tree is accessed one by one. It starts with the root node first and than accessing all its neighbours before moving on to next level.
2. Depth First search(DFS)
In DFS we go in depth of one node , this again is classified into 3 types:
a. Preorder Traversal :
In this traversal first the left node is accesed than the root and than the right node is accessed.
b. Inorder Traversal
In this traversal first the left node is accesed than the root and than the right node is accessed.
The output of inorder traversal is always sorted.
c. Postorder Traversal
In this traversal first the left node is accessed than the right and than the root node is accessed.
A tree is a data structure made up of nodes or vertices and edges without having any cycle. A linear list is a type of tree. A tree consists of a root node and many additional nodes that form a hierarchy.
In a binary tree each node is connected to two more node (called as left and the right node) and the data is stored in a sorted manner such that lookup, addition and removal of items more efficiently.
On an average in each comparison the other half of the tree is not operated on and therefore the time taken is proportional to the logarithm of the number of items stored in the tree which is much better than the linear method but slower than the correspinding operations on hash tables
Common terms used in tree are:
root node : The top nose in a tree
leaf : A node with no children
parent : A node directly connected to a node when moving towards root node
child : A node directly connected to another node when moving away from root node
Degree : The number of subtrees of a node
Edge : The connection between one node and another.
Path : A sequence of nodes and edges connecting a node with a descendant
Level : The level of a node is defined by 1 + (the number of connections between the node and the root).
Height of node : The nuber of edges on the longest path between the node and a leaf.
Height of tree : height of root node
Depth : The number of edges from the tree's root node to the node
How to insert elements in a Binary Search Tree
Each element is compared first to the root node isf it is greater than root value than it goes left else it goes right. The same process is now repeated on the next node until a leaf node is found. The element is then stored in leaf node which now becomes parent and gets two leaf nodes.
Traversal
Traversal is a method of accessing the nodes of the tree. There are basically two types of traversals:
1. Breadth First Search(BFS)
It is also called Level Order search in this traversal each level of the tree is accessed one by one. It starts with the root node first and than accessing all its neighbours before moving on to next level.
2. Depth First search(DFS)
In DFS we go in depth of one node , this again is classified into 3 types:
a. Preorder Traversal :
In this traversal first the left node is accesed than the root and than the right node is accessed.
b. Inorder Traversal
In this traversal first the left node is accesed than the root and than the right node is accessed.
The output of inorder traversal is always sorted.
In this traversal first the left node is accessed than the right and than the root node is accessed.
No comments:
Post a Comment