Session 5-Tree & Binary Tree

Subtopic:
-Binary Tree Termology
-Advantages of Tree
-Binary Search Tree
-Threaded Binary Tree

Binary Tree Termology

• The depth of a node is the number of edges from the root to the node.
• The height of a node is the number of edges from the node to the deepest leaf.
• The height of a tree is a height of the root.
• A full binary tree.is a binary tree in which each node has exactly zero or two children.
• A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

A complete binary tree is very special tree, it provides the best possible ratio between the number of nodes and the height. The height h of a complete binary tree with N nodes is at most O(log N).

Advantages of Tree

Trees are so useful and frequently used, because they have some very serious advantages:

• Trees reflect structural relationships in the data
• Trees are used to represent hierarchies
• Trees provide an efficient insertion and searching
• Trees are very flexible data, allowing to move subtrees around with minumum effort

Binary Search Tree

We consider a particular kind of a binary tree called a Binary Search Tree (BST). The basic idea behind this data structure is to have such a storing repository that provides the efficient way of data sorting, searching and retriving.

Insertion

The insertion procedure is quite similar to searching. We start at the root and recursively go down the tree searching for a location in a BST to insert a new node. If the element to be inserted is already in the tree, we are done (we do not insert duplicates). The new node will always replace a NULL reference.

Searching
Searching in a BST always starts at the root. We compare a data stored at the root with the key we are searching for (let us call it as toSearch). If the node does not contain the key we proceed either to the left or right child depending upon comparison. If the result of comparison is negative we go to the left child, otherwise - to the right child. The recursive structure of a BST yields a recursive algorithm.

Deletion
Deletion is somewhat more tricky than insertion. There are several cases to consider. A node to be deleted (let us call it as toDelete)

• is not in a tree;
• is a leaf;
• has only one child;
• has two children.

If toDelete is not in the tree, there is nothing to delete. If toDelete node has only one child the procedure of deletion is identical to deleting a node from a linked list - we just bypass that node being deleted

Deletion of an internal node with two children is less straightforward. If we delete such a node, we split a tree into two subtrees and therefore, some children of the internal node won't be accessible after deletion. In the picture below we delete 8:

Threaded Binary Tree
A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.   

• We have the pointers reference the next node in an inorder traversal; called threads
• We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer

Types of threaded binary trees:

• Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right) means all right null pointers will point to inorder successor OR all left null pointers will point to inorder predecessor.
• Double Threaded: each node is threaded towards both the in-order predecessor and successor (left and right) means all right null pointers will point to inorder successor AND all left null pointers will point to inorder predecessor.

Session 4-Introduction to Tree, Binary Tree And Expression Tree

Subtopic:
-Tree Concept
-Binary Tree Concept
-Type of Binary Tree
-Property of Binary Tree
-Representation of Binary Tree
-Expression Tree Concept
-Prefix, Postfix, and Infix Traversal

Tree Concept

Degree of Tree = 3

Degree of C = 2

Height = 3

Parent of C = A

Children of A = B, C, D

Sibling of F = G

Ancestor of F = A, C

Descendant of C = F, G


Binary Tree Concept
is a rooted tree data structure in which each node has at  most two children.

Rooted = 18

Leaves = 9, 12 ,10, and 23

Type of Binary Tree

Perfect Binary Tree

is a binary tree which every level are at the same depth.

Complete Binary Tree

is binary tree in which every level, except possibly the last, is completely filled, and all nodes far as possible

Skewed

is a binary tree in which each node has at most one child

Property of Binary Tree 

is a binary tree in which no leaf is much father away from the root

-Explanation for  the Example Property of Binary Tree

Maximum nodes of a binary tree of height 3

= 1 + 2 + 4 + 8

= 20 + 21 + 22 + 23

= 24 – 1

= 15

Representation of Binary Tree

-Using Array

Ex:

Index on array represents node number

Index 0 is Root node

Index Left Child is 2p + 1, where p is parent index

Index Right Child is 2p + 2

Index Parent is (p-1)/2

-Using Linked List
Ex:

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

Expression Tree Concept

Ex:





Prefix             : *+ab/-cde

Postfix            : ab+cd-e/*

Wrong Inflix   : a+b*c-d/e

Correct Inflix  : (a+b)*((c-d/e)





Prefix, Postfix, and Inflix Traversal

Prefix Traversal Ex:

void prefix(struct tnode *curr) {

  printf( “%c “, curr->chr );

  if ( curr->left  != 0 ) prefix(curr->left);

  if ( curr->right != 0 ) prefix(curr->right);
}

Postfix Traversal Ex:

void postfix(struct tnode *curr) {

  if ( curr->left  != 0 ) postfix(curr->left);

  if ( curr->right != 0 ) postfix(curr->right);
  printf( “%c“, curr->chr );

}

Inflix Traversal Ex:

void infix(struct tnode *curr) {

  if ( curr->left  != 0 ) infix(curr->left);

  printf( “%c“, curr->chr );

  if ( curr->right != 0 ) infix(curr->right);
}

Session 3-Linked List Implementation II-2101727190-Fedrick

Subtopic:
- Stack Concept
- Inflix, postfix and prefix notation
- Depth First Search
- Queue Concept
- Breadth First Search

Stack Concept
is an important data structure which stores its elements in an ordered maner.
In stack concept, the data are stored in Last In First Out way.

Stack Operation
- push(x) : add an item x to the top of the stack.
- pop()    : remove an item from the top of the stack.
- top()     : reveal/return the top item from the stack.
//top = peek.

Stack Applications
There are 4 applications of stack we will discuss:
- Infix
- Postfix
- Prefix
- Depth first search

Inflix, Postfix, and Prefix Notation
- Prefix notation = Reverse Polish notation
- Inflix notation (commonly used)
- Postfix notation = Polish notation

Prefix   : operator is written before operands
Infix     : operator is written betwen operands
Postfix : operator is written after operands
//We recommend to use Prefix and Postfix because much easier for computer to evaluate.

Example - Infix.
4 + 8 * (4+1) / 5
4 + 8 * 5 / 5
4 + 40 / 5
4 + 8
12

Example - Postfix
String                   Stack
4 6 5 2 - * 3 / +           
4 6 5 2 - * 3 / +    4            push 4
4 6 5 2 - * 3 / +    4 6         push 6
4 6 5 2 - * 3 / +    4 6 5      push 5
4 6 5 2 - * 3 / +    4 6 5 2   push 2
4 6 5 2 - * 3 / +    4 6 3      pop 2, pop 5, push 5-2
4 6 5 2 - * 3 / +    4 18       pop 3, pop 6, push 6*3
4 6 5 2 - * 3 / +    4 18 3    push 3
4 6 5 2 - * 3 / +    4 6         pop 3, pop 18, push 18/3
4 6 5 2 - * 3 / +    10          pop 6, pop 4, push 10 -> the result

Example - Prefix
+ 7 - x 6 5 ^ 3 2
+ 7 - x 6 5 ^ 3 2
+ 7 - x 6 5 9
+ 7 - x 6 5 9
+ 7 - 30 9
+ 7 - 30 9
+ 7 21
+ 7 21
28

Depth First Search
Depth First Search is an algorithm we can use for traversing or searching in tree or graph.

in this search, data with last index will be poped firstly.

Queue Concepts
is an important data structure which stores its elements in an ordered maner.
In queue concept, the data are stored in First In First Out way.

Same with stack concepts but in queue top = front.
Queue Operation
- push(x) : add an item x to the top of the stack.
- pop()    : remove an item from the top of the stack.
- front()     : reveal/return the top item from the stack.
//front = peek.

now what happen if we push MAXN times and pop MAXN times?

we cant push another data into the queue, so we can use Circular Queue.

Circular Queue

if R reach MAXN then set R as zero, do the same to L.

Queue Applications
There are 3 applications of queue we will discuss:
- Deques
- Priority Queues
- Breadth First Search

Deques
is a list in which elements can be inserted or deleted at either end.

Priority Queue
is an abstract data type in which the each element is assigned a priority.

Breadth First Search
same like DFS is also an algorithm for traversing or searching in a tree or graph but pop data in the smaller index first.

in this search data with front index will be poped firstly.

Session 2-Linked List Implementation-2101727190-Fedrick

Linked list divided to 6 subtopic:
• Single Linked List
• Polynomial Representation
• Circular Single Linked List
• Double Linked List
• Circular Doubly Linked List
• Header Linked List

Single Linked List
use to create a list, we first need to define a node structure for the list.

Ex:

struct nodes{
    int  value;
    struct nodes *next;
};

struct nodes *head = 0; //head = pointer to the first element in our linked list.

How to insert a new value?
first we should dynamically allocate a new node and assign the value to it and then connect it with the existing linked list.

Ex:

struct tnode *node =

  (struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = head;

head = node;

Now How to delete a value that we add before?

first we should find the location of node which store the value we want to delete, remove it, and connect the remaining 

linked list.

Ex:

struct tnode *curr = head;

// if x is in head node

if ( head->value == x ) {

  head = head->next;

  free(curr);
}

// if x is in tail node

else if(tail->value == x){

  while(curr->next!=tail) curr = curr->next;

  free(tail); tail = curr;

  tail->next = NULL;

}

// if x is not in head node, find the location

else {

  while ( curr->next->value != x ) curr = curr->next;

  struct tnode *del = curr->next;

  curr->next = del->next;

  free(del);

}

Polynomial Representation
A polynomial is an expression that contains more than two terms. A term is made up of coefficient and  exponent. An example of polynomial is P(x) =  4x^3+6x^2+7x+9
Detail:
Input:

 1st number = 5x^2 + 4x^1 + 2x^0
     2nd number = 5x^1 + 5x^0
Output:
        5x^2 + 9x^1 + 7x^0
Input:
     1st number = 5x^3 + 4x^2 + 2x^0
     2nd number = 5x^1 + 5x^0
Output:
        5x^3 + 4x^2 + 5x^1 + 7x^0

Circular Single Linked List

• In circular, last node contains a pointer to the first node

• We can have a circular singly linked list as well as a circular doubly linked list.

• There is no storing of NULL values in the list

Double Linked List

is a linked list data structure with two link, one that contain reference to the next data and one that contain reference to 

the previous data.

Ex:

struct nodes {

  int value;

  struct nodes *next;

  struct nodes *prev;

};

•

struct nodes *head = 0;

struct nodes *tail = 0;

How to insert new value?

Just like in a single linked list, first we should allocate the new node and assign the value to it, and then we connect the 

node with the existing linked list.

Ex:

struct tnode *node =

  (struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

Now How to delete the new value?

There are 4 conditions we should pay attention when deleting:

•The node to be deleted is the only node in linked list.

•The node to be deleted is head.

•The node to be deleted is tail.

•The node to be deleted is not head or tail.

1.  If the node to be deleted is the only node

•  free(head);

•  head = NULL;

•  tail   = NULL;

2.If the node to be deleted is head:

•  head = head->next;

•  free(head->prev);

•  head->prev = NULL;

3.If the node to be deleted is tail:

•  tail = tail->prev;

•  free(tail->next);

•  tail->next = NULL;

4.If the node to be deleted is not in head or tail:

Ex:

  struct tnode *curr = head;

  while ( curr->next->value != x ) curr = curr->next;

  struct tnode *a   = curr;

  struct tnode *del = curr->next;

  struct tnode *b   = curr->next->next;

  a->next = b;

  b->prev = a;

  free(del);

Circular Double Linked List

It is similar with circular single linked list, but total pointer in each node here is 2 (two) pointers.

Header Linked List
aheader linked list is linked list that always contain a special note at the front of the list, this special
node is called headednote.

 Linked List devide into 2 types:

1 .Grounded Header list is the header list where the last node contains the null pointer. Grounded comes from the fact that many text use the electrical ground symbol to indicate the null pointer.

• Location Of first node is written as:

        PTR->LINK(HEAD)

        Where as in singly linked list we write it as PTR->HEAD

• Condition to check empty header linked list:

2. Circular header list is a header list where the last more points back to the header node .the term node by itself normally refer to an ordinary node not  the header node, when used with header list. Thus the first node in header is the node following the header node and the list.

• location of the first node is:
  • Location Of first node is written as:
            PTR->LINK(HEAD)
  • Condition to check empty Circular header linked list:
            LINK(HEAD)=HEAD.

Session 1-Pointer, Array and Introduction to Data Structure-2101727190-Fedrick

Hi everybody, today i will explain 4 topic about data structure, first of all i will explain about:

Array
Array is a collection of data of same types stored in sequential memory location. It is a linear data structure, where data is stored sequentially one after the other. The elements in an array is accessed using an index. For example, In an array of n elements, the first element has index zeroand the last element has index (n-1). Elements with consecutive index (i.e. i and i+1) are stored in consecutive memory location in the system.

Array can be divided into following types:

1. One Dimensional Array

example:

• int var [10]; (declaration)

• var [2] = 12; (adding value)

so, the value on row -> 3 = 12

(why row 3? because array always start from 0)

2. Multi Dimensional Array

example 2 dimensional array:

• int var [10] [10]; (declares an integer array with 10 elements)

• var [2] [4] = 14; (accessing an integer array with 14 value)

so, the value on coloum -> 3 and row -> 5 = 14

array have more than 2 dimension, and all of them working like the examples on the top.

There are a number of operations that can be performed on arrays.

They are:

• Traversal

• Insertion

• Searching

• Deletion

• Merging

• Sorting

Pointer

C++ pointers are easy and fun to learn. Some C++ tasks are performed more easily with pointers, and other C++ tasks, such as dynamic memory allocation, cannot be performed without them.

As you know every variable is a memory location and every memory location has its address defined which can be accessed using ampersand (&) operator which denotes an address in memory. Consider the following which will print the address of the variables defined −

The two most important operators used with pointer type are:

• &  (the address operator)

• *   (the dereferencing operator)

example:

If we have the declaration:

  int test;

  int *ptest;

then test is an integer and ptest is a pointer to an integer. If we say:

  ptest  = &test;

then &test returns the address of x and assigns it as the value of ptest.

To assign a value of x we can say

  x = 10;

or

  *ptest = 10;

Data Structure

Data structures are used to store data in a computer in an organized form. In C language Different types of data structures are; Array, Stack, Queue, Linked List, Binary Tree, Hash Tables.

• Array: Array is collection of similar data type, you can insert and deleted element form array without follow any order.
• Stack: Stack work on the basis of Last-In-First-Out (LIFO). Last entered element removed first.

• Queue: Queue work on the basis of First-In-First-Out (FIFO). First entered element removed first.

• Linked List: Linked list is the collection of node, Here you can insert and delete data in any order.

• Binary Tree: Stores data in a non linear form with one root node and sub nodes.

• Hash Tables: Stores data in tables form.

Data Type
A data type defines what kind of value a column can hold: integer data, character data, monetary data, date and time data, binary strings, and so on.

example of predefined data types are:
• Int : (4), (6), (9)
• Char : (A), (D), (C)
• Float : (1,35), (3,567546)

•Abstract Data Type (ADT)

is a data type that is organized in such a way that the specification of the objects and the

specification of the operations on the objects is separated from the representation of the 

objects and the implementation of the operations.

Question

1. How many dimension in array (max).

2. What is the different between single pointer and double pointer.

3. How many pointer we can use (max).

Answer

1. maximum dimension we can use in array are 256 dimension.

2. Printed addresses become slightly different, when new line starts. If I use static array,

addresses are exactly the same, and array elements are going one after another.

Presumably, you're talking about a static array of arrays and compare it to the array of

pointers that you have.

Elements of an array are allocated continuously in memory. In the case of array of static

arrays, the elements of the outer array are static arrays and they are stored continuously in

memory. In the case of array of pointers, the elements of the outer array are the pointers

and they are also stored continuously in memory. The arrays of int that you allocate

dynamically on the other hand are not stored in the outer array. Where they're stored is

implementation defined and typically not related to the location of the array which holds the

pointers.

Extension.

Why we need to use Double Pointer?

If you want to have a list of characters (a word), you can use char *word

If you want a list of words (a sentence), you can use char **sentence

If you want a list of sentences (a monologue), you can use char ***monologue

If you want a list of monologues (a biography), you can use char ****biography

If you want a list of biographies (a bio-library), you can use char *****biolibrary

       etc.

3.Its depend by your computer, how far your computer can process it.

Thats all thank you :)