Нахождение высоты в Дереве двоичного поиска
Я задавался вопросом, мог ли кто-либо помочь мне переделать этот метод для нахождения высоты дерева двоичного поиска. До сих пор мой код похож на это. Однако ответ, который я получаю, больше, чем фактическая высота 1. Но когда я удаляю +1 из своих операторов возврата, это - меньше, чем фактическая высота 1. Я все еще пытаюсь перенести голову вокруг рекурсии с ними BST. Любая справка очень ценилась бы.
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;
}
}
5 ответов
Проблема заключается в вашем базовом случае.
«Высота дерева - это длина пути от корня до самого глубокого узла дерева. У (корневого) дерева только один узел (корень) имеет нулевую высоту."- Википедия
Если узла нет, вы хотите вернуть -1, а не 0. Это потому, что вы добавляете 1 в конце.
Итак, если узла нет, вы возвращаете - 1, который отменяет +1.
int findHeight(TreeNode<T> aNode) {
if (aNode == null) {
return -1;
}
int lefth = findHeight(aNode.left);
int righth = findHeight(aNode.right);
if (lefth > righth) {
return lefth + 1;
} else {
return righth + 1;
}
}
Это не проверено, но довольно очевидно верно:
private int findHeight(Treenode aNode) {
if (aNode.left == null && aNode.right == null) {
return 0; // was 1; apparently a node with no children has a height of 0.
} else if (aNode.left == null) {
return 1 + findHeight(aNode.right);
} else if (aNode.right == null) {
return 1 + findHeight(aNode.left);
} else {
return 1 + max(findHeight(aNode.left), findHeight(aNode.right));
}
}
Часто проще упростить код, чем выяснить, почему он не работает по одному. Этот код легко понять: четыре возможных случая явно обрабатываются очевидно правильным образом:
- Если и левое, и правое деревья равны нулю, возвращаем 1, так как единственный узел по определению имеет высоту 1.
- ] Если левое или правое дерево (но не оба!) Равны нулю, вернуть высоту ненулевого дерева плюс 1 для учета добавленной высоты текущего узла.
- Если ни одно дерево не является пустым, вернуть высоту более высокого поддерева, снова плюс один для текущего узла.
На мой взгляд, ваш код можно было бы немного упростить. Вместо того, чтобы пытаться завершить рекурсию, когда указатель child равен нулю, завершайте ее только тогда, когда указатель current равен нулю. Это значительно упрощает написание кода. В псевдокоде это выглядит примерно так:
if (node = null)
return 0;
else
left = height(node->left);
right = height(node->right);
return 1 + max(left, right);
Вот краткий и, надеюсь, правильный способ выразить это:
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;
}
Если текущий узел равен нулю, дерева нет. Если оба дочерних элемента - это один слой, что означает нулевую высоту. Здесь используется определение высоты (упомянутое Стивеном) как количество слоев - 1
Высота двоичного дерева поиска равна количество слоев - 1 .
См. Диаграмму на http://en.wikipedia.org/wiki/Binary_tree
Ваша рекурсия хороша, поэтому просто вычтите единицу на корневом уровне.
Также обратите внимание, что вы можете немного очистить функцию, обработав нулевые узлы:
int findHeight(node) {
if (node == null) return 0;
return 1 + max(findHeight(node.left), findHeight(node.right));
}