A binary Tree is a special type of generic tree in which, each node can have at most two children. Binary tree is generally partitioned into three disjoint subsets, i.e. the root of the node, left sub-tree and Right binary sub-tree.
Binary Tree Traversal:
1)preorder
Visit root, visit left subtree in preorder, visit right subtree in preorder
2)postorder
Visit left subtree in postorder, right subtree in postorder, then the root
3)Inorder
Visit left subtree in inorder, then the root, then the right subtree in inorder
Example:
typedef struct node-tag {
item-type info ;
struct node-tag * left ;
struct node-tag * right ;
} node-type ;
node-type * root ; /* pointer to root */
node-type * p ; /* temporary pointer */
void preorder(node-type * root)
{
if (root) {
visit (root) ;
preorder (root $ \rightarrow$ left) ;
preorder (root $ \rightarrow$ right) ;
}
}
void inorder (node-type * root)
{
if (root) {
inorder (root $ \rightarrow$ left) ;
visit (root) ;
inorder (root $ \rightarrow$ right) ;
}
}
void postorder (node-type * root)
{
if (root) {
postorder (root $ \rightarrow$ left) ;
postorder (root $ \rightarrow$ right) ;
visit (root) ;
}
}
Applications:
▪︎Huffman's algorithm is implemented using a forest (disjoint collection of trees), each of which has its leaves labeled by characters whose codes we desire to select and whose roots are labeled by the sum of the probabilities of all the leaf labels. We call this sum the weight of the tree.
▪︎Initially each character is in a one-node tree by itself and when the algorithm ends, there will be only one tree, with all the characters as its leaves. In this final tree, the path from the root to any leaf represents the code for the label of that leaf.
