A binary tree is a hierarchal data structure in which each node has at most two children. The child nodes are called the left child and the right child.
To start with, let’s describe the linked list representation of a binary tree in which each node has three fields:
- Pointer to store the address of the left child
- Data element
- Pointer to store the address of the right child
Let’s see an example of a binary tree:
Types of Binary Trees
4.1. Full Binary Tree
A binary tree is said to be a full binary tree when each internal node has zero or two children:
4.2. Perfect Binary Tree
A perfect binary tree is a special type of binary tree in which all the leaf nodes are at the same level, and each internal node has two children:
4.3. Complete Binary TreeA binary tree is referred to as a complete binary tree when all of its levels are completely filled. The only exception is possibly the lowest level in which the nodes must lean as left as possible:
4.4. Degenerate or Pathological
Tree A degenerate or pathological tree is a type of binary tree in which each internal node has a single child, either the left child or the right child:
4.5. Skewed Binary Tree
A binary tree is said to be a skewed binary tree if all of its internal nodes have exactly one child, and either left children or right children dominate the tree. In particular, there exist two types of skewed binary trees: left-skewed binary tree and the right-skewed binary tree:
4.6. Balanced Binary Tree
A balanced binary tree is also a special type of binary tree in which the difference of height between the left and the right subtrees for each node is at most one:
5. Applications
There are many other data structures that are derived from the idea of a binary tree, such as binary search tree, syntax tree, heap, hash tree, red-black tree, binary trie, AVL tree, GGM tree, T-tree, and Treap.
Other real-life applications of a binary tree include binary space partition, heap sort, Huffman coding, virtual memory management, and indexing.
No comments:
Post a Comment