BinaryTree - Converting Array Binary Tree to a Linked List - I Can't figure out the algorithm...

My assignment:

"1.      Write a static function convertLink that receives a binary tree in sequential representation (Array SR and the index last) and returns the root of the tree in linked representation.

2.      Write a static function convertSequential that receives the root of a binary tree in linked representation  and returns the sequential representation of the tree (i.e. the array SR and the index last). The maximum size of the array SR may be computed by using another function computeLevel that computes the number of levels in the received tree.

Test the above two function as follows:
    1. Draw a random binary tree with at least 15 nodes
    2. Draw the sequential representation of the tree. So you have its array SR and
        its index last.
    3. Call the function convertLink for the sequential representation computed in  the previous step.
    4. Call the function convertSequential for the root computed in the previous step. You should obtain exactly the same sequential representation of step#2. "




my teacher is saying we don't even need to really implement a binary tree class... just the dummy node

so i have the node class something like

Class Node
{
Node Left
Node Right
char data
}

I'm having trouble with just the first function algorithm for "convertLink"........
say i have a binary tree that looks like this:

        A
      /    \
    B      C
   /  \     /  \
  D  E   F  G

the array i would receive as a parameter would contain

0 1 2 4 5 6 7
A B C D E F G

Arrayname = BTarray[]


This is where I’m stuck and am desperate for help……… I’m thinking I have to make an “insert” function??

Say in my convert-to-link function I have a for loop

Node root(‘A’);

For(int a=0, a<last index of array; a++)
{
Insert(root, BTarray[a])
}

Void Insert (Node node, char value)
{
If(node.left != NULL)
      Insert(node.left, a)
If(node.right != NULL)
      Insert(node.right, a)
If(both right and left != NULL)
     ?????????
}

So… that would give me:

        A
      /    \
    B      C

I’m really stuck here in that I don’t know how to make a function or algorithm that can reach the D, E, F, G etc………

The teacher went over the assignment real briefly in class and said this function is really really easy and everyone seemed to agree so I feel like I’m making this too complicated and I’m totally missing something??

Or if I’m not… how can I make the rest of my Insert function keep adding to the binary tree.. really desperate here.. due tomorrow

PS - I could be wrong in anything i wrote here... as in i could be writing my original sequential array completely wrong or something... i'm really lost so i'm open to anything.... maybe if i'm going about this completely wrong I can use some suggestions too
nocturn4lAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

phoffric\Commented:
What does SR mean?

There seems to be potentially a 1/2 dozen or more questions here. I would be more comfortable if you were to ask a new question with just one focused question providing at least two different inputs and the two expected outputs. In such a question, show your best attempt and identify what problem you are having.

Here is your class node modified for C++:
Class Node
{
Node * Left;
Node * Right;
char data;
};

You gave an example of a binary tree:
        A
      /    \
    B      C
   /  \     /  \
  D  E   F  G

What criteria are you using for building this particular tree. It does not appear to be in sort-order by char since E > C; and yet E is not shown as a right child of C.
phoffric\Commented:
Suppose your tree were:

        A
      /    \
    B      F
      \        \
       C       K
                /
              H

In this case, what would your input be?
phoffric\Commented:
BTW, if you do ask a related question, I recommend you close this question, and then hit the ask a related question so that others will be able to look back at what you have written; and not have to repeat what has already been said.
Introduction to Web Design

Develop a strong foundation and understanding of web design by learning HTML, CSS, and additional tools to help you develop your own website.

nocturn4lAuthor Commented:
Typing from my phone atm but SR is jus the name of the array, nothing significant

basically were supposed to (physically) draw a binary tree however I want, put the contents into an array in main (root = 0, left and rt child = 2i plus 1 and 2i pls 2) then implement the functions mentioned

Since we can draw the binary however we want.. I think you're right in that now I'm thinking I drew my binary tree in a way so that its not even possible to make an algorithm

If I do it in regards of "node>node" like you mentioned, wouldn't that be considered a binary search tree?

I duno if that's what he wants as we jus started covering that topic, but I don't see any other way you could make an algorithm otherwise, am I wrong in thinking this?
nocturn4lAuthor Commented:
The array would contain

0 1 2 3 4 5 6 7 8
A B F 0 C 0 K H 0

0 is null (sorry still on cell atm)
nocturn4lAuthor Commented:
Ill close this question once I get access to a PC but please keep this open for now as I believe the questions I'm asking are still pertaining to the subject
phoffric\Commented:
Your title refers to "Linked List", but there is no further mention of a "Linked List" in your question. Since a Linked List doesn't lend itself that well to a binary tree, I'm assuming that the title is in error. A Linked List has one child node pointer (and if doubly linked list, then there is also a parent node pointer). A binary tree using links will have two child node pointers as shown in http:#30759761.

SR is a Sequential Representation of a binary tree. And from your question, we don't care about how that tree was created or what kind of tree it represents (it may be an expression tree, a sort tree, but no matter). Given SR, a binary tree is well-defined from the contents.

My understanding is that you have two distinct conversion problems. Given an Array Binary Tree, convert it into a Linked Binary Tree; and given a Linked Binary Tree, convert it into an Array Binary Tree.

Note that in a Linked Binary Tree, any node represents a sub-tree; it itself is a Linked Binary Tree that is part of its parent. In other words, node A (root) can be a Linked Binary Tree (call it LBT) consisting of two LBT subtrees - the left and the right.

Class Node
{
Node * Left;
Node * Right;
char data;
} lbt;

lbt is not only a node; you can consider it as a model of a LBT.

Your job is to start figuring out the relationships between array elements and LBT nodes (forget programming - use pictures of arrays and trees).


phoffric\Commented:
Be back in a couple of hours. Are you allowed to use recursion?
I think it would be beneficial for the LBT to come up with a two coordinate representation of a node in the LBT.
nocturn4lAuthor Commented:
Yes we can use recursion, driving atm, won't have access to a comp for a few hrs neither, ty for your help
phoffric\Commented:
>> won't have access to a comp for a few hrs
OK, but I would draw pictures first. Consider both recursion and non-recursion. Consider fact that a node in a Linked Binary Tree is a sub-tree (i.e., it is a Linked Binary Tree in its own right). Show the (non-computer) relationships between the array and the binary tree.
nocturn4lAuthor Commented:
okay i'm on my laptop now

ah i didn't notice that i put linked list on the title...yea that was a typo... i did mean to put linked binary tree

i don't see the close question button though.. i see delete question?  do you think i should still close this subject due to the typo?  because i would like to reward points at the least for help on this subject...



i believe i have a decent understanding between the array and linked version of the binary tree?  or maybe not or else i wouldn't be having this problem...lol

i guess i'm just still confused...on what i'm misunderstanding or what i'm missing between the relationship of the picture of the binary tree and the array because i think i understand?

i guess like i stated above earlier... is the only way i could really code an algorithm for an insert for the convertLink function to make my original binarytree picture into a binarysorttree?

because otherwise i really don't see an algorithm on how to code it...
nocturn4lAuthor Commented:
at the moment i'm trying to figure out an algorithm using the fact that with the array each child is i*2+1 or 2... am i in the right direction at least?
phoffric\Commented:
>> do you think i should still close this subject due to the typo?
No, you don't have close because of that. I just brought it up to make sure that we were both on the same page about your assignment. But I wonder - is there an edit button where you can edit the question?

You don't have to close this thread if you want to keep to the design; i.e., the relationship between the array and linked representations of a binary tree.

>> to make my original binarytree picture into a binarysorttree
No, the tree you drew is fine. As I later mentioned, there is nothing in your OP that indicates that the binary tree is in any identifiable order. A binary tree needed be a sorted tree having a comparison operator; I mentioned, for example, that it could be an expression tree. The latter tree can be used to convert algebraic infix to prefix notation for example.

>> i have a decent understanding between the array and linked version of the binary tree?
Then converting from array to a LBT, if the input is an array of 50 elements, and you want to make a correspondence between array element 12, to the node in a LBT, how would you explain that? Can you do it qualitatively (i.e., a picture) as well as quantitatively (i.e., using indexes)?

When I mentioned closing this question, I was originally thinking that there were too many different parts. But since we're limiting this discussion to the binary tree conversion design, no need to close (unless you are making no progress in this thread). Once satisfied with the thread, you need to accept one or more appropriate posts for the knowledge-base; in that case, I don't believe you are closing, you are accepting.
phoffric\Commented:
I didn't see your 04/14/10 08:42 PM, ID: 30776331 post
My last response was to the previous post.

>> figure out an algorithm using the fact that with the array each child is i*2+1 or 2... am i in the right direction at least?
Probably, but tell me, what index are you using for the first element in the array - is it 0 or 1? (For the design, it can be either, but it needs to be specified. Then for the implementation, if using C++, we need to remember that the first array element has an index of 0.)
nocturn4lAuthor Commented:
i don't see anything where i can edit my OP topic anymore...  =T



"As I later mentioned, there is nothing in your OP that indicates that the binary tree is in any identifiable order."

correct

" A binary tree needed be a sorted tree having a comparison operator"

if i'm understanding you correctly, you're saying that a binary tree needs to have a comparison operator?

or are you saying if i do make a binary tree with a comparison operator that is called an expression tree?

i just want to make to make sure i'm understanding you correctly


"Then converting from array to a LBT, if the input is an array of 50 elements, and you want to make a correspondence between array element 12, to the node in a LBT, how would you explain that? Can you do it qualitatively (i.e., a picture) as well as quantitatively (i.e., using indexes)?"

ok i'll think bout that for now and i'll come back here...

i'm stressin out atm =[
nocturn4lAuthor Commented:
"Probably, but tell me, what index are you using for the first element in the array - is it 0 or 1? (For the design, it can be either, but it needs to be specified. Then for the implementation, if using C++, we need to remember that the first array element has an index of 0.)"

The first element starts with 0 (the root).  this is actually a Java class, I just put the C++ topic because i know it can be applied there with just different syntax (i'm familiar with both atm)
phoffric\Commented:
>> i just want to make to make sure i'm understanding you correctly
Good. It is not necessary that a binary tree have a comparison operator. If you wanted to save integers as the values in a binary tree, and if you wanted the smallest numbers to be to the left, then you use the default integer comparison operator. If you were storing names, and wanted the tree to have some alphabetical ordering, then the default operator in the C language could be strcmp(), or in C++, the < operator works on the C++ string library class.

Bottom line, since your OP says nothing about the nature about the tree, then I cannot make any assumptions about what the purpose of the tree is nor can I say that there is or is not a comparison operator associated with this tree. In any case, all you need is a mapping from a linear index to a drawing that looks like a 2D drawing. That is the challenge, to go from a 1D domain to a 2D domain for one conversion problem; and then from 2D domain to 1D domain for the reverse conversion.

>>i'm stressin out atm =[
Why, when is this due?

>> ok i'll think bout that for now and i'll come back here...
OK, I'll keep on the lookout. But you did say that you think you have "have a decent understanding between the array and linked version of the binary tree - lol" So, maybe before working on the little problem I gave you, why don't you try to describe in words what that understanding is. If the qualitative mapping from one domain to the other is reasonable, then you can try to quantify this understanding.
    - Also, I would like to read your understanding so that I'm on the same page as you.
phoffric\Commented:
After you think you have a clear design, you can accept this, and choose the language to implement this in. I know C++ pretty well but a little rusty in Java. I am guessing that if you can convert array --> LBT, then the inverse conversion LBT --> array will be easy for you. Having done that, it will be easy to do steps 3 and 4.

Drawing may be another related question after you get steps 3 and 4 working.
phoffric\Commented:
Check out "Ahnentafel list" in http://en.wikipedia.org/wiki/Binary_tree

Don't forget to let me know about "what index are you using for the first element in the array - is it 0 or 1?" Any formulations you use may assume one or the other. I certainly don't want to second guess you.
nocturn4lAuthor Commented:
project is due Friday.. but i have other stuff for other classes due too so i need to get this done asap and it just doesn't seem like it's going to happen......jus kinda scared to be honest cuz if i can't get this project done i might as well drop the class (last day to drop is monday).. but this is the last programming prerequisite class so i really hope i don't gotta do that.. anyway

"Then converting from array to a LBT, if the input is an array of 50 elements, and you want to make a correspondence between array element 12, to the node in a LBT, how would you explain that? Can you do it qualitatively (i.e., a picture) as well as quantitatively (i.e., using indexes)?"

okay quantitatively.... i understand that it's:

left child = 12*2 + 1 = 25
right child = 12*2 + 2 = 26
parent = 12/2 - 1 = 5

i'm not really sure what you want me to do with the picture though?
nocturn4lAuthor Commented:
"Don't forget to let me know about "what index are you using for the first element in the array - is it 0 or 1?" Any formulations you use may assume one or the other. I certainly don't want to second guess you."

first element of the array is 0, the root

i'm really just worried about step #1 to be honest.. i believe if i can get the other steps done fine if i can the array-->link done
nocturn4lAuthor Commented:
other than what i gave you.. i guess i really don't understand the correlation from the 1D-->2D or else i'd be able to come up with the algorithm... atm im staring at a binary tree picture trying to figure this all out
nocturn4lAuthor Commented:
hmmm the Ahnentafel list might be the answer... because i'm thinking even if a node is missing a leaf i can jus make a dummy node that has null in it
nocturn4lAuthor Commented:
okay nevermind.. the Ahnentafel list is exactly what i already described.. haven't found much else on it though
phoffric\Commented:
>> i'm not really sure what you want me to do with the picture though?
I just thought that you would draw lines from array elements to tree nodes to try to see a pattern between array elements and levels of the tree (and also the offset within the level).

>> my teacher is saying we don't even need to really implement a binary tree class... just the dummy node
Hmm, if you have an input array SR, and you have to convert it into a LBT, how is this done with just a "dummy node"?
phoffric\Commented:
We've been writing in  parallel. Hold on. Let me catch up.
nocturn4lAuthor Commented:
"Hmm, if you have an input array SR, and you have to convert it into a LBT, how is this done with just a "dummy node"?"

that's what i'm wondering and why i'm posting on here.. i even verified it and he repeated that yea "there's no need to implement the whole binary tree class...just gotta use the dummy node"

/confused

i'm thinking im going to stop stressing out and use the comparative operators and just make my binary tree so that it has some sort of order..........

i have a feeling though that this is not what he wants though as just today we started covering BinarySearchTrees.. but i just can't figure it out
phoffric\Commented:
>> i'm thinking im going to stop stressing out and use the comparative operators and just make my binary tree so that it has some sort of order..........
No need to do that; let's not make the problem more complicated than it is. From your problem statement, it appears that you can fill in the array with whatever you want provided that it is a "random binary tree with at least 15 nodes"

Now thinking ahead about drawing, I see that you are using a char value. We can use single char printable chars in no particular order for your tree.
nocturn4lAuthor Commented:
seems like all the binarytree inserts i been looking at online.. all end up being binarysearchtrees using the comparative operator

is what i'm doing even possible?? lol.. i would like to think so but i find it weird that there's not one example of it online...
phoffric\Commented:
I had an EE outage. Did you experience that as well. You should look at my profile and get my email address. If there is another outage, we can continue there and then add the posts back here when the outage is over.

Do not use comparative operators. Not part of this problem. You are seeing typical usage of binary trees. To convert from array to LBT, I recommend that we use a recursive approach in C++. Is that good for you or do you have to do it in Java?
nocturn4lAuthor Commented:
sigh even that doesn't work.. lol i tried implementing 0, 1, 2, 3, 4, 5 and i end up getting what looks like a linked list because it's already in order.. sigh
nocturn4lAuthor Commented:
yea i got that outage too, i have to do it in Java but even if we do it in C++ i'm sure i can convert it.. it's just syntax.. i'm familiar with both languages
nocturn4lAuthor Commented:
hm looking at you're profile but i don't see anywhere where it states your email
phoffric\Commented:
What does it say immediately under "Member Profile:" and before "Favorite Software"?

Then let's go with C++ recursion. I think I may know what the dummy node may be useful for; but I'll try to avoid it.

What OS and compiler are you using?

nocturn4lAuthor Commented:
"Member Profile:
If you would like to reach me, I can be reached via email: phoffric at hotmail dot com; please begin the subject with EE.

Favorite Software
Visual Studio 2008 Express C++
Cygwin cc, g++, ddd
Xserver is Xming"



using windows XP, the C++ i got on here is Microsoft Visual Studio 2008 Express Edition
nocturn4lAuthor Commented:
rofl sorry i must really be out of it...i didn't even see your email till i pasted it

been brainstorming this stupid problem since 8am... head hurts lol
phoffric\Commented:
Great, let's fix the head hurt. :)

Are you on-board with the idea that a node is a sub-tree?
For your array, what represents a node; an element, right?
And how do you get an element?
An index, right?

So, think of the index into the array as a sub-tree.The index 0 represents the sub-tree of the entire tree. Work in breadth order. Add the 1 sub-tree , and then the 2 sub-tree.

>> "1.  Write a static function convertLink that receives a binary tree in sequential representation (Array SR and the index last) and returns the root of the tree in linked representation.
  ---- Let's call this function convertArrayBTtoLBT. You can rename it to what is required when you are done.

So, let's talk this through to find a recursive pattern and figure out what state information you need. Firstly, in recursion, there must be a way to stop the recursion. What is it for this process?
nocturn4lAuthor Commented:
how long are you planning to stay up tonight?  the internet is going to cut off on me in less than 40 minutes (stupid coffeebean and their 2 hr cutoff -.-)

it's going to take me at most 2 hrs to get access to my home PC...

duno if you're planning to be up that late, what time will you be on tomorrow?


going over what you wrote right now
nocturn4lAuthor Commented:
"Are you on-board with the idea that a node is a sub-tree?
For your array, what represents a node; an element, right?
And how do you get an element?
An index, right?"

Yes, agree to that all

"So, let's talk this through to find a recursive pattern and figure out what state information you need. Firstly, in recursion, there must be a way to stop the recursion. What is it for this process?"

okay i hate recursion so bare with me here..

i'm thinking that when both the left and right child's != NULL
nocturn4lAuthor Commented:
Node convertArrayBTtoLBT(char array[], int lastindex)
{
Node root(array[0];

for(int a=1; a<= lastindex; a++)
{
if(root.left!=NULL)
  insert(root, array[a]);
else if(root.right!=NULL)
  insert(root, array[a]);
else //both leaves are occupied
{
??
}

}
}


lol this is what i came up with so far...
nocturn4lAuthor Commented:
don't even know if that makes sense now that i'm looking at it because i'm not sure how to program the insert
phoffric\Commented:
Ok, you are writing faster than I can respond. :) I'll catch up now.

I'll be in tomorrow night and maybe tomorrow afternoon. Others can help as well. I'll be around later. I can work with you now, and possibly a little more in 2 hours.


>> i'm thinking that when both the left and right child's != NULL
I think you meant that we stop recursion when both children == NULL. That sounds reasonable with the understanding that if only one child is NULL, then we continue recursion down one node.

The dummy node may come in handy; but I'd like to avoid it. It may be useful as a dummy starting point for the tree you are going to create.
nocturn4lAuthor Commented:
i'm pretty sure i have to use the dummy node though because the function is going to end up returning the root node?
phoffric\Commented:
Post code (in the "Code" link) that compiles please. If you can't get it to compile then that is a question that has to be asked. (Usually compiler errors are separate questions.)

Before coding we need to discuss your design since there are many ways to design a problem, and I don't have confidence yet that there is a design in place.

Give me a chance to rewrite the stuff I lost during the darn outage!
You can write in words what you would do manually at a high level using recursion.
nocturn4lAuthor Commented:
ah okay to be honest i have nothing in actual yet atm... just been writing psuedo code

i definitely don't have a design/algorithm... that's what i been trying to come up with this whole darn day

basically if i can come up with the design/algorithm, the coding part is simple
nocturn4lAuthor Commented:
gonna make some code right now... but it's nothing more than what i previously posted tbh
phoffric\Commented:
Agreed, then let's come up with a design first. So, no code just yet.

>> because the function is going to end up returning the root node
Maybe, you may be right - I am not thinking that far ahead. The need will come out as we design the problem.

It isn't necessarily the convertArrayBTtoLBT that is used recursively. Are you required to use that profile? No problem if you are, but there may not be enough arguments to use recursion. We'll see.

To start with an array, you have no problem creating the first 3 nodes of the LBT, right? You can use recursion if you remember that nodes 1 and 2 (the children of 0) are themselves sub-trees. Given the index of the root of a sub-tree array (which can be the 0, the entire SR array), then you can insert the two elements in the LBT. You may do well to define auxiliary functions like createNode, addToParent to help the thinking about recursion.

The array index is, in a sense, a binary sub-tree. Agree?

>> i'm thinking that when both the left and right child's != NULL
I think you meant that we stop recursion when both children == NULL. That sounds reasonable with the understanding that if only one child is NULL, then we continue recursion down one node.


nocturn4lAuthor Commented:
i have about 10 minutes left before the internet shuts off on me......... i'll try to get access to a PC asap but if you end up going before i can contact you in here again... if you do have a design/algorithm in mind maybe you can post something that can help me towards that?

atm it really seems like i'm not going to get this project done.. =[
phoffric\Commented:
How many hours do you have between now and Friday?
Can you request an extension until Monday? (Maybe even if it means a few points off.)
I'll be around for awhile with a break shortly.
nocturn4lAuthor Commented:
"It isn't necessarily the convertArrayBTtoLBT that is used recursively. Are you required to use that profile? No problem if you are, but there may not be enough arguments to use recursion. We'll see."

what i was thinking is that the convertArrayBTtoLBT will just use a for loop to traverse through the array that's given through the parameter...

im thinkin before the for loop in the function i'll create the node root with the first element in the array... then somehow implement a function called "insert" that'll take a node and an element as the parameters

that's what it seems like everyone's doing from the online one's im lookin at anyway
nocturn4lAuthor Commented:
yea i can turn it in on Monday with points off.. Monday is the last day i can drop so i guess really based on if i can even complete this project will be based on whether i drop or not

i'm free all day tomorrow
nocturn4lAuthor Commented:
"To start with an array, you have no problem creating the first 3 nodes of the LBT, right? You can use recursion if you remember that nodes 1 and 2 (the children of 0) are themselves sub-trees. Given the index of the root of a sub-tree array (which can be the 0, the entire SR array), then you can insert the two elements in the LBT. You may do well to define auxiliary functions like createNode, addToParent to help the thinking about recursion."

yea the first 3 nodes seem straight forward.. it's just after that is where i'm completely stuck
phoffric\Commented:
Recursion means that a function named foobar actually can call itself. If I understand you right, you are not talking about recursion.
nocturn4lAuthor Commented:
yea my recursion thinking sucks =[  i'll brainstorm some more while i don't have access to a pc.. lol tbh duno if i'll come up with anything... i been thinking of anything all day!
phoffric\Commented:
According to your earlier posts, you are leaving about now and coming back in two hours. I will look for you then.

I would start with an array of, say 6 elements, and let's walk through a recursive way to build a LBT.

See you in a couple hours.
phoffric\Commented:
One more thing. I do respond to your posts, but every time you write before I respond, I have to save what I've written and try to catch up. So, let's try to have more of a dialogue - unless you need to make a correction to an earlier post.
phoffric\Commented:
>> my teacher is saying we don't even need to really implement a binary tree class... just the dummy node
I think what teacher means is that instead of defining a class Node, we can use instead a struct Node; and then as you mentioned, create a root dummy node to be the start of the LBT.
phoffric\Commented:
In http:#30761123 you mentioned that in the array, you are using the number 0 to represent that the element is not really a node. Now char is an integer. Are you saying that 0 is not allowed to be one of the integer values? Is it that you are allowing only printable characters, or even alphabetical characters to be allowed?
nocturn4lAuthor Commented:
hey i'm sorry, i hope you didn't wait around long, i couldn't get back home until not long ago..

i was brain storming and entered some code (it's in java though.. ) and this is what i came up with so far

using this tree (using numbers for sake of simplicity atm)

                   0
                /     \
              1       2
             / \       / \
           3   4    5   6
          /\    /\    /\    /\
        7 8 9 1011121314

and the most i can get an output is this:


Binary Tree Example
Building tree with root value 0
  Inserted 3 to left of 1
  Inserted 7 to left of 3
  Inserted 4 to right of 1
  Inserted 10 to right of 4


still dont have a real algorithm.. just been toying with it........ just trying to come up with something......

i have the worst headache gonna pass out.. sorry once again.. i duno im having 2nd thoughts bout everything.... i can't believe it's taking me this long to figure out not even half of the assignment and i still have no idea how to figure out just that part..



public class BinaryTreeTest {

  public static void main(String[] args) {
    new BinaryTreeTest().run();
  }

  static class Node {
    Node left;

    Node right;

    int value;

    public Node(int value) {
      this.value = value;
    }
  }

  public void run() {
  
  int[] sr = new int[15];
  for(int a=0; a<15; a++)
	sr[a] = a;


    Node root = new Node(sr[0]);
    root.left = new Node(sr[1]);
    root.right = new Node(sr[2]);

    System.out.println("Building tree with root value " + root.value);

for(int a=3; a<15; a=2*a+1)
    insert(root, sr[a]);
  

for(int a=4; a<15; a=2*a+2)
    insert2(root.left, sr[a]);
  }





public void insert(Node node, int value)
{

if(node.left == null)
{
  node.left = new Node(value);
  System.out.println("  Inserted " + value + " to left of " + node.value);
}

else
{
  insert(node.left, value);
}

}

public void insert2(Node node, int value)
{

if(node.right == null)
{
  node.right = new Node(value);
  System.out.println("  Inserted " + value + " to right of " + node.value);
}

else
{
  insert2(node.right, value);
}

}


}

Open in new window

nocturn4lAuthor Commented:
"In http:#30761123  you mentioned that in the array, you are using the number 0 to represent that the element is not really a node. Now char is an integer. Are you saying that 0 is not allowed to be one of the integer values? Is it that you are allowing only printable characters, or even alphabetical characters to be allowed?"

i was on my cellphone so i just used 0 for lack of a better key for null

it would really be

0 1 2 3 4 5 6 7 8
A B F NULL C NULL K H NULL
phoffric\Commented:
But char can hold an 8 bit integer. So NULL is what?
phoffric\Commented:
I worked on a recursive solution, createSubtree. Now that you're back, here's what I have written on recursive solution for you.

We talked about the array index not only representing an array element (as in array[index]) but also as a sub-tree binary tree in array representation.

To think recursively, start in the middle. Since you already wrote the following that given array index 12, its:
   left child   = 12*2 + 1 = 25
   right child = 12*2 + 2 = 26
   parent      = 12/2 - 1  = 5
then let's proceed from here to deal with the corresponding Linked Binary Tree. You can have a function called createSubtree which creates these nodes and links them to the parent.

You have no problems creating the left and right child nodes given an index 12, right? But, careful, under what cases is there no right and/or left child? Spell out in words what are the cases. Then spell out all the information that createSubtree needs to handle these cases.

But after creating a child node, you need to link it to the parent. So, createSubtree needs what entity to enable it to do this linking?

Now, if there is a child (whether left or right), then you know its corresponding array index (you just figured it out), and you have the child, so you can take this information and create another sub-tree.

After we get through the createSubtree function design, let's see if it can work for the first array element where i = 0.
phoffric\Commented:
Now, about the drawing part. Given a binary tree, do you know how to do a Breadth-first order traversal? If not, then I am not sure why you are expected to draw it just as you did. It's probably a little tricky - even if you get the levels out correctly, you have to get the spacing right.

Here is a link where someone did do this. See if this is what you have in mind.
              http://www.experts-exchange.com/Programming/Algorithms/Q_25014702.html

nocturn4lAuthor Commented:
hey i can't believe you're still up!  was just shutting off my comp until i heard the email noise

i really have no energy right now along with a headache.. i've been up since 8am PST so please excuse me for being rude and going to bed... i really can't believe u've been working on this !

i really really need a fresh mind to work on this, i'll be back here first thing when i wake up.. i appreciate the time and effort you've put into this with me, i really can't expect more from you - just stop by here again whenever ur free and i'll tell u my progress

the things u wrote jus now makes sense i think.. hopefully i can code it/figure it all out tomorrow

sorry again, good night
phoffric\Commented:
The problem I thought we were solving is how to convert an array binary tree into a linked binary tree, right? Is that what your Java code is doing? I don't see the array. Well, I guess your tired. We'll talk tomorrow after your fresh.

I see that you changed the "char data" to "int value". But still, how do you plan on representing NULL as an int?

Also, if you actually have a java test project, it might be good to show all the code including the test driver. No second guessing that way.
phoffric\Commented:
Have a good night. Hope your headache goes away!
phoffric\Commented:
>> just stop by here again whenever ur free and i'll tell u my progress
I'm hoping that if you address some of my hints (in the form of questions) then you'll be able to design the interface. Once doing that, the code will be easier.
BTW - I thought "run" was used for Java threading.
phoffric\Commented:
One more thing about change from char data to int value..
If data was a single printable character, then spacing in printing the tree using BFS is easier than value which when printed will require a variable width.
phoffric\Commented:
Please let me know your status. I'll be back in 1-2 hours to check to see if you have any desire to continue with the recursive solution that we talked about. If so, please address all the questions I asked, including those about the drawing of the binary tree. Does it have to be drawn as you have shown it, or can it be drawn in any way just to show the LBT is correct. The way you show it requires a Breadth First Search (Order) approach which is a little harder than other depth approaches.

Let me know what course this is for, and your knowledge of the material (and future expectations); and we can even talk about you thinking about whether to drop the course. (I assume that the problems will get harder, not easier, as you get further into the course.)
nocturn4lAuthor Commented:
Hi, i'm back.. i pretty much slept almost 24 hrs ...this project has been stressing me out so bad.. i have other class hw/projects that ima finish up first before i attempt to tackle this again as it's impossible for me to finish by Friday (it's due in a few hours)

i'm goign to make a real attempt to get back at this and finish by Monday (last day to drop the class with a 'W') so i'll post here when i attempt to crack at this again... gonna re-read everything you posted since we last talked when i do but until now i'm not wasting anymore brain energy (lol) on this stupid assignment that's making me re-think if i'm even cutout for this damn CS major aldfjlakfjaklfjalsdfjasdf
phoffric\Commented:
The best approach given your time schedule is instead of you taking cracks, just try to answer the questions I raised. If you have trouble answering, well, then you do your best, and I will guide you to the right answers. At that point it is a good idea to take a coding attempt. No one really writes code without a design (at least in the head). So, if we're going to be on the same page, I need to know what you are thinking so that I can guide you. Given the pressure you are under, you might consider a tutor as well. That usually goes faster than email.

You might address the question about whether you are familiar with BFS, or whether you have to draw the picture exactly as shown in your OP - it is shown with "pretty spacing" and a breadth-first ordering, which is a little harder than the usual depth ordering. When do you want to start again? Tonight and through the weekend?

We can talk about how comfortable you are with CS major. Sometimes you just get a little behind, and then seem lost, when the highway is just above the next hill.
phoffric\Commented:
If you want, post the entire Java project with your test driver, so that I can try to assess what you have done. If I don't think I can help (because it is java) then I'll find a Java expert for you.
nocturn4lAuthor Commented:
"The best approach given your time schedule is instead of you taking cracks, just try to answer the questions I raised. If you have trouble answering, well, then you do your best, and I will guide you to the right answers. At that point it is a good idea to take a coding attempt. No one really writes code without a design (at least in the head). So, if we're going to be on the same page, I need to know what you are thinking so that I can guide you. Given the pressure you are under, you might consider a tutor as well. That usually goes faster than email."

will do, maybe tonite at the latest some time tomorrow, thanks once again
nocturn4lAuthor Commented:
I DID IT~!!!

ADSKLFJADKLFJADKLFJADLFJAD

i'm not proud of the way i did it lol but i friggin did it... you gave me an idea when you said to make a class that involves the parent

lol i'm in a race against the clock to finish the 2nd half of the program because class is real soon but i'll be back here later!
phoffric\Commented:
>> I DID IT~!!!
Congrats!!!!!!

>> i'm not proud of the way i did it lol but i friggin did it !!!!!!!!!
Right, this is not a trivial problem. So, the first pass is likely not the supreme professional solution - if it were, why the heck aren't you working at Google now, and forget school - lol.

>> i'm in a race against the clock to finish the 2nd half
If you post what you have, maybe I can help further. But, I'm assuming that you are doing this in Java. So, I'll need all the source code, and will build in Eclipse.

Are you using Netbeans, Eclipse, or what? Maybe I'll build in your same environment if that will help.
phoffric\Commented:
BTW, is your deadline midnight PDT? It is 9:15pm EST where I am. So, do you have almost 6 hours left. If you have an extension till Monday (morning?), then you can submit what you have before midnight, and then resubmit (possibly with improvements including a notice of improvements - that will look good) over the weekend. Then you should not lose as many points since you have done some (most?) of the work today. One student on EE did this, and ended up with a score of 105 because of extra bonus points which made up for the lost penalty points.

Please don't post here near the deadline and ask for help. I may need time to download the IDE and build your project, and then walk-through your code to understand the approach you are taking. (I don't want to confuse you with my approach, if you are taking a different path.)
nocturn4lAuthor Commented:
hey again - not home atm but i already turned it in - i was able to finish it in time (was actually due like half an hour after my last post lol) ;D

it's crazy.. once i came up with the solution to the first part i was able to write the program in like an hour.. i feel so great today haha

i gotta thank you so much for your dedication in helping me.. when i get home i'll post my solution

i'm curious though - did you come up with a solution with the problem at all?
phoffric\Commented:
You identified about 6 problems! I worked out (C++) the problem of converting an array BT to a LBT, and then verified that all the elements were there in a display method (I have to tweak it to get the BFS ordering).

I didn't want to move too far ahead, because, you may not have decided to do a recursive approach, which is fine.

I was surprised to hear that you got the entire problem solved in such short time. 12 hours earlier you were talking about dropping CS!! Maybe you should get more rest. You seem to do better that way. :)
nocturn4lAuthor Commented:
On my phone atm but haha yea I meant just the arraybt to a linked bt.

I didn't do it recursively unfortunately, but after I post how I did it, I'd love to see how u solved the problem.. Its still buggin the crap out of me lol
phoffric\Commented:
You may have a very good solution. I'll look at your post - be sure to include enough so that I can build it along with your test drivers - I'll check to see whether you included enough test cases.

Do you want to continue working on the problem further, and if you end up with any improvements, you could resubmit it leaving it up to the instructor as to whether or not to look at it. Ultimately, it's not the assignment that counts in the long run, but what you learn from the assignment and how it may help you in the future.
phoffric\Commented:
I'll be back a couple of hours to review your solution. If I find any errors in testing, I'll be sure to let you know. Get some rest - you earned a break!
nocturn4lAuthor Commented:
                   A
                 /       \
              B            C
             /  \          /   \
            D   E      F     G
           / \   / \     / \    / \
          H I  J K   L M  N O
            / \        /         \
           P Q     R          S
nocturn4lAuthor Commented:
okay that's the tree i drew.... basically in the main function i just manually made an array tree of what i drew there then called the 2 functions i was supposed to make

the convert to link like i stated i didn't do recursively but i duno it just clicked out of no where while reading through this thread that i can just do it really simply.... lol

i basically made an array full of nodes then made a for-loop to link them all together........how simple was that? =T

then for the link to array i just used one of the million recursive ideas i was trying for the previous function to traverse through the array....even though it would overlap the same node it would still be writing the correct value.. just overwriting i guess

pretty sloppily programmed i must say but it got the assignment done i believe

only thing i'm not sure is that int he assignment the convert to array function was supposed to return the array + index.. which isn't possible because how can u return 2 things?  so i'm assuming it's a typo and i just returned the array



i would love to improve on this but you know how school is.... so many subjects- just gotta keep moving on so i dont think i can spend too much more brain power on this specific problem

but you're right, it's really not about solving the problem (it was in this case though as i just needed the points and to keep the class!) but what i've learned from it and well.. i duno if i learned much tbh lol

i'm still interested to see how you solved the array-to-linked tree

but yea feel free to test my code.. because of it's simplicity i'm thinking it's pretty much bug free?

thanks again for your time and effort.. i'd buy you lunch or somethin if i could ;P
public class BinaryTreeTest {

  public static void main(String[] args) {
    new BinaryTreeTest().run();
  }

  static class Node {
    Node parent;
    Node left;
    Node right;

    String value;

    public Node(String value) {
      this.value = value;
    }
  }

  public void run() {
  

  //create Binary Tree that I made
  String[] sr = new String[29];
  sr[0] = "A";
  sr[1] = "B";
  sr[2] = "C";
  sr[3] = "D";
  sr[4] = "E";
  sr[5] = "F";
  sr[6] = "G";
  sr[7] = "H";
  sr[8] = "I";
  sr[9] = "J";
  sr[10] = "K";
  sr[11] = "L";
  sr[12] = "M";
  sr[13] = "N";
  sr[14] = "O";
  sr[17] = "P";
  sr[18] = "Q";
  sr[23] = "R";
  sr[28] = "S";

  //call functions required of assignment
  Node root = convertLink(sr, 28);
  String []SR = convertSequential(root);

//note: your instructions say for convertSequential to return the array SR AND index last
//      since functions can't return 2 things i just returned the array SR


  //print contents of SR
  for(int a=0; a<=28; a++)
    System.out.print(SR[a] + ", ");
}




private void printTree(Node node) {
 if (node == null) return;

 // left, node itself, right
 printTree(node.left);
 System.out.print(node.value + "  ");
 printTree(node.right);
} 

public int size(Node node) {
  if (node == null) return(0);
  else {
    return(size(node.left) + 1 + size(node.right));
  } 
}

public String[] convertSequential(Node rootnode)
{
  //create empty node array with size of tree
  int sizeoftree = size(rootnode);
  String[] arrayofnodes = new String[sizeoftree];

  getallvalues(rootnode, arrayofnodes, 0);

  return arrayofnodes;
}

public void getallvalues(Node rootnode, String []seq, int a)
{
  int left = 2*a+1;
  int right = 2*a+2;
  int last = seq.length - 1;

  seq[a] = rootnode.value;

  if(left<=last) //if left child exists
  {
    seq[left] = rootnode.left.value;
  }
  if(right<=last) //if right child exists
  {
    seq[right] = rootnode.right.value;  
  }

  if(left<=last)
    getallvalues(rootnode.left, seq, left);
  if(right<=last)
    getallvalues(rootnode.right, seq, right);

}

public Node convertLink(String []sr, int last)
{
//create empty array of nodes
Node[] nodesarray = new Node[last+1];

//create root node
Node root = new Node(sr[0]);
root.parent = null;
nodesarray[0] = root;

//create rest of nodes
for(int a = 1; a<=last; a++)
{
  Node eh = new Node(sr[a]);
  nodesarray[a] = eh;
}

//link nodes to it's childs and parent
for(int a = 0; a<=last; a++)
{
  int left = 2*a+1;
  int right = 2*a+2;
  if(left<=last) //if left child exists
    nodesarray[a].left = nodesarray[2*a+1];
  if(right<=last)
    nodesarray[a].right = nodesarray[2*a+2];
  if(a>0) //if not root
    nodesarray[a].parent = nodesarray[(a-1)/2];
}

//print node info
for(int a=0; a<=last; a++)
{
  System.out.println("Node = " + nodesarray[a].value);

  if(nodesarray[a].left!=null)
    System.out.println(nodesarray[a].value + ".left = " + nodesarray[a].left.value);
  else
    System.out.println(nodesarray[a].value + ".left = NONE");

  if(nodesarray[a].right!=null)
    System.out.println(nodesarray[a].value + ".right = " + nodesarray[a].right.value);
  else
    System.out.println(nodesarray[a].value + ".right = NONE");

  if(nodesarray[a].parent!=null)
    System.out.println(nodesarray[a].value + ".parent = " + nodesarray[a].parent.value);
  else
    System.out.println(nodesarray[a].value + ".parent = NONE, is ROOT");

  System.out.println();
}

return root;

}


}

Open in new window

nocturn4lAuthor Commented:
if you don't want to mess with java it shouldn't be too hard to convert to c++... just change the System.out to cout's.. use the --> for the node class and declare the functions.. only a few syntax changes i believe

oh and i didn't use PrintTree function that i have in there.. i just copied and pasted it from the internet to see how that would print my tree i just forgot to remove it when i turned it in.. doh!
nocturn4lAuthor Commented:
yea i been up since 4am PST, so gonna hit the sack soon, i'll come by to check this page out tmrw

also i would like to give you points or something... it's the least i can do...which post can i push "accept as solution" to?
nocturn4lAuthor Commented:
oh this is what it looks like when i run the program:

$ java BinaryTreeTest

Node = A
A.left = B
A.right = C
A.parent = NONE, is ROOT

Node = B
B.left = D
B.right = E
B.parent = A

Node = C
C.left = F
C.right = G
C.parent = A

Node = D
D.left = H
D.right = I
D.parent = B

Node = E
E.left = J
E.right = K
E.parent = B

Node = F
F.left = L
F.right = M
F.parent = C

Node = G
G.left = N
G.right = O
G.parent = C

Node = H
H.left = null
H.right = null
H.parent = D

Node = I
I.left = P
I.right = Q
I.parent = D

Node = J
J.left = null
J.right = null
J.parent = E

Node = K
K.left = null
K.right = null
K.parent = E

Node = L
L.left = R
L.right = null
L.parent = F

Node = M
M.left = null
M.right = null
M.parent = F

Node = N
N.left = null
N.right = S
N.parent = G

Node = O
O.left = NONE
O.right = NONE
O.parent = G

Node = null
null.left = NONE
null.right = NONE
null.parent = H

Node = null
null.left = NONE
null.right = NONE
null.parent = H

Node = P
P.left = NONE
P.right = NONE
P.parent = I

Node = Q
Q.left = NONE
Q.right = NONE
Q.parent = I

Node = null
null.left = NONE
null.right = NONE
null.parent = J

Node = null
null.left = NONE
null.right = NONE
null.parent = J

Node = null
null.left = NONE
null.right = NONE
null.parent = K

Node = null
null.left = NONE
null.right = NONE
null.parent = K

Node = R
R.left = NONE
R.right = NONE
R.parent = L

Node = null
null.left = NONE
null.right = NONE
null.parent = L

Node = null
null.left = NONE
null.right = NONE
null.parent = M

Node = null
null.left = NONE
null.right = NONE
null.parent = M

Node = null
null.left = NONE
null.right = NONE
null.parent = N

Node = S
S.left = NONE
S.right = NONE
S.parent = N

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, null, null, P, Q, null, null, null, null, R, null, null, null, null, S,
nocturn4lAuthor Commented:
i shoulda made a better output format but obviously i was in a rush......
phoffric\Commented:
Just got back. Haven't looked yet. Just seeing if you are awake.
For drawing from the LBT, do you have to draw a tree as you have shown in your original post?
phoffric\Commented:
I liked your getallvalues method - nice use of recursion! Only comment is performance related. The same seq slots are filled more than once with the same value - of course, at least it is the same value. :) Recursion is sometimes a little tricky. But not bad, all in all.

re: convertLink
Technically speaking, you linked up the nodes. But, I'm not sure whether you will get full credit for your effort since you stuck the nodes in an array of nodes. Usually, a LBT is supposed to consist of free-standing nodes, I believe; and not in an array container. By doing so, you really simplified the problem, but my concern is that maybe it was simplified too much to get full credit. So, to play safe, maybe you can submit another solution without creating an array, perhaps a recursive solution since you seem to now have a better recursive grasp.

>> computeLevel that computes the number of levels in the received tree
You computed the number of elements in the LBT which allowed you to make enough room in your SR. But, the assignment calls for the number of levels in the tree. In the LBT drawn in your OP (from A..G) computeLevel would return 3 levels. So max # elements in your SR is 2^3 - 1 = 7 And in your latest example, there are 5 levels, so you would need 2^5 - 1 = 31.

Nit comment: I didn't see any real need for the parent attribute (except maybe for your peace of mind by seeing it your debugging output).

Re: Test step 1 - I probably misunderstood this to mean that given an LBT draw a 2D picture. (And I gave you an EE link of someone who actually pursued that path.) Here is my output using your test scenario (later I may add proper spacing that is a function of the number of levels, and the particular level).

A
B C
D E F G
H I J K L M N O
_ _ P Q _ _ _ _ R _ _ _ _ S * *
The underscore means that the initial string had an _ in it which represented a NULL. This display routine was done using recursion also.

I may provide some additional inputs to test further after I hear back from you on these comments.

Here is the C++ code defining the initial array BT. Can you do something similar in Java so that you do not have to write each char in a separate statement? Makes change easier, I think. Of course, then you would need a special char to represent NULL (e.g., the underscore).
string arrBT = "ABCDEFGHIJKLMNO__PQ____R____S";

Open in new window

phoffric\Commented:
I forgot to mention that in my LBT 2D display, the * also represents a null. But it represents the case where there was not an explicit NULL in the input string. Every level in the display is a power of 2, so the *'s fill up the last level.
phoffric\Commented:
I'll be back for a brief visit around 5-6pm EDT and then again after 8pm in case you are planning on doing more work on this. But if you need to pursue this further before then you can accept one or more posts that helped you with your assignment, and then there's an Ask A Related Question button, where you can do just that. If you want to learn more about the recursive function (array to LBT) that I used, then I and others will be happy to help you develop it.

All in all - nice going. :)
(You made me relearn some of the basics in using the Eclipse IDE for your Java.)
phoffric\Commented:
On whether to drop CS or not (as you were considering before). I'm not sure how much more there is for you to complete the program. Suffice to say that I have met students who actually graduated with a CS degree and then went on to another major. If you really enjoy working out problems and modeling requirements into a design, implementing and testing the code, then go for it. Depending on the complexity of your school, the curriculum can be very arduous; so if you're going to work that hard, hopefully you will enjoy it. I think that should be one of your major decisions if you are asking this question, rather than whether you met this deadline. If you want to write about this offline, then see my contact information in my profile.
nocturn4lAuthor Commented:
HEY! i haven't read your comments yet (i gotta head out right now) but omg......it just hit me out of no where that i'm an idiot and i can pretty much use the same way i made my convertsequential function to make my convertlink......i made it even better too so that it doesn't overlap (i think)

omfg im so proud of myself haha i think it works!......i just turned this in through email so hopefully he accepts this version

Output:


java BinaryTreeTest
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, null, null, P, Q, null, null, null, null, R, null, null, null, null, S,

public class BinaryTreeTest {

  public static void main(String[] args) {
    new BinaryTreeTest().run();
  }

  static class Node {
    Node parent;
    Node left;
    Node right;

    String value;

    public Node(String value) {
      this.value = value;
    }
  }

  public void run() {
  

  //create Binary Tree that I made
  String[] sr = new String[29];
  sr[0] = "A";
  sr[1] = "B";
  sr[2] = "C";
  sr[3] = "D";
  sr[4] = "E";
  sr[5] = "F";
  sr[6] = "G";
  sr[7] = "H";
  sr[8] = "I";
  sr[9] = "J";
  sr[10] = "K";
  sr[11] = "L";
  sr[12] = "M";
  sr[13] = "N";
  sr[14] = "O";
  sr[17] = "P";
  sr[18] = "Q";
  sr[23] = "R";
  sr[28] = "S";

  //call functions required of assignment
  Node root = convertLink(sr, 28);
  String []SR = convertSequential(root);

//note: your instructions say for convertSequential to return the array SR AND index last
//      since functions can't return 2 things i just returned the array SR


  //print contents of SR
  for(int a=0; a<=28; a++)
    System.out.print(SR[a] + ", ");
}

public int size(Node node) {
  if (node == null) return(0);
  else {
    return(size(node.left) + 1 + size(node.right));
  } 
}

public String[] convertSequential(Node rootnode)
{
  //create empty node array with size of tree
  int sizeoftree = size(rootnode);
  String[] arrayofnodes = new String[sizeoftree];

  getallvalues(rootnode, arrayofnodes, 0);

  return arrayofnodes;
}

public void getallvalues(Node rootnode, String []seq, int a)
{
  int left = 2*a+1;
  int right = 2*a+2;
  int last = seq.length - 1;

  seq[a] = rootnode.value;

  if(left<=last) //if left child exists
  {
    seq[left] = rootnode.left.value;
  }
  if(right<=last) //if right child exists
  {
    seq[right] = rootnode.right.value;  
  }

  if(left<=last)
    getallvalues(rootnode.left, seq, left);
  if(right<=last)
    getallvalues(rootnode.right, seq, right);

}



public void createsubtree(Node rootnode, String []seq, int a)
{
  int left = 2*a+1;
  int right = 2*a+2;
  int last = seq.length - 1;

  if(left<=last) //if left child exists
  {
    Node lnode = new Node(seq[left]);
    rootnode.left = lnode;
    createsubtree(rootnode.left, seq, left);
  }
  if(right<=last) //if right child exists
  {
    Node rnode = new Node(seq[right]);
    rootnode.right = rnode;
    createsubtree(rootnode.right, seq, right);
  }
    
}

public Node convertLink(String []sr, int last)
{
//create empty array of nodes
Node[] nodesarray = new Node[last+1];

//create root node
Node root = new Node(sr[0]);
root.parent = null;
nodesarray[0] = root;

//recursive func here
createsubtree(root, sr, 0);

return root;

}


}

Open in new window

nocturn4lAuthor Commented:
i'll be back to answer/comment on your comments and close up the topic and everything

i'm so happy right noW!!!!!!!!
phoffric\Commented:
>> it just hit me out of no where
Really nice cleaner looking solution. Maybe some time off cleared your mind!

Nit: If you don't need nodesarray, you can remove it. (It gives the wrong impression about the array crutch you had used earlier.)

I noticed that in your run function, you hard-coded the number 28. When calling convertSequential with an arbitrary LBT (not one that you just created), you don't know without examining it; i.e., use the level idea talked about in previous post, or at least compute the size as you did.

Also, for the future, try to figure out how to set up a string such as arrBT shown below, and then compute the size from it (C++ code shown below). Now, there won't be any magic numbers (such as 28) - all will be computed, including test variables programmatically. Try to avoid hard-coded magic numbers.

>> since functions can't return 2 things i just returned the array SR
Just as C++ can return only one value and Java has the same rule, there is nothing to say that you cannot create a class pair (as in C++ STL) which is a pair of two values, of same or different types, and then you can return an object of that pair type.

This is a good second round. Nice going! If you are up for a third round, then consider the case where you have an unbalanced BT (i.e., some paths go much deeper than other paths). In this case, I believe that you (and I in my first round) are creating a Node having a NULL value, and then linking it up to the parent. In LBT's a leaf of a tree has a value (i.e., not a null value), and its left/right pointers are NULL. But your LBT (and mine) has a leaf (with a value) that has children which are NULL nodes (and they in turn may also have children with these NULL value Nodes).

I'll try to fix my own version.

======
Now, in the real world, you have to deal with inputs that don't make complete sense. For example, if you comment out the line:
   // sr[5] = "F";
then even though there are still values 'L' and 'M' in the children slots, those are just bogus values since sr[5] is NULL and cannot have any children; so we know that they should be ignored. But both our solutions are still picking them up. I may fix my version so that there are no nodes under 'F', and then even if  'L' and 'M' are in the children slots, then no nodes will be generated for them.
string arrBT = "ABCDE_GHIJ_LMNO__PQ____R____S";
int arr_size = arrBT.size(); // compute size from the test string

Open in new window

nocturn4lAuthor Commented:
yea it really seems like my solutions to these problems just come out of the blue.......and never when i'm really trying to solve the problem.. lol... not necessarily a good thing but at least i'm eventually solving em

"Nit: If you don't need nodesarray, you can remove it. (It gives the wrong impression about the array crutch you had used earlier.)"

ah yea gonna clean that up when i turn that in on monday


"I noticed that in your run function, you hard-coded the number 28. When calling convertSequential with an arbitrary LBT (not one that you just created), you don't know without examining it; i.e., use the level idea talked about in previous post, or at least compute the size as you did."

ah never noticed that, good catch, gonna clean that up too


"Also, for the future, try to figure out how to set up a string such as arrBT shown below, and then compute the size from it (C++ code shown below). Now, there won't be any magic numbers (such as 28) - all will be computed, including test variables programmatically. Try to avoid hard-coded magic numbers."

gonna do that too....but say i do
string arrBT = "ABCDE_GHIJ_LMNO__PQ____R____S";

any idea how i can insert NULL so that it looks clean in that sort of same format?



>> since functions can't return 2 things i just returned the array SR
Just as C++ can return only one value and Java has the same rule, there is nothing to say that you cannot create a class pair (as in C++ STL) which is a pair of two values, of same or different types, and then you can return an object of that pair type.

hmmmm i think i'll change it then so that i have an SR class instead.. maybe that's actually what he wants.....

so i have an important question then.. looking at my OP at the actual assignment.. in my main function.. do you think i'm manually creating my sequential binary tree correctly??  all i know is we're supposed to create it manually and then use that to call the functions that i've made.. guess ima have to do more googling but now i'm having 2nd doubts that i even made the original sequential binary tree correctly...


"In this case, I believe that you (and I in my first round) are creating a Node having a NULL value, and then linking it up to the parent. In LBT's a leaf of a tree has a value (i.e., not a null value), and its left/right pointers are NULL. But your LBT (and mine) has a leaf (with a value) that has children which are NULL nodes (and they in turn may also have children with these NULL value Nodes)."

hm yea i think from my code where there's no children at the bottom level i'm just creating a node with a NULL value.. not sure how else i would do it?  i'm not even sure if it's making null children for those nodes tbh lol.. don't think i have enough time to fix all that have 2 other things for other classes due monday  /stressed again
phoffric\Commented:
>> any idea how i can insert NULL so that it looks clean in that sort of same format?
    Not positive I understand the question. Here is where your Java expertise comes into play. If I have a string and stick in a null (say by using \000), then that acts as a string terminator. The '_' is internal representation only. It is, in a sense, a magic number which must not ever be normally present as a value. In C++ I have the #define shown below. The display can look at the value and if it is a NULL_NODE_INDICATOR produce a clean looking output similar to what you produce by testing for this null indicator value.
    I probably should have used const char NULL_NODE_INDICATOR = '_' instead (and something like that translates better into Java than #define.
    Of course, one advantage about your approach for debugging is that you really make it clear the value and the index for an array element.



#define NULL_NODE_INDICATOR '_'

Open in new window

phoffric\Commented:
>> do you think i'm manually creating my sequential binary tree correctly??
    Yes, based on all the info you've given me, this does not appear to be a specific binary tree for a particular application. It appears more like a mapping from array representation to linked BT and back again. This is not trivial, and some issues are coming up.

    But, as I mentioned, your particular examples in the OP and your later posts show a fairly balanced BT. For more generality you could have an unbalanced BT where it is more obvious that you are creating Nodes that have no value. That is, usually I see the leaves of the BT as having a value, and not having some representation of a NULL value. For a large sparse input array, you could end up making 100's or 1000's of Nodes that do not have to be created for the LBT. That, I don't think is a good idea. (Of course, later you will learn how to balance the trees.) But even with your later posts, you are creating a few Nodes that have no value in them, so I think that could be avoided.

Don't forget about the level vs size comments - your OP asks for a get level function that acts on a LBT. You are doing a good job of getting the number of elements in the LBT. If you have 4 levels, then you need at least 2^4 - 1 elements for your array.
phoffric\Commented:
>> guess ima have to do more googling but now i'm having 2nd doubts that i even made the original sequential binary tree correctly...
    What doubts explicitly do you have? What will you google on? If you wanted to make a searchable or an expression BT, you could do that provided that is what the teacher is expecting. Sounds like your teacher does not respond to clarification questions. But if you write down your concerns here, I can at least help you formulate a clear question for the teacher.
nocturn4lAuthor Commented:
bout to hit the sack but jus went over your comments real quick.. looks like there's a lot i still gotta do........gonna try to touch up on all the things that you've mentioned as much as possible tomorrow if i have the time... but it's definitely gonna be time consuming so not sure how much of all that i can actually get finished

i'll be back here late tomorrow hopefully i'll let u know what things i've changed etc, gonna try your NULL suggestion too, thanks again!
phoffric\Commented:
If you have time, and want to do one extra thing, namely display the LBT in the form I presented (a set of value in each level per line), it may look easy, but there is one gotcha that you may not be aware of. Anyway if you do it, not only will you learn a little more about design, but you may receive extra credit if you make sure the teacher is aware of it.

Even as it stands now, your program is pretty good. Having extra nodes may not be the worst thing for this first type of an assignment. The level vs size actually does not meet the OP requirements, but that shouldn't be too hard - starting from the root, you have a directed graph (the LBT), and you are just trying to find the longest path.
phoffric\Commented:
One last thing. Do you think that the test should be automated. That is after doing the two conversions, you could do a simple check that sr and SR have the same results, and report all index values wherever there is a mismatch. And if none (as is your goal), then output the message saying that input SR and output sr match - SUCCESS!!!

Otherwise, for every test scenario you come up with, you have to manually do this step by hand.
phoffric\Commented:
OK, my version now creates an LBT with only nodes having values. I had to modify the display routine to always print out 2^level items per line. Notice I even handle the case where the 'F' is now NULL, and yet its children, 'L' and 'M' are still in the array. However, they are no longer in the LBT.
/*
string size = 29
array BT = ABCDE_GHIJ_LMNO__PQ____R____S
parent[0] = A
0: left child[1] = B
parent[1] = B
1: left child[3] = D
parent[3] = D
3: left child[7] = H
parent[7] = H
3: right child[8] = I
parent[8] = I
8: left child[17] = P
parent[17] = P
8: right child[18] = Q
parent[18] = Q
1: right child[4] = E
parent[4] = E
4: left child[9] = J
parent[9] = J
0: right child[2] = C
parent[2] = C
2: right child[6] = G
parent[6] = G
6: left child[13] = N
parent[13] = N
13: right child[28] = S
parent[28] = S
6: right child[14] = O
parent[14] = O

string size = 29
array BT = ABCDE_GHIJ_LMNO__PQ____R____S
A
B C
D E * G
H I J * * * N O
* * P Q * * * * * * * * * S * *
*/

const char NULL_NODE_INDICATOR = '_';

int main() {
   //string arrBT = "ABCDEFGHIJKLMNO__PQ____R____S";
     string arrBT = "ABCDE_GHIJ_LMNO__PQ____R____S";
   int arr_size = arrBT.size();
   int max_level = (int)getMaxLevel( float(arr_size) );

   Node root( arrBT[0] );
   cout << "string size = " << arr_size << endl;
   cout << "array BT = " << arrBT << endl;
   createSubtree( 0, &root, arrBT, arr_size );

   vector<Node*> rootNodeList;
   rootNodeList.push_back( &root );
   displayTree( rootNodeList );
}

Open in new window

phoffric\Commented:
I looked at your createsubtree with my version. I start off like this (don't worry about the profile - I didn't follow the naming conventions in your OP so I have a different profile. Where do you set your left/right pointers if there are no children?
void createSubtree( int array_parent_index, Node * btree, string arr, int last_index ) {
   btree->Left  = NULL; // assume no left child
   btree->Right = NULL; // assume no right child
...
}

Open in new window

phoffric\Commented:
If you have any further questions, I'm back to help you.
phoffric\Commented:
Again, congrats on submitting your assignment in on time, and figuring out how to do it both ways (recursive and not). I hope you learned a lot.

To create the LBT without any excess nodes (i.e., nodes having a null value), I just added a test for the data value having a NULL INDICATOR to my create LBT function (see below). I also show my C++ createArray function which converts an LBT into a SR.

Here is the output now that I added the step to eliminate excessive nodes. It now handles the case where the input has dangling children (i.e., no parent); for example L and M were left over from a previous run, but the parent F has been removed. So you cannot reach L and M from the root A.

string size = 29
Before: array BT = ABCDE_GHIJ_LMNO__PQ____R____S
  After:  array BT = ABCDE_GHIJ___NO__PQ_________S__
A
B C
D E * G
H I J * * * N O
* * P Q * * * * * * * * * S * *
void createSubtree( int array_parent_index, Node * btree, string arr, int last_index ) {
   btree->Left  = NULL; // assume no left child
   btree->Right = NULL; // assume no right child

   char array_parent_val = arr[array_parent_index];
   int left_index  = 2*array_parent_index + 1;
   int right_index = left_index + 1;

   // Make sure that left index is not out-of-bounds
   if( left_index < last_index && arr[left_index] != NULL_NODE_INDICATOR ) {
      btree->Left = new Node( arr[left_index] );
      createSubtree( left_index, btree->Left, arr, last_index );
   }
   // Make sure that right index is not out-of-bounds
   if (right_index < last_index && arr[right_index] != NULL_NODE_INDICATOR ) {
      btree->Right = new Node( arr[right_index] );
      createSubtree( right_index, btree->Right, arr, last_index );
   }
}

void createArray( Node * pRoot, char * strArrBT, int levelNum ) {
   strArrBT[levelNum] = pRoot->data;
   if( pRoot->Left != NULL ) {
      createArray( pRoot->Left, strArrBT, 2*levelNum + 1 );
   }
   if( pRoot->Right != NULL ) {
      createArray( pRoot->Right, strArrBT, 2*levelNum + 2 );
   }
}

Open in new window

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
nocturn4lAuthor Commented:
hihi good morning

in a race against the clock again this morning as I'm still racing to do other assignments due... so i actually didn't get to change/fix as much as i wanted to

after Tuesday i should have a little bit a free time so i'll be stopping by here to reread comments and stuff, just learn what i can out of all this and close up topic

really wanna see what you coded but i don't wanna get sucked in cuz i have no time =P

thanks again!
nocturn4lAuthor Commented:
Hey long time, just wanted to close up this topic as I kept this topic up alot longer than intended

Admittingly I still haven't been able to go over the code you wrote phoffric though I still plan to when I do have some time (you know how college is i'm sure.. time is precious!), i'll prob email you bout it too

Again I wanted to say thanks so much for the time and effort you put into helping me with this.  I subscribe to this site because of members like you and others who are so dedicated, thanks!
phoffric\Commented:
Glad to have helped. You gave it the college try and came out OK! You did the work yourself with me just giving you a nudge here and there. Let me know what comments the teacher leaves you on this assignment. If you have any questions about them, please do not hesitate to bring them up if you wish before going back to the teacher. The point now is to learn what you can and to learn how to learn. The latter will last a lifetime.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.