Share your knowledge at the LQ Wiki.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org representation of binary tree using array
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 10-06-2005, 07:23 PM #1 sajith Member   Registered: Sep 2005 Location: kannur Posts: 59 Rep: representation of binary tree using array hai sir i have to know how to represent a binary tree using array in c++ using OOP concepts how to repesents binary tree please help me sir..
 10-06-2005, 07:58 PM #2 paulsm4 LQ Guru   Registered: Mar 2004 Distribution: SusE 8.2 Posts: 5,863 Blog Entries: 1 Rep: Sounds like a homework assignment. Sounds like a homework assignment. Suggestion: 1. Try to get as far as you can with the problem. 2. Post some code (or even pseudo code) to let us know you made some minimal effort 3. Ask a specific question about exactly where you're "stuck". We'd be happy to help!
 10-06-2005, 08:35 PM #3 sajith Member   Registered: Sep 2005 Location: kannur Posts: 59 Original Poster Rep: binary tree hai sir the algothrim for binary tree using array is create(node I,item) { if(I!=0) { a[I]=item optiony/n) node I has left subtree if(option=y) create(2*I,nextitem) else create(0,NULL) optiony/n) node I has right subtree if(option=y) create(2*I+1,nextitem) else create(0,NULL) } } please tell me how to code this using C++
10-06-2005, 10:59 PM   #4
paulsm4
LQ Guru

Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep:
OK, here's a copy of my homework assignment on what I suspect is a similar (the same?) topic from a couple of years ago:
Quote:
 Binary searching B-tree blocks for keys is an important for DBMS systems. The keys are arrays, and are contiguous in the B-tree block. Lower performance systems, e.g., Oracle, store the keys as arrays of bytes. Higher performance DBMS systems, e.g. MKF, store the keys as arrays of longwords: When comparing the target key against a key in the B-tree block, you must do 4 times as many compares when the keys are arrays of bytes compared to the case when the keys are arrays of longwords. Therefore, in this exercise the keys are arrays of longwords. (The most significant longword is first.) In a B-tree block, a key is the value of the key column(s) followed by an address pointer. The address pointer points to a lower level B-tree block, or to a row in a data block. In this exercise as in MKF, the key arrays are fixed length. When you search for a target key, you may or may not find it. If you find it, you need to find the first duplicate, if there are duplicates. If you don't find it, you need the index of the point at which you should insert the target key (after first shifting all the keys from that point onward up by one key position). Write a binary search routine to search a B-tree block for a target key that satisfies the following signature: FN_uint32_t binary_search( FN_uint32_t *a, FN_int32_t n, FN_int32_t key_lw, FN_uint32_t *target_p, FN_int32_t *index_p); The array a[] holds the keys. key[i] starts at a[i * key_lw]. The index of the first key is 0 (and it starts at a[0]), and the index of the last key is n - 1 (and it starts at a[(n-1) * key_lw]). n >= 0. The key_lw parameter is the number of longwords in a key. 1 <= key_lw <= 4. The target_p parameter points to the first longword of the target key. If the key is found, 1 is returned, else 0. If the key is found, *index_p is set to the index of the first key in the array that has a value identical to the target key (i.e., duplicate keys are allowed in the array). If the key is not found, *index_p is set to the insertion point (i.e., the index of the key minimally greater than the target key), or, if the target key is greater than all the keys in the array a[], *index_p is set to 'n'. Your goal is to write a the fastest B-tree key search routine in the world. That is, no one can write a faster routine. The key_lw parameter is the number of longwords (unsigned 32 bit integers) per key. This value can range from one to four. Your routine should work for any n >= 0. Put the binary_search routine in the attached file called "binsearch.c". Do not create your own file. Edit the attached file.
I suppose I could post my solution, verbatim.

1. What exactly does your "create()" function do?
2. Where exactly does the "option" parameter come from?
... and ...
3. "a[]" is an array of exactly what?
(or, to put it differently: "what exacty is the definition of 'item'?"

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post zero79 Programming 1 09-01-2005 10:19 AM zero79 Linux - Software 1 08-29-2005 09:30 PM niteshadw Programming 1 08-25-2005 09:03 AM ksgill Programming 6 02-12-2004 05:11 PM JMC Programming 5 09-26-2003 11:02 AM

LinuxQuestions.org

All times are GMT -5. The time now is 06:16 PM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -