i need help in working with trees, how to actually do it, or what do i need to do it, im not asking for codes, but ideas... and maybe links that will help me... im doing my own research but ur help is very appretiated
i need to implement a tree.. no GUI, its like having lists inside a list, and inside those lists there shall be another lists (strings)!!! im really struggling to guess how can that be done! i know i will be using collections, but is there a particuler method that helps to add a list inside another? i read the ADT but still didnt do much... ahh
A simple example node for a binary tree might look like this:
Then you would have some Tree class that would use these nodes to perform operations such as search, pre/post traversal. Some people would make the Node class an inner class of the Tree, I personally don't really like that approach.
Hope that helps.
but that mean i will only have 2 children attached to each parent, but what i need is a parent node that can have many children all in one level below it, and i should be able to make any of them a parent of another list!
i could use a linkedList to store children of one parent, but the problem is with making the children parents!! which means i need to link the 2 lists
Something that looks like this... any help
[ March 25, 2005: Message edited by: H Melua ]
Here's a simple example where each tree node has either a value or children, but never both. Supporting both would require creating a TreeNode class to hold a String and a List.When you access an element of a List using get(index), you can test the returned Object to see if it's another List or a value (String) that you're storing in the tree. If you enforce some structure (or in the case above where you already know), you can make assumptions.In a binary search tree, you use the ordering of the elements to determine how to build the structure of the tree. For example, starting with this tree,inserting the value 5 will create a new node as the left child of 6 to hold it.How will you specify where values should be stored in your tree if each node can have an unlimited number of children?
yes i can use collections...now i can start imagining how it can be done .. wellllll thats a good question :roll: .... i guess it will be using the name i specify, so i'll do a little search and when i find the specified name i can then add another value to it...
oh my life, iterating through this will be a killer!!
i'll have a go at programming this and i'll c how it goes, i thank u lot so much..
ive got a problem with this code,
this code gives me incompatible type error, and i understand y
if i change it to then it works, but would it create a problem for me in the future since house1 will always be of type House? is defining house1 as object means house1 can be either a House or any other object?
OK ive solved this problem, but it might be slightly imperfessional! so what do u lot think?
ArrayList house = (ArrayList)house1;
is it actually doing what i want?
[ March 26, 2005: Message edited by: H Melua ]
Since addFive() operated on its local copy, the x inside addAndPrint() is unaffected. Thus, it prints 10.
Having said that, the first thing to address is what House is. I assume you have defined a House class. If so, can you post it? Is House the TreeNode I described above? Does it hold a String and an ArrayList of children? If so, you need to add a method to House called add() that will add a given House as its child.
Your use of a method outside the House class -- addToHouse() -- is what's known as procedural programming. You have a method that lives off on its own that you give arguments on which it does its work. One of the major points of object oriented programming is encapsulation: combining data with the operations (methods) to act upon the data.
Instead of addToHouse(), create an add(House) method in the House class itself. You might also want to start by writing a one or two paragraph description of what a House represents and what it can do. This will serve as a good starting point for creating the methods House will need.
Here's an example using a Person class.
A Person has a name and age. Each Person has two parents (Person), either of which can be null if unknown, and zero or one spouse (Person). A Person also maintains a List of its children (each a Person).As you can see from the example, it's not always clear where responsibilities lie. A method like marry(Person) could arguably belong to a different helper class since it operates on two people equally (one Person doesn't have all the responsibility since they both marry each other). However, it's generally easier to start this way to enforce encapsulation.
The method more applicable to your code would be getChildrenCount() and addChild(). Notice that the Person class has sole responsibility for managing the List of children.
and thank u very much david
ok thats what i did so far.. the problem is that im not thinking to the future! and whether it will be possible for me since im not very knowlegdeable in java to do what i want to do!
i wish to know, if what im doing is at least abit right? if i solve the problem of iterating will this code be ok? and regarding the find method, is it going to be ok to iterate throught a list of house children and house lists (parents)? :roll:
i honestly dont know if its supposed to hold a string and its list, i asked my lecturer and he said i cant tell u this then i'll be doing most of the work for u!!! hes like that i dont ever ask him cus hes useless!!
im assuming that the name of the list is basically the parent name i need, and so if u look back at my diagram, e.g. laura is going to be a list and the name laura will be name i search for if i want to add any child to it.. if thats possible!
i cant wait till the 12 of june, i'll be done and sleeping at home
would it be better if i have for example a class that creates a child, another class that creates a parent and another class that creates the list of parents? or would keeping mine be ok?!
If you clear that up and explain exactly what iteration is supposed to do (iterate the whole tree or just a single House's children?), I can help further.
I recall this attitude from professors in beginning classes. They forget that it really isn't that easy when you're starting and focus on one small piece of the design which they feel is 90% of the effort -- making a single decision about the structure of a class!
i honestly dont know if its supposed to hold a string and its list, i asked my lecturer and he said i cant tell u this then i'll be doing most of the work for u!!!
In any case, the Collections framework has a binary tree implementation, TreeSet, that you could look at for ideas. Make a case for both ways and see which makes more sense to you. Often in school exercises, you can go the simpler route that is less flexible because flexibility isn't the point of the problem -- it's to learn how trees work, for example.
Also, I've got a few pointers if you'd like. It's a good practice to use the Collections interfaces in type declarations when possible, specifying the exact implementation only when creating it. This makes it much easier to change from ArrayList to LinkedList later.
Perhaps name one house "parent" and the other "child" so the caller knows which is which. Also, I'm unclear what the second method does. The comment makes it sound like they're the same method. Does the second one add multiple houses to house2? Or is the ArrayList house1's list of children?
public boolean addToHouse(House house1, House house2);
public boolean addToHouse(ArrayList house1, House house2);
Make sure to override equals(Object) for TheHouse so that houseList.contains(house) will work. I assume two houses are equal if they have the same name. If not, and two houses are equal only when they are the same instance, ignore this paragraph. Object.equals(Object) does the latter for you.
A single class will usually have multiple methods that make up one or a few coarse responsibilities. Especially in the beginning, don't over-emphasize cohesion (few responsibilities) or you end up with a whole bunch of entangled classes that are harder to understand than one or two larger classes.
Originally posted by H Melua:
making the House creates the children, and the houselist makes them parents and adds some of those children to the parents created, and that is making houselist in charge of 2 major functions!!
Can you briefly summarize the requirements for the assignment? Given them, what responsibilities must House have?
basically, we can look it that way, its nothing to do with houses, but thats like a demo..
i can add an area which will hold set of houses, and i can add a house to an area, i can also add to the house a number of people who live there.. and keep on extending it... and to be able to add anything, i'll have to find where to add it (and so search the whole tree) and check if its not there already..
what the 2nd addToHouse(ArrayList...) does, it takes in a list which is little subtree and adds a child to it or can actually be a list itself!!! << in this case i'll need a third method that takes in 2 ArrayLists!
we should be able to add for example, the subtree "someArea" to the subtree "YourArea", and we should be able to add "TheirChild" to the subTree "MyParents", and so on of that..
thats what i need for now.. but its honestly way bigger than that
the problem with treeSet is that it is a set, and i want a list, im allowed to have dublicate values there, so i can have "You" in "YourArea" & "someArea" meaning "you" can have more than1 house!
[ March 27, 2005: Message edited by: H Melua ]
not any1 can be a lecturer!
Basically, a generic tree can be constructed with a Tree class for the main operations (add, remove, find, etc) and a TreeNode to represent a single item in a tree along with that item's children. The Tree also has a reference to the root TreeNode. Each node maintains a List of its children.
You can have TreeNode manage its list of children, or the Tree class can do all the work.
Do you really need to model House (and Company, Area, and Person) or can you use a String to represent them? In other words, can you simply store the String "MyParents" in the list as a child of the node that contains the String "MyArea", or do you actually need to be able to grab the item named "MyParents" and check that it's a House?
Basically, it seems to me that your overcomplicating it by adding details not in the original assignment, but I can only guess. Are you supposed to do more than implement a tree class? I see you've implemented Comparable which is useful for sorting; is this related?
not really i dont need to sort it but he said u can use it if u wish to and sort the list, im not worried about that..
what is confusing me is that, when i do find(), wouldnt it have a problem when it looks throught objects of type House and suddently it finds it mixed with ArrayLists?
i imagin it to be like this
so the name of the arrayList is a group of houses, and if i contact the ArrayList it means it will contact all the once bellow it...
ok can i send u a private letter on this?
[ March 27, 2005: Message edited by: H Melua ]
This is the reason you must override equals(Object) in the House class. The House "this" is equal to the passed in Object only if
Originally posted by H Melua:
when i do find(), wouldnt it have a problem when it looks throught objects of type House and suddently it finds it mixed with ArrayLists?
One question, though: How will you locate an ArrayList since they don't have names?
I prefer to keep it public so others that search the forums can learn as well, but if you want to send me a private message, that's fine.
ok can i send u a private letter on this?