Как вычислить глубину дерева двоичного поиска
Я думаю практика о хранении кода к 80 (или 79), столбцы были первоначально созданы для поддержки людей, редактирующих код простых терминалов на 80 столбцов или распечаток на 80 столбцов. Те, которые требование главным образом ушло теперь, но существуют все еще допустимые причины сохранить правило на 80 столбцов:
- , Чтобы постараться не переноситься при копировании кода в электронную почту, веб-страницы и книги.
- представление To несколько исходных окон бок о бок или использования бок о бок различного средства просмотра.
- Для улучшения удобочитаемости. Узкий код может быть считан быстро, не имея необходимость сканировать Ваши глаза поперек.
я думаю, что последняя точка является самой важной. Хотя дисплеи увеличились в размере и разрешение в последние несколько лет, , глаза не имеют .
6 ответов
Примерно так:
int countChildren(Node node)
{
if ( node == null )
return 0;
return 1 + countChildren(node.getLeft()) + countChildren(node.getRight());
}
И чтобы получить сумму глубин каждого ребенка:
int sumDepthOfAllChildren(Node node, int depth)
{
if ( node == null )
return 0; // starting to see a pattern?
return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) +
sumDepthOfAllChildren(node.getRight(), depth + 1);
}
Теперь, надеюсь, информативное объяснение на случай, если это домашнее задание. Подсчитать количество узлов довольно просто. Прежде всего, если узел не является узлом ( node == null ), он возвращает 0. Если это узел, он сначала считает себя ( 1 ), плюс количество узлов в его левом поддереве плюс количество узлов в его правом поддереве. Другой способ думать об этом - вы посещаете каждый узел через BFS и добавляете единицу к счету для каждого посещаемого вами узла.
Суммирование глубин аналогично, за исключением того, что вместо добавления только одного для каждого узла узел добавляет глубина самого себя. И он знает глубину своего «я», потому что ему сказал его родитель. Каждый узел знает, что глубина его дочерних элементов - это он. s собственная глубина плюс единица, поэтому, когда вы получаете глубину левого и правого потомков узла, вы говорите им, что их глубина равна глубине текущего узла плюс 1.
И снова, если узел не является узлом, в нем нет глубины. Поэтому, если вам нужна сумма глубины всех дочерних узлов корневого узла, вы передаете глубину корневого узла и корневого узла следующим образом: sumDepthOfAllChildren (root, 0)
Рекурсия весьма полезна, это просто совершенно другой способ мышления о вещах и требует практики, чтобы к нему привыкнуть
Для любого данного дерева количество узлов равно 1 для корня плюс количество узлов в левом поддереве плюс количество узлов в правом поддереве :)
Подробности, например убедившись, что на самом деле является левым или правым поддеревом, «оставлены читателю».
public class Node {
private Node left;
private Node right;
public int size() { return 1+ (left==null?0:left.size())+ (right==null?0:right.size());}
}
public int numberOfNodes()
{
// This node.
int result = 1;
// Plus all the nodes from the left node.
Node left = getLeft();
if (left != null)
result += left.numberOfNodes();
// Plus all the nodes from the right node.
Node right = getRight();
if (right != null)
result += right.numberOfNodes();
return result;
}
public int countNodes(Node root)
{
// Setup
// assign to temps to avoid double call accessors.
Node left = root.getLeft();
Node right = root.getRight();
int count = 1; // count THIS node.
// count subtrees
if (left != null) count += countNodes(left);
if (right != null) count += countNodes(right);
return count;
}
private static int getNumberOfNodes(Node node) {
if (node == null) {
return 0;
}
return 1 + getNumberOfNodes(node.left) + getNumberOfNodes(node.right);
}