Ich frage mich, ob mir jemand helfen kann, diese Methode zu überarbeiten, um die Höhe eines binären Suchbaums zu finden. Bis jetzt sieht mein Code so aus. Allerdings ist die Antwort, die ich bekomme, um 1 größer als die tatsächliche Höhe. Aber wenn ich die +1 aus meinen Rückgabeanweisungen entferne, ist es weniger als die tatsächliche Höhe um 1. Ich versuche immer noch, meinen Kopf um Rekursion mit diesen BST zu wickeln. Jede Hilfe würde sehr geschätzt werden.
public int findHeight(){
if(this.isEmpty()){
return 0;
}
else{
TreeNode<T> node = root;
return findHeight(node);
}
}
private int findHeight(TreeNode<T> aNode){
int heightLeft = 0;
int heightRight = 0;
if(aNode.left!=null)
heightLeft = findHeight(aNode.left);
if(aNode.right!=null)
heightRight = findHeight(aNode.right);
if(heightLeft > heightRight){
return heightLeft+1;
}
else{
return heightRight+1;
}
}
Die Höhe eines binären Suchbaums ist gleich der "Anzahl der Ebenen - 1".
Siehe das Diagramm unter http://en.wikipedia.org/wiki/Binary_tree
Ihre Rekursion ist gut, also ziehen Sie einfach auf der Wurzelebene eins ab.
Beachten Sie auch, dass Sie die Funktion ein wenig aufräumen können, indem Sie Null-Knoten behandeln:
int findHeight(node) {
if (node == null) return 0;
return 1 + max(findHeight(node.left), findHeight(node.right));
}
Meiner Meinung nach würde Ihr Code davon profitieren, etwas vereinfacht zu werden. Anstatt zu versuchen, die Rekursion zu beenden, wenn ein child-Zeiger null ist, sollten Sie sie nur beenden, wenn der current-Zeiger null ist. Das macht den Code viel einfacher zu schreiben. In Pseudocode sieht er etwa so aus:
if (node = null)
return 0;
else
left = height(node->left);
right = height(node->right);
return 1 + max(left, right);
Hier ist eine knappe und hoffentlich korrekte Formulierung:
private int findHeight(TreeNode<T> aNode){
if(aNode == null || (aNode.left == null && aNode.right == null))
return 0;
return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
}
Wenn der aktuelle Knoten Null ist, gibt es keinen Baum. Wenn beide Kinder null sind, gibt es eine einzige Ebene, was 0 Höhe bedeutet. Dies verwendet die (von Stephen erwähnte) Definition von height als # of layers - 1