Graphs

Graphs

• Representation
  • Adjacency Matrix
  • Adjacency Lists
• Traversal schemes
  • DFS (Depth First Search)
  • Breadth First Search (BFS)
• Minimal Spanning
• Kruskal
• Prim

Queues

• Queues
  • Introduction
  • Representation
  • Operations
  • Implementation
    • Simple queue
    • With front always at zero
    • Linked queue
    • Dequeue
    • Priority Queues
      • Max Priority
      • Min Priority

Queues

Recursion

Recursion

A function call is said to be recursive, if we invoke a function from within the same function.  The phenomenon being referred to as recursion.  A termination condition must be specified with each recursive call to avoid infinite execution of that function.  Recursion is basically required whenever a function has to operate upon different set of values to obtain the result.

Evaluation of Infix expression

Application of Stacks

Evaluation of Infix expression

An infix expression is evaluated using two stacks, one for operator and another for operands.  The infix sting is read in an array, from which symbols/characters are fetched one by one and the following checks are performed:

Conversion from Prefix to Infix

Application of Stacks

Conversion from Prefix to Infix

The algorithm for converting a Prefix expression to an Infix notation is as follows:

• Accept a prefix string from the user.
• Start scanning the string from right one character at a time.
• If it is an operand, push it in stack.
• If it is an operator, pop opnd1, opnd2 and concatenate them in the order (opnd1, optr, opnd2) as follows:

Conversion from Prefix to Postfix

Application of Stacks

Conversion from Prefix to Postfix

The algorithm for converting a Prefix expression to a Postfix notation is as follows:

• Accept a prefix string from the user.
• Start scanning the string from right one character at a time.
• If it is an operand, push it in stack.
• If it is an operator, pop opnd1, opnd2 and concatenate them in the order (opnd1, opnd2, optr) as follows:

Conversion from Postfix to Infix

Application of Stacks

Conversion from Postfix to Infix

The algorithm for converting a Postfix expression to Infix notation is as follows:

•  Accept a postfix string from the user.
• Start scanning the string from left to right one character at a time.
• If it is an operand, push it in stack.
• If it is an operator, pop opnd2, opnd1 and concatenate them in the order (opnd1, optr, opnd2) as follows:

Conversion from Postfix to Prefix

Application of Stacks

Conversion from Postfix to Prefix

The algorithm for converting a Postfix expression to Prefix notation is as follows:

•  Accept a postfix string from the user.
• Start scanning the string from left to right one character at a time.
• If it is an operand, push it in stack.
• If it is an operator, pop opnd2, opnd1 and concatenate them in the order (optr, opnd1, opnd2) as follows:

Conversion from Infix to Prefix

Application of Stacks

Conversion from Infix to Prefix

The algorithm for converting an Infix expression to Prefix is as follows:

An Infix expression is converted into Prefix using two stacks, one for operator and another for operands.  The infix sting is read in an array, from which symbols/characters are fetched one by one and the following checks are performed:

Conversion from Infix to Postfix

Application of Stacks

Conversion from Infix to Postfix

The algorithm for converting an Infix expression to Postfix is as follows:

An Infix expression is converted into Postfix using two stacks, one for operator and another for operands.  The infix sting is read in an array, from which symbols/characters are fetched one by one and the following checks are performed:

Evaluation of Prefix expression

Application of Stacks

Evaluation of Prefix expression

The algorithm for evaluating a prefix expression is as follows:

• Accept a prefix string from the user.

say (-*+ABCD), let A=4, B=3, C=2, D=5

i.e. (-*+4325) is the input prefix string.

Evaluation of Postfix expression

Application of Stacks

Evaluation of Postfix expression

The algorithm for evaluating a postfix expression is as follows:

• Accept a postfix string from the user.

say (ABCD*+-), let A=4, B=3, C=2, D=5

i.e. (4325*+-) is the input postfix string.

Parenthesis checker

Application of Stacks

Parenthesis checker

It is an algorithm that confirms that the number of closing parenthesis equals opening parenthesis by using stack.  If number of closing parenthesis is not equal to the number of opening parenthesis, then it results in an error.  Input a string from the user.  The user must enter a set of opening and closing parenthesis as follows:

Polish Notations

Polish Notations

In the early 1920s, a Polish logician, Jan Lukasiewicz invented a special notation for prepositional logic that allows to eliminate all parenthesis from formulas.  The notation is called Polish Notation, which results in a less readable expression.  Depending upon the arrangement of operators and operands in an expression, Polish notation may be classified as:

• Infix Polish Notation
• Prefix Polish Notation
• Postfix Polish Notation

Infix Polish Notation:  In this notation, the operator comes between two operands.  For example: A+B, where A, B are operands and + is an operator.

Prefix Polish Notation:  In this notation, the operator comes before two operands.  For example: +AB.

Postfix Polish Notation:  In this notation, the operator comes after two operands.  For example: AB+.

Application of Stacks:

1. Parenthesis checker
2. Evaluation of Postfix expression
3. Evaluation of Prefix expression
4. Evaluation of Infix expression
5. Conversion from Infix to Postfix
6. Conversion from Infix to Prefix
7. Conversion from Postfix to Prefix
8. Conversion from Postfix to Infix
9. Conversion from Prefix to Postfix
10. Conversion from Prefix to Infix

Program to implement Stack using Linked List

Stacks

Program to implement Stack using Linked List:

Trees

Trees

Definitions:

Binary Tree:  A binary tree is either empty or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root.

Threaded Binary Trees

Threaded Binary Trees

Threaded Binary Trees are an improvement over Binary Search Trees that uses stack for iterative traversal.  If a strategy is introduced such that the leaf node of a binary search tree points to its inorder predecessor or its successor, then direct links (called threads) are obtained to traverse a tree without using stack, which basically stores and retrieves the address of nodes in LIFO manner.  If the left pointer of the leaf node points to its inorder predecessor, then such a threaded tree is called Left-In-Threaded Binary Tree.  If the right pointer of the leaf node points to its inorder successor, then such a threaded tree is referred to as Right-In-Threaded Binary Tree. However, if both the links, left as well as right are available, then the threaded tree is called In-Threaded Binary Tree.

Program to implement Left-In- And Right-InThreaded Binary Tree

Left-In-Threaded Binary Tree

Program to implement Left-In-Threaded Binary Tree:

Program to implement various operations on a Binary Search Tree

Binary Search Tree:

Program to implement various operations on Binary Search Tree:

Binary Search Tree

Binary Search Tree

A Binary Search Tree is a Binary Tree which satisfies the following conditions:

1. The left subtree of the root contains keys smaller than the root.
2. The right subtree of the root contains keys greater than the root.
3. The left and right subtrees are also Binary Search Trees.
4. There are no duplicates in the tree.