TREE (DATA STRUCTURE)

Binary tree: 

Depth-first

·                    Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right) 

·                    In-order traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right) 

·                    Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root) 

Breadth-first

·          

Implementations

Depth-first

In-order

inorder(node)

  if node == null then return

  inorder(node.left)

  visit(node)

  inorder(node.right)

iterativeInorder(node)

  parentStack = empty stack

  while not parentStack.isEmpty() or node != null

    if node != null then

      parentStack.push(node)

      node = node.left

    else

      node = parentStack.pop()

      visit(node)

      node = node.right

Pre-order

preorder(node)

  if node == null then return

  visit(node)

  preorder(node.left) 

  preorder(node.right)

iterativePreorder(node)

  parentStack = empty stack

  while not parentStack.isEmpty() or node != null

    if node != null then

      visit(node)

      parentStack.push(node.right)

      node = node.left

    else

      node = parentStack.pop()

Post-order

postorder(node)

  if node == null then return

  postorder(node.left)

  postorder(node.right)

  visit(node)

iterativePostorder(node)

 if node == null then return

 nodeStack.push(node)

 prevNode = null

 while not nodeStack.isEmpty()

   currNode = nodeStack.peek()

   if prevNode == null or prevNode.left == currNode or prevNode.right == currNode

     if currNode.left != null

       nodeStack.push(currNode.left)

     else if currNode.right != null

       nodeStack.push(currNode.right)

   else if currNode.left == prevNode

     if currNode.right != null

       nodeStack.push(currNode.right)

   else

     visit(currNode)

     nodeStack.pop()

   prevNode = currNode

C program (WELCOM)

write a program to scroll welcome on ur screen from one end to another end



#include<stdio.h>
#include<conio.h>
#include<dos.h>
  void main()
   {
   int x,y,i;
      x=20;
      y=10;
    while(!kbhit())
    {
    gotoxy(x,y);
    delay(200);
    printf("WELCOME");
    gotoxy(x,y);
    for(i=1;i<=7;i++)
       {
       printf(" ");
       }
       if(x<50)
       x=x+1;
       if(x==50)
       x==20;
       getch();
     }
      }

Pointers

Discuss concepts of pointer 

It is a memory reference which is used to store the address of another variable of samr type.if a pointer variable is integer type then it store the ddress of any another integer variable.

a) size of the space.
b) Name of the space.
c) contain of the space
d) type of the space
e) Address of the space

Type of pointer
1) pointer as a structure,
2) pointer as a structure member.
3) Array of a pointer.
4) string as a pointer.
5) void pointer.
6)chain pointer.

Array of a pointer

As we create the array of any primitive data type like float ,char, int etc.as we can creat the array of derieved data types.

Derived data type is the types that is created with the help of pre.basic data type like structure, pointer, array these data type derived the property(inhevent) of basic data type plus its own property.

Differences between arrays and linked list

LINKED LIST:-

1)    Can quickly insert and delete items in linked list.

2)     You simply rerrange those pointers that are affected by the change in linked list.

3)    Linked list are very difficulty to sort.

4)    Can not immediately locate the desires element.need to traverse the whole list to reach that element.

5)    Linked list are not constrained to be stored in adjacent locations.

6)    Basically 3 types are there :- singly,doubly,and circular.

7)    Linked list is a list whose order is given by links from one item to the next.

ARRAY:-

1)       Can not do so quickly as in linked list.

2)       Inserting and deleting items in an array requires you to either make room for new item or fill the hole left by deleting an item.

3)      They are not difficulty to sort.

4)      Easy to locate the desired element.

5)      The element of an array occupy contiguous memory locations.

6)      Basically two types are there :- one dimention, two dimention.

7)      An array is a group of related data items that share a common name.

The difference between arrays and linked lists are:

     Array

1-     Arrays are linear data structures.

2-     - Array has homogenous values. And each element is independent of each other positions

3-     - Array elements can not be added, deleted once it is declared.

4-     - Array elements can be modified easily by identifying the index value.

    

       Linked lists

 1-Linked lists are linear and non-linear data structures.

 2- It is a complex process for modifying the node in a linked list.
  The nodes in the linked list can be added and deleted from the list.    

3- Linked lists are linear for accessing, and non-linear for storing in memory. Each node in the linked list is connected with its previous node which is a pointer to the node.

Difference Between Array and Stucture

Array	Structure
i. Data Collection
Array is a collection of homogeneous data.	Stucture is a collection of heterogeneous data.
ii. Element Reference
Array elements are referred by subscript.	Structure elements are referred by its unique name.
iii. Access Method
Array elements are accessed by it's position or subscript.	Stucture elements are accessed by its object as '.' operator.
iv. Data type
Array is a derived data type.	Structure is user defined data type.
v. Syntax
<data_type> array_name[size];	struct struct_name {     structure element 1;     structure element 2;         ----------         ----------         structure element n; }struct_var_nm;

Difference Between Static Memory and Dynamic

STATIC MEMORY ALLOCATION	DYNAMIC MEMORY ALLOCATION
Memory is allocated before the execution of the program begins.	Memory is allocated during the execution of the program.
Implemented using stacks and heaps.	Implemented using data segments.
Pointer is needed to accessing variables.	No need of Dynamically allocated pointers.
Faster execution than Dynamic.	Slower execution than static.
More memory Space required.	Less Memory space required.