I have to make a programm that counts the nodes bigger than their sons without including the leaf nodes for example:
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:
//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.
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; }