3/15/2012

Data structures and algorithms (Binary Tree)

If you order your cheap term paper from our custom writing service you will receive a perfectly written assignment on Data structures and algorithms (Binary Tree). What we need from you is to provide us with your detailed paper instructions for our experienced writers to follow all of your specific writing requirements. Specify your order details, state the exact number of pages required and our custom writing professionals will deliver the best quality Data structures and algorithms (Binary Tree) paper right on time.

Out staff of freelance writers includes over 120 experts proficient in Data structures and algorithms (Binary Tree), therefore you can rest assured that your assignment will be handled by only top rated specialists. Order your Data structures and algorithms (Binary Tree) paper at affordable prices with LivePaperHelp.com!



Data structures and algorithms


A major area of the computer is the storage of data for efficient search and retrieval, the main memory of a computer is linear consisting of a sequence of memory cells that are numbered 0,1,,… in order. However one of the simplest forms of data structure is the one-dimensional or linear array accessed by using the element numbers. Data items such as a list of names are usually stored in arrays and efficient methods are sought to handle the data. If the list is long it would be an advantage to sort the list in-order to greatly reduce the time the user spends waiting for the retrieval of the search criteria compared to a search on an unsorted list.


Several structures exist for the storage of data within the computers memory as listed above a one-dimensional array, two-dimensional array, stacks, queue (circular), linked lists, doubly linked lists, binary tree and heaps are just a few techniques in which algorithms have been based on the speed in which data is searched and stored in the computers memory.


A heap is a saturated binary tree structure; the two branches of each node lead to nodes with lower numerical values.


Do my essay on Data structures and algorithms (Binary Tree) CHEAP !

essay writing service



In the example below, the items in the heap are numbers, and the heap is maintained with larger numbers floating to the top. Each item is a member of an array, and we make use of array numbers in order to deal quickly and effectively with the heap.


A heap works on the principle that items are interrelated item n in the heap is a larger number than item n and item n+1. When all the items are in this relationship you have a valid heap, each item is like a stone resting firmly on two under it.





Using weights could help use balance the tree for each specific item the calculation for each item in the tree will be its weight times its level number with the root being at level one.


The binary tree is used for the basis of this assignment has the methods for searching and storage is more efficient than the one-dimensional array. Pointers are used to link together the memory addresses (A pointer is a variable that hols the memory address) bellow is a schematic representation were each location is equal to One byte.





Declared variable called of type unsigned integer (age).


10110101 01110110 11110110 11101110


100 101 10 10 104 105 106 107 108 10 110 111 11 11 114 115 116 117 118 11


The unsigned integer age = 4bytes = bits


The following C# shows the key word struct which identifies the beginning of a structure definition and must be followed by the structure name, or tag.


Fig 1


Struct tree {


Char f_name ;


Int age;


}


within the braces following the structure name is a list of the structure member variables.


Fig


Struct tree {


Char f_name;


Int age;


} Tree_Node;


The example in fig shows that I have declared an instance of the tree structure


The data structure below is the first part of the assignment, which sets up a structure called carreg.


typedef struct carreg


{


char reg_num[7+1];


char Surname[5+1];


char Forename[0+1];


char Age_of_Owner[+1];


char Make[0+1];


char Model[15+1];


char Colour[15+1];


char cubic_capacity[5+1];


struct carreg next; // pointer (link) to the next node


int counter;


}list_entry;


To enable us to manipulate the structure members the following notation is used (-); this sign is used as shown in fig.


Fig





Cout list_entry-reg_num; print(display on screen) the reg_num.


The following source code has been commented, to show what is happening within the procedure.


//Assignment 1 - Andrew Trot man


//Attempt at a binary tree structure


#include stdio.h


#include conio.h


#include iostream.h


#include stdlib.h


#include string.h


#includeiomanip.h


typedef struct carreg


{


char reg_num[7+1];


char Surname[5+1];


char Forename[0+1];


char Age_of_Owner[+1];


char Make[0+1];


char Model[15+1];


char Colour[15+1];


char cubic_capacity[5+1];


struct carreg next; // pointer (link) to the next node


int counter;


}list_entry;


struct carreg start=NULL; //pointer to first entry


struct carreg last=NULL; //pointer to last entry


struct carreg previous=NULL; //pointer to a previous item


struct carreg find(char );


void display_by_Reg(struct carreg ,int);


void display_all(int);


int enterdata(int);


void Error();


int menu_select(void);


void remove(struct carreg ,struct carreg );


void Storeage(struct carreg ,struct carreg ,struct carreg );


void show_all(struct carreg ,int);


void view_by_Reg_list(int);


void search(struct carreg ,struct carreg );


int global_counter;


/////////////////////////////////////////////////////////////////////////////


void main(void)


{


int count =1;


for(;;)//menu loop


{


switch(menu_select())


{


case 1 enterdata(count);


count++;


global_counter=count;


break;


case remove(&start,&last);





global_counter--;


break;


case view_by_Reg_list(global_counter);


break;


case 4search(&start,&last);


break;


case 5display_all(global_counter);


break;


case 6exit(0);


default


clrscr();cout Incorect Entry ;





}


clrscr();


}


}


////////////////////////////////////////////////////////////////////////////////


void display_by_Reg(struct carreg info , int file_count)


{


for(file_count; file_count = 0;file_count--)


printf( ---------------------------------------------------------------

);


printf(%s| %-0s |%-0s

, Entry No. , Reg_Num , Index );


printf( ---------------------------------------------------------------



a);


printf( %d | %-0s | %-0d

,info-counter,info-reg_num,file_count );


if(file_count =0)


{


cout Press a key ;


getch();


}


}


////////////////////////////////////////////////////////////////////////////////


int enterdata(int fred)


{





struct carreginfo;


/////////////////////////////////////////////////


//to-do test for duplicate registration.


/////////////////////////////////////////////////


info=(struct carreg )new list_entry;//allocate memory (dynamic)


cout FileNumber = fred

;


cout Is File number correct Please Enter Number to confirm.;


cin info-counter ;


if(info-counter !=fred)


{


Error();


//return to the menu if incorrect entry is encountered


//TO-Do reset the value sent to fred from main !!!


return 0;


}


else


{


clrscr();


cout PLEASE DO NOT ENTER Pre-Fixs (Q,O,Z)



aa;


cout Please Enter Regn No. ; cin info-reg_num ;cout

;


find(info-reg_num );


if(!(info || info 0))


{


Error();


}


//To Do trap for duplicates at this point......


}


cout Enter the owners age ;


cin info-Age_of_Owner ;


cout Enter Owners Surname ;


cin info-Surname ;


cout Enter Forename ;


cin info-Forename ;


cout Enter Vehicle Make ;


cin info-Make;


cout Enter Vehicle Model ;


cin info-Model;


cout Enter Colour of Vehicle ;


cin info-Colour;





// Enter the rest of the Struct here !!


Storeage(info,&start,&last);//store the data in memory


return 0;


} // end of function enterdata


////////////////////////////////////////////////////////////////////////////////


struct carreg find(char name)


{


struct carreg info;


info=start;


previous=NULL;


while(info)


{


if(strcmp(name,info-reg_num)==0)return info;


else


{


previous=info;


info=info-next;//get next


}


}


cout Registration not found endl;


return NULL;


}


////////////////////////////////////////////////////////////////////////////////


int menu_select(void)


{


textbackground(BLUE); // change the color of the background and


textcolor(WHITE); // change the textcolor to white


clrscr(); // clear the screen and set the color.


char key[1];


int c;


gotoxy(1,4);cout Welcome to the car registration Assignment.

;


gotoxy(16,6);cout 1. Add data.

;


gotoxy(16,8);cout . Delete data.

;


gotoxy(16,10);cout . Show Search criteria.

;


gotoxy(16,1);cout 4. Search.

;


gotoxy(16,14);cout 5. Display all

;


gotoxy(16,16);cout 6. Exit program.



;


//the size of the structure is determined by the key word Sizeof(crreg) or


//list_entry....... can be used.


cout

Size of Struct is sizeof(carreg) Bytes

;


do


{


gotoxy(16,0);cout

Enter your choice ;


key[0]=getch();//get choice


c=atoi(key);//converts string to int


clrscr();//clear the screen


}


while (c0 || c6);//loop until valid selection


return c;//return menu choice


}


////////////////////////////////////////////////////////////////////////////////


void remove(struct carreg start, struct carreg last)


{


struct carreg info, find(char);


char tempreg[10];


cout Enter Registration ;


cin tempreg;


info=find(tempreg);


if(info)


{


if(start==info)//if its the first item


{


start=info-next;//index start point


if(start) previous=NULL;


else last=NULL;


}


else


{


previous-next=info-next;


last=previous;


}


delete info;//deallocate memory


}


}


////////////////////////////////////////////////////////////////////////////////


void Storeage(struct carreg i,struct carreg start, struct carreg last)


{


struct carreg old,p; //Local scope


p=start;


if(!last )//if its the first element


{


i-next=NULL;


last=i;


start=i;


}


old=NULL;


while(p)


{


if(strcmp(p-reg_num,i-reg_num)0)//Sort in assending order.


{


old=p;


p=p-next;


}


else


{


if(old)


{


old-next=i;


i-next=p;


return;


}


i-next=p;//new first element


start=i;


return;


}


}


(last)-next=i;//put on end


i-next=NULL;


last=i;


}


////////////////////////////////////////////////////////////////////////////////


void view_by_Reg_list(int counter_one)//display the registration entries.


{


struct carreg info;


counter_one = 1;


info=start;


if (start)//check if the list is not empty


{


while(info)


{


display_by_Reg(info,counter_one++);


info=info-next;//gets the next address


}


}


else


cout The list is empty.;


getch();


}


////////////////////////////////////////////////////////////////////////////////


void search(struct carreg start, struct carreg last)


{


clrscr();


gotoxy(1,);cout Search Function



;


struct carreg info, find(char);


char tempreg[10]; //create a temporary variable to


cout Enter Registration ;


cin tempreg;


info=find(tempreg);


if (info== NULL)


{


cout

; //information not found


}


else cout Search Information found info-reg_num




Is at this address &info-reg_num ;


getch();


}


////////////////////////////////////////////////////////////////////////////////


void display_all(int counter_one)//display the whole lot......


{


struct carreg info;


counter_one = 1;


info=start;


if (start)//check if the list is not empty


{


while(info)


{


show_all(info,counter_one++);


info=info-next;//gets the next address


}


}


else


cout The list is empty.;


getch();


}


////////////////////////////////////////////////////////////////////////////////


void show_all(struct carreg info,int file_count)


{


for(file_count; file_count = 0;file_count--)


gotoxy(1,);cout Record number


info-counter Stored At Address


&info-reg_num



;


gotoxy(,);cout Customer name Registration Number


setw(10) Make & Model setw(10) Colour



;


cout info-Forename info-Surname setw(0) info-reg_num


setw() info-Make info-Model setw() info-Colour





;


cout Owners age is info-Age_of_Owner ;


gotoxy(10,0);cout Press Any key to continue ;


getch();


clrscr();


if(file_count =0)


{


; //execute empty statement block.


}


}


////////////////////////////////////////////////////////////////////////////////


void Error()


{


clrscr();


gotoxy(,10);


cout Error the file number entered is not in sequence.



You can still continue to enter data but you

will not be able to have access to the currnt error.





Press Any key to Return to menu.;


getch();


}


////////////////////////////////////////////////////////////////////////////////


The above source code is essentially a doubly linked list and demonstrates the search, add and delete methods these are clearly shown as described in the following examples on testing the program.


Testing





On selecting option 1 “Add data.” You are prompted for conformation of the record number if this entry is incorrect the program displays the following error message.


The message informs the user that the entry made is not in a sequence and gives its reasons.


Once a key is pressed the user is back to the main menu.


To do.


The function controlling this routine is not fully functional and requires a little more work to reset the values when returning to the entering of data.


Option will not operate until data has been entered into the tree.


PLEASE SEE NEXT PAGE


Option shows the data in-order with the entry points to the left and the sorted on the right as shown bellow





Option To Delete 5E5RT from the tree enter the registration number to delete that object from memory then to test it display the contents by pressing option . Shown bellow





Option 4Search.


On clearing the screen you enter the search function this function prompts the user to enter the search key(Registration number); on entering the registration number the following screen dump is displayed





Option 5 Display all


The following display is shown to the user one record at a time until the entries have been exhausted. They are also displayed in ascending order.





Option 6 closes the program.


Typical application


Where a binary tree data structure may be found.


A binary tree is an appropriate data structure when a large number of items need to be held in such a way that any item may be quickly accessed or a sequenced list is required. Additions can be easily handled since this requires only the adjustment of a single pointer. There are three methods in which the tree can be displayed they are as follows -


1. In-Order traversal.


. Pre-Order traversal.


. Post-Order traversal.


The following examples are shown bellow.


1. void inOrder (TreeNode treePtr) //recursive function


{


if(treePtr != NULL)


{


inOrder (treePtr-leftPtr);


printf (%d, treePtr-registration_number);


inOrder (treePtr-rightPtr);


}


}


. void preOrder (TreeNode treePtr) //recursive function


{


if (treePtr != NULL)


{


printf(%d, treePtr-registration_number);


preOrder (treePtr-leftPtr);


preOrder (treePtr-rightPtr);


}


}


. void postOrder (TreeNode treePtr) // recursive function


{


if (treePtr!= NULL)


{


postOrder (treePtr-leftPtr);


postOrder (treePtr-rightPtr);


printf(%d, treePtr-registration_number);


}


}


Such applications a RDBMS(relational database management system) would be a suitable candidate to store a large amount of data in a structure type manner(object).


For something a little less demanding the tree structure can be used to hold a file directory on a backing store so that any file can be quickly located.


The following source code demonstrates the use of a binary tree with the data randomly generated and duplicates removed.


#include stdio.h // used for printf


#include stdlib.h // required for rand()


#include conio.h


struct treeNode{


struct treeNode leftPtr;


char registration_number;


//enter the rest of the


//customer information here.


struct treeNode rightPtr;


};


typedef struct treeNode TREENODE;


typedef TREENODE TreeNode;


void insertNode (TreeNode , int);


void inOrder (TreeNode);


void preOrder (TreeNode);


void postOrder (TreeNode);


int main(void)


{


int i, item;


TreeNode rootPtr = NULL;


//generate a random set of numbers to test the traversal methods used below


printf(The numbers being placed in the tree are

);


for (i = 1; i=0; i++) {


item = rand() % 50;


printf (%d, item);


insertNode (&rootPtr, item);


}


//call the following traversal functions


printf(



The preorder traversal is



);


preOrder (rootPtr);


printf(



The inorder traverasl is



);


inOrder (rootPtr);


printf(



The postorder traversal is



);


postOrder(rootPtr);


getch();


return 0; }


void insertNode (TreeNode treePtr, int value)


{


if (treePtr == NULL)


{


treePtr =new (TREENODE); //dynamic memory allocation


if (treePtr != NULL)


{


(treePtr)-registration_number = value;


(treePtr)-leftPtr = NULL;


(treePtr)-rightPtr = NULL;


}


else


printf (%d. No memory available.

, value);


} //go left


else


if(value (treePtr)-registration_number)


insertNode(&((treePtr)-leftPtr), value);


else // go right


if(value (treePtr)-registration_number)


insertNode (&((treePtr)-rightPtr), value);


else


printf( duplicate ); //Catch duplicate values


}


void inOrder (TreeNode treePtr) //recursive function


{


if(treePtr != NULL)


{


inOrder (treePtr-leftPtr);


printf (%d, treePtr-registration_number);


inOrder (treePtr-rightPtr);


}


}


void preOrder (TreeNode treePtr) //recursive function


{


if (treePtr != NULL)


{


printf(%d, treePtr-registration_number);


preOrder (treePtr-leftPtr);


preOrder (treePtr-rightPtr);


}


}


void postOrder (TreeNode treePtr) // recursive function


{


if (treePtr!= NULL)


{


postOrder (treePtr-leftPtr);


postOrder (treePtr-rightPtr);


printf(%d, treePtr-registration_number);


}


}


THE SOURCE CODE IS ON THE DISK FOR YOUR VIEWING.


Recursion.


The routines within this document to produce the desired output of traversing the tree use recursion, this means that it creates a tempory instance of itself or calls itself until the desired result is met.


Constructing a binary tree.


Addition.


As we construct a binary tree there are lots of considerations to make. The final shape of the tree including its depth (and therefore its efficiency for searching) is pretty much dependent on the order in which we add items to the growing tree. The following example using the standard rules, entering the data in the order YTRT, B50RTR, N88LOP, A5RTT, S4TGB, M887MFP this will produce a valid (and workable) binary tree- but after the 6th entry it will already be four levels deep.








Depending on the order in which you add items to a growing binary tree, you can end up with structures with more levels of depth than necessary. In fact, we could have known we would be in trouble when we find the root entry in the tree is YTRT. So close to the end of the alphabet the ideal root entry will be the one that does not waste its comparison, sending half of the possible searches one way and half the other. One way to do this is to balance the tree structure and this procedure is difficult to maintain particularly when deleting the root node.


However by using heaps instead of adding an item by dropping downward to a node and locating an appropriate empty spot we can add the item by writing it at the root. This however will displace the item already at the root, and to maintain the “heap property” we may have to do a little quick surgery to the rest of the tree.


An alternative method for adding an item to the binary tree proceeds as follows -


1. Put the item at the root, making necessary adjustments to the left and right nodes.


. Calculate the efficiency impact the sum of weight times level for each entry in the tree


. Start with the root node as ‘Current node’


4. Rotate the items at the current node, so that the immediate left branch item and right branch item become temporarily, the root item; make heap corrections so that these trial rotations remain valid binary trees


5. Calculate the efficiency impact on each trial rotation


6. If a rotation produces a score better than before, you have gained efficiency. Adopt the changes permanently, move attention (the current node) one upward towards the root, and resume at step 4.


7. If no rotation produces a better score, start with the newly added item’s node as ‘current’, and resume step 4.


8. At each stage, keep track of the lowest score, which represents the most efficient tree up to that point.


The end.





Please note that this sample paper on Data structures and algorithms (Binary Tree) is for your review only. In order to eliminate any of the plagiarism issues, it is highly recommended that you do not use it for you own writing purposes. In case you experience difficulties with writing a well structured and accurately composed paper on Data structures and algorithms (Binary Tree), we are here to assist you. Your cheap custom college papers on Data structures and algorithms (Binary Tree) will be written from scratch, so you do not have to worry about its originality.

Order your authentic assignment from LivePaperHelp.com and you will be amazed at how easy it is to complete a quality custom paper within the shortest time possible!



0 comments:

Post a Comment

 
Copyright 2009 Samples of Thesis Essays
essays-thesis.blogspot.com contains free examples of essays on the best essay topics and disciplines.