Binary Tree

Binary TREE

A tree is a non linear data structure in which items are arranged in a sorted sequence.

Terminology

• A is the root node.

• B is the parent of D and E.

• C is the sibling of B

• D and E are the children of B.

• D, E, F, G, I are external nodes, or leaves.

• A, B, C, H are internal nodes.

• The depth (level) of E is 2

• The height of the tree is 3.

• The degree of node B is 2.

Binary Trees

• Ordered tree: the children of each node are ordered.

• Binary tree: ordered tree with all internal nodes of degree 2.

• Recursive definition of binary tree:

• A binary tree is either

– an external node (leaf), or

– an internal node (the root) and two binary trees (left subtree and right subtree)

TRAVERSING TREES

• preorder traversal

Algorithm preOrder(v)

“visit” node v

for each child w of v do

recursively perform preOrder(w)

eg. reading a document from beginning to end

• postorder traversal

Algorithm postOrder(v)

for each child w of v do

recursively perform postOrder(w)

“visit” node v

• inorder traversal

Algorithm inOrder(v)

recursively perform inOrder(leftChild(v))

“visit” node v

recursively perform inOrder(rightChild(v))

Polynomial Addition

Addition of Polynomial

In the linked representation of polynomials, each term is considered as a node. Each such node contains three fields:

• Coefficient field
• Exponent field
• Link field

STEPS

Two polynomials can be added and the steps to be followed are as follows:

1. Read the number of terms in the first polynomial, P
2. Read the coefficient and exponents of the first polynomial
3. Read the number of terms in the second polynomial, Q
4. Read the coefficients and exponents of the second polynomial
   1. Set the temporary pointers p and q to traverse the two polynomials respectively
5. compare the exponents of two polynomials starting from the first nodes.
   1. i.      If both exponents are equal then add the coefficients and store it in the resultant linked list
   2. ii.      If the exponent of the current term in first polynomial P is less than the exponent of the current term of the second polynomial is added to the resultant linked list and move the pointer q to point to the next node in the second polynomial Q
   3. iii.      If the exponent of the current term in first polynomial P is greater than the exponent of the current term of the second polynomial Q, then the current term of the first polynomial is added to the resultant linked list and move the pointer p to point to the next node
   4. iv.      Append the remaining nodes of either of the polynomials to the resultant linked list.

Linked List Variations

Variations in LINKED LISTS

Types of linked lists

• Singly linked list

It is one in which all nodes are linked together in some sequential manner. It has got the single beginning and a single end.

• Doubly linked list

In it all nodes are linked together by multiple links which help in accessing both the successor node and the predecessor node for any arbitrary node within the list.

• Circular linked list

In it there is no beginning and no end. It is prepared by sorting the address of very first node in the link field of the last node.

ü    The circular list can be made circular by simply putting the link between the last node and the first node.

ü    Sometimes in the representation of the circular linked list a node representing the last node is also added.

ü    It is to be noted the arrows here are representing the link between the several nodes used here.

• Circular doubly linked list

In it both the successor and the predecessor pointers are pointed in the circular manner.

Linked List Operations

Operations on LINKED LIST

Linked lists are dynamic data structures, which can grow or shrink during the execution of a program.

Operations:

The basic operations to be performed on the linked lists are as follows:

• Creation This operation is used to create a linked list. Here the constituent node is created as and when it is required and linked to the list to preserve the integrity of the list.

• Insertion This is used to insert a new node in the linked list at a specified position

1. At beginning
2. At end
3. At specified location
4. If list is empty, then at the end

• Deletion This is used to delete a node from

1. Beginning
2. End
3. Specified location

• Traversing It is a process of appending (joining) the second list to the end of the first list consisting of m nodes.

• Display This operation is used to print each and every node’s information.

Queue Variations

QUEUE VARIATIONS

Circular QUEUE

A circular queue is one in which the insertion of a new element is done at the very first location of the queue if the last location of the queue is full.

• The position of element to be inserted is calculated as :

rear = (rear + 1) % maxsize

queue[rear] = value .

• The new position after every deletion should be :

front = (front + 1) % maxsize

DOUBLE ENDED QUEUES  (DEQUEUE)

It is a homogenous list of elements in which insertion and deletion operation are performed from both ends thus referred to be as dequeue.

There are two types of dequeues. These two types are due to restrictions put to perform either the insertions or deletions only at one end.

1. Input-restricted dequeue
2. Output-restricted dequeue

Priority Queue

It is a collection of elements such that each element has been assigned a priority and the order in which elements are deleted and processed comes from the following rules:

ü    An element of higher priority is processed first .

ü    Two element with same priority are processed according to the order in which they were added to the queue.

Multiple Queues

• We can maintain two queues in the same array which is possible if one grows from position1 of array and other grows from last position.
• There should be two front and two rear of the two queues.
• Both queues can grow up to any extent from position1 to maximum. Hence there must be check to keep track of total values stored.

Queue Algorithms

Queue Insertion Algorithm

Queue Deletion Algorithm

Using POINTERS

Adding a NODE

Deleting a NODE

Queue Operations

OPERATIONS  ON  QUEUE

• Queue is a non primitive linear data structure.
• It is an homogenous collection of elements in which new elements are added at one end called the REAR end and the existing elements are deleted from other end called the FRONT end.

Implementation of QUEUE

• Static implementation       (using arrays)
• Dynamic implementation  (using pointers)

Total Elements

Total elements present within a queue are :

front  –  rear  +  1

Operations on a Queue

Basic operations that can be performed on a queue are :

• To insert an element in a queue
• To delete an element from the queue

Binary Expression Tree

Binary Expression Tree

An expression tree is a strictly binary tree in which leaf nodes contain operands and non-leaf nodes contain operator, root nodes contain the operator that is applied to result of left and right sub trees.

The following figure shows an expression tree for above expression

2 * 3 / ( 2 – 1 ) + 5 * ( 4 – 1 )

Note : A binary expression tree does not contain parenthesis, the reason for this is that for evaluating an expression using expression tree, structure of tree itself decides order of the operations.

Multiple STACKS

• We can maintain two stacks in the same array which is possible if one grows from position 1 of the array and the other grows from the last position.
• Stack refers to the data structure where the elements are stored such that a new value is inserted as well as deleted from only one end called the top of the stack.

The structure for such implementation can be given below :

Struct multistack

{

int top0 , top1 ;

int  count  ;

int  num  ;

}  ;

Stack Algorithms

PUSH

POP

Applications  of  STACKS

1.     Stack Frames

2.     Reversing a string

3.     Calculation of Postfix Expression

4.     Notation   Conversions

Infix to Postfix conversion

Infix to Prefix conversion

Postfix form Evaluation

Stack Operations

Operations on Stack

A stack is a non primitive linear data structure. It is an ordered list in which addition of new data item and deletion of already existing data item is done from only one end, known as top of stack.

This is the reason the stack is also called Last in first out (LIFO) type of list.

Stack implementation

1. Static implementation           – It gets the use of arrays to create stack.

2. Dynamic implementation      – It is also called linked list representation and uses pointers to implement the stack type of data structure.

Operations on STACK

1. PUSH                     – The process of adding a new element to the top of stack.

2. POP                       – The process of deleting an element from the top of stack.

• In case no new element can be accommodated, it is called STACK-FULL condition.
• In case no element can be popped this results in the STACK-UNDERFLOW condition.