A tree is a data structure similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes. A tree is an example of non-linear data structures. A Tree structure is a way of representing the hierarchical nature of a structure in a graphical form.
In trees ADT(Abstract Datta Type), an order of the elements is not important. If we need ordering information linear data structures like linked lists, stacks, queues, etc. can be used.
Binary Tree
A tree is called a binary tree if each node has zero child, one child or two children. An empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right subtrees of the root.
Types of Binary Trees
- Strict Binary Tree: A binary tree is called a strict binary tree if each node has exactly two children or no children.
- Full Binary Tree: A binary tree is called a full binary tree if each node has exactly two children and all leaf nodes are at same level.
- Complete Binary Tree: Before defining the complete binary tree, let us assume that the height of the binary tree is h. In a complete binary tree, if we give numbering for the nodes by starting at the root then we get a complete sequence from 1 to a number of nodes in the tree. while traversing we should give numbering for NULL pointers also. A binary tree is called a complete binary tree if all leaf nodes are at height h or h-1 and also without any missing number in the sequence.
source: Data Structures and Algorithms Made Easy in Java ( By Narasimha Karumanchi )
