LinuxQuestions.org
Did you know LQ has a Linux Hardware Compatibility List?
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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

Reply
 
Search this Thread
Old 10-06-2005, 07:23 PM   #1
sajith
Member
 
Registered: Sep 2005
Location: kannur
Posts: 59

Rep: Reputation: 15
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..
 
Old 10-06-2005, 07:58 PM   #2
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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!
 
Old 10-06-2005, 08:35 PM   #3
sajith
Member
 
Registered: Sep 2005
Location: kannur
Posts: 59

Original Poster
Rep: Reputation: 15
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++
 
Old 10-06-2005, 10:59 PM   #4
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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.

But instead, let me ask these questions:

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'?"

Thanx in advance .. PSM
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to convert a float to its binary or hex representation in Python? zero79 Programming 1 09-01-2005 10:19 AM
How to convert a float to its binary or hex representation in Python? zero79 Linux - Software 1 08-29-2005 09:30 PM
binary seach; vector instead of an array niteshadw Programming 1 08-25-2005 09:03 AM
Binary search tree insertion in java ksgill Programming 6 02-12-2004 05:11 PM
Printing a binary tree in c? JMC Programming 5 09-26-2003 11:02 AM


All times are GMT -5. The time now is 09:11 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration