[CS] General Trees and Height

D

Durak

Veteran XV
sup noobs, I'm implementing a General Tree in java and I need a function for height.

I thought this one would work:

Code: 
   public static int height(TreeNode t){
    	if (t == null) return -1; //no height
    	if (isLeaf(t))  return 0; //if you can't go down or right anymore
	else return 1 + Math.max(height(t.getFirstSub()), height(t.getNextSub()));
	
    }

But it only gets the left most subtree's height. If the height on one of the subtrees to the right is greater, it doesn't count that for some reason....

Thanks.
 
Is this a binary tree? Or by general tree do you mean a node can have 0-n children?

If it's a binary tree, your algorithm seems good, so I'd check t.getFirstSub(), t.getNextSub() if you wrote these.

What class is this for anyway?
 
Wait, I take the algorithm comment back.
I think it should be

if (t == null) return 0;
if (isLeaf(t)) return 1;

I'm assuming at this point we're talking about a binary tree.
 
Shouldn't you be finding the Math.max(goleft, go right)?

Maybe that's what you're doing, but I'm not sure what firstsub and nextsub are.
 
bonafide said:
Wait, I take the algorithm comment back.
I think it should be

if (t == null) return 0;
if (isLeaf(t)) return 1;

I'm assuming at this point we're talking about a binary tree.
Click to expand...
If that's the problem then his answer should be off by 1 all the time, since it wouldn't count any of the leaves.

Edit: Or off by two I guess since it subtracts 1 for each of the null spots.
 
Yeah, that's why I think the firstSub functions are borked.

The results before the numbers are fixed will be worse than off by just 1 I think.
 
Actually, this works. It was just that both my left and right subtrees were the same height when I thought they weren't. Yes it's a general tree, but anyways, the search function should be the same since the general tree implementation is done by a pseudo-binary tree.
 
Hey, I still need implement a postorder print for a general tree

Anyone got ideas about that shit? I have completed the preorder traversal function. What would be the difference between these two functions? Is there some way I could utilize the code from preorder for the post order?

Thanks.

Thanks.
 
What candy assed CS class is this for?

Post order is Left, Right, Root.

Code: 
RECURSIVE( tree node) {

if tree node not null {

 Recursive(left child)
 Recursive(right child)

 print node value;
}

}

This pseudocode should get you started.

BTW, do your own fucking homework.
 
bonafide said:
What candy assed CS class is this for?

Post order is Left, Right, Root.


This pseudocode should get you started.

BTW, do your own fucking homework.
Click to expand...

Alright I got it, thx :D


Ps. this is for a college level 2 CS course. This is not exactly the assignment. The actual assignment is to parse an XML file and convert it to HTML with general trees. I was just confused on the post order. Thx :D
 
bonafide said:
NP. CS211 was a lot fucking harder when I took it.
Click to expand...

This is actually pretty difficult. It's not just a post order traversal, you gotta add the appropriate html code in as well. There's alot more shit to figure out.
 
For our final project we pretty much had to write a fully functional Java version of Excel, complete with a GUI, cell equations, etc.

Both Prof. Pengali and that class can burn in hell for making my frosh year suck ass.
 
You must log in or register to reply here.
Back
Top