I have to make a programm that counts the nodes bigger than their sons without including the leaf nodes for example:
JavaScript
x
4 For this tree, the solution would be 4 because is greater than its son 3 but
3 is not counted
3
This is my approach:
JavaScript
//Result2 is a class that stores a T value (info of the node) and n (counter) to
// count the nodes that are bigger than it's sons, this is a method into the class of
//the node that is a generic class of binary nodes for trees (left, right and info
//parameters)
public Result2<T> countBigger()
{
Result2<T> result = new Result2<T>();
result.info = this.info;
if(this.isLeaf())
{
result.n = 0;
}
else
{
Result2<T> resultL = new Result2<T>();
Result2<T> resultR = new Result2<T>();
if(this.hasLeft())
{
resultL = this.left.countBigger();
}
else
{
resultL.info = this.info;
}
if(this.hasRight())
{
resultR = this.right.countBigger();
}
else
{
resultR.info = this.info;
}
if(result.info.compareTo(resultL.info) > 0 & result.info.compareTo(resultR.info) > 0)
{
result.n++;
}
result.n = result.n + resultL.n + resultR.n;
}
return result;
}
But I can’t see the error
Advertisement
Answer
Assuming info is an int, this could work for you. I haven’t tested the code, so let me know if there are issues.
JavaScript
public Result2<T> countBigger() {
Result2 <T> result = new Result2<T>();
result.info = this.info;
if (this.isLeaf()) {
result.n = 0;
} else {
Result2<T> resultL;
Result2<T> resultR;
if (this.hasLeft()) {
resultL = this.left.countBigger();
}
if (this.hasRight()) {
resultR = this.right.countBigger();
}
//if resultL/resultR is not set, then there are no children.
int left = (resultL != null) ? resultL.info ? 0;
int right = (resultR != null) ? resultR.info ? 0;
// if parent.info is bigger than both child's info combined, add 1
// if you want to cout it seprately, then use (result.info > left && result.info > right)
if (result.info > (left + right)) {
result.n++;
}
//Add the counter from child results if they are not null
result.n += (resultL != null) ? resultL.n : 0;
result.n += (resultR != null) ? resultR.n : 0;
}
return result;
}