Home | | **Programming and Data Structure II** | Binary Tree ADT: Implementation, Types, Application, Comparison

A binary tree is a tree in which no node can have more than two children. The maximum degree of any node is two. This means the degree of a binary tree is either zero or one or two.

__Binary
Tree ADT__

A binary
tree is a tree in which no node can have more than two children. The maximum
degree of any node is two. This means the degree of a binary tree is either
zero or one or two.

In the
above fig., the binary tree consists of a root and two sub trees T_{l}
& T_{r.} All nodes to the left of the binary tree are referred as
left subtrees and all nodes to the right of a binary tree are referred to as
right subtrees.

__Implementation__

A binary
tree has at most two children; we can keep direct pointers to them. The
declaration of tree nodes is similar in structure to that for doubly linked
lists, in that a node is a structure consisting of the *key* information plus two pointers (*left* and *right*) to other
nodes.

**Binary Tree node declaration**

typedef
struct tree_node *tree_ptr; struct tree_node

{

element_type
element;

tree_ptr
left; tree_ptr right; };

typedef
tree_ptr TREE;

__Types of Binary Tree__

**i.
****Strictly
binary tree**

Strictly binary tree is a binary tree where all the nodes will have
either zero or two children. It does not have one child in any node.

**ii.** **Skew
tree**

A skew tree is a binary tree in which every node except the leaf has
only one child node. There are two types of skew tree, they are left skewed
binary tree and right skewed binary tree.

**Left skewed binary tree**

A left skew tree has node with only the left child. It is a binary tree
with only left subtrees.

**Right skewed binary tree**

A right skew tree has node with only the right child. It is a binary
tree with only right subtrees.

**iii.
****Full
binary tree or proper binary tree**

A binary
tree is a full binary tree if all leaves are at the same level and every non
leaf node has exactly two children and it should contain maximum possible
number of nodes in all levels. A full binary tree of height h has **2 ^{h+1}**

iv. **Complete
binary tree**

Every non
leaf node has exactly two children but all leaves are not necessary at the same
level. A complete binary tree is one where all levels have the maximum number
of nodes except the last level. The last level elements should be filled from
left to right.

**v.
****Almost complete
binary tree**

An almost complete binary tree is a tree in which
each node that has a right child also has a left child. Having a left child
does not require a node to have a right child.

**Comparison between General Tree and Binary Tree**

**General Tree**

1.
General tree has any number of children.

2.
Evaluating any expression is difficult in general trees.

**Binary Tree **

1. A
binary tree has not more than two children

2.
Evaluation of expression is easy in binary tree.

__Application of trees__

i.
Manipulation of arithmetic expression

ii.
Symbol table construction

iii.
Syntax Analysis

iv.
Grammar

v.
Expression Tree

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Advanced Non-Linear Data Structures : Binary Tree ADT: Implementation, Types, Application, Comparison |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.