Traversal question
Hello,
I'm have difficulty figuring out a some code to traverse a composite struture that I have created and was hoping someone could point out some code to help me.
I have a class
RightType
-
String name;
String description;
List conditionTypes;
RightsType childRightsType;
The story goes as follows.....
A RightsType may be a parent to many RightType and indeed that child RightType may be a parent to any number of child RightTypes. I am trying to write a function so I can start at the very top or God Parent of the entire structure and work my way down through it printing out the name of each.
Would anyone have idea code examples of how I might do this? Starting for the child and working backwards is not a option for me unfortunately. Therefore pseudo code:
I have a reference to GodRightType
print GodRightType.getName()
for (all childrenOfGodRightType )
print childOfGodRightType.getName()
for (all childrenOf TheirChildrenRightType )
print theirChildrenNames.
The deepth of the struture will always be the same (i.e.) No instance of any one child at a given deep will be the only one to have children. They all will or no will but that's a given.
Any help would be great.
Thanks
[1321 byte] By [
barrytlf] at [2007-9-30 22:30:40]
If the rights do not have any circular definitions, where some node X is a great great grand child of itself, then you have a tree structure.
If it is a tree structure, the standard recursive algorithm for printing trees will work.
You simply include a recursive print routine of the form
public treePrint(){
print(name); // this is some formating routine that could just be System.out.println()
for(each child of this){
child.treePrint()
}
}
Now that simple code will work for trees which by definition have no loops.
If your structure does have loops, it then becomes necessary to mark each element as you output it, so that if you trip over it again in your traversal you will not try to print it (or traverse it) a second time. And then you clean up your marks at the end of the process.
The other thing that this code does not do is allow much flexibility in the output order. If any old order is acceptable, than this is as good as any. If on the other hand you MUST have things in the order suggested by your sketch of an algorithm (where you list god first - then gods immediate children, then all god's grand children before you print a single one of god's great grand children) you will need to do some more work. If you need that probably the simplest coder (not the fastest) is something along these lines.
private static boolean somethingPrinted;
public treePrint(int level){
if(level == 0) { print(name); somethingPrinted = true;}
if(level > 0) {
for(each child of this){
child.treePrint(level-1)
}
}
}
public printAll(){
int level = 0;
somethingPrinted = false;
while(something Printed){
somethingPrinted = false;
treePrint(level);
level++;
}
}
