Прежде всего, я клянусь, что это не домашнее задание, это вопрос, который меня задали в интервью. Я думаю, что я это испортил (хотя я понял, что решение требует рекурсии). Вот вопрос:
Внедрить метод count(), который возвращает количество узлов в дереве. Если node не имеет ни левого, ни правого дочернего элемента, соответствующий метод getXXChild() возвращает null
class Tree {
Tree getRightChild() {
// Assume this is already implemented
}
Tree getLeftChild() {
// Assume this is already implemented
}
int count() {
// Implement me
}
}
Моя причина задавать вопрос просто любопытно увидеть правильное решение и тем самым измерить, насколько плохой был.
Cheers, Тони
int count() {
Tree right = getRightChild();
Tree left = getLeftChild();
int c = 1; // count yourself!
if ( right != null ) c += right.count(); // count sub trees
if ( left != null ) c += left.count(); // ..
return c;
}
Тривиальное рекурсивное решение:
int count() {
Tree l = getLeftTree();
Tree r = getRightTree();
return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0);
}
Менее тривиальный нерекурсивный:
int count() {
Stack<Tree> s = new Stack<Tree>();
s.push(this);
int cnt = 0;
while (!s.empty()) {
Tree t = s.pop();
cnt++;
Tree ch = getLeftTree();
if (ch != null) s.push(ch);
ch = getRightTree();
if (ch != null) s.push(ch);
}
return cnt;
}
Последний, вероятно, немного более эффективен с точки зрения памяти, поскольку он заменяет рекурсию стеком и итерацией. Это также, вероятно, быстрее, но его трудно сказать без измерений. Ключевым отличием является то, что рекурсивное решение использует стек, в то время как нерекурсивное решение использует кучу для хранения узлов.
Изменить: Здесь вариант итеративного решения, которое использует стек менее тяжело:
int count() {
Tree t = this;
Stack<Tree> s = new Stack<Tree>();
int cnt = 0;
do {
cnt++;
Tree l = t.getLeftTree();
Tree r = t.getRightTree();
if (l != null) {
t = l;
if (r != null) s.push(r);
} else if (r != null) {
t = r;
} else {
t = s.empty() ? null : s.pop();
}
} while (t != null);
return cnt;
}
Если вам нужно более эффективное или более элегантное решение, естественно, зависит от размера ваших деревьев и от того, как часто вы собираетесь использовать эту процедуру. Ремеммер, что сказал Хоар: "преждевременная оптимизация - это корень всего зла".
Мне нравится это лучше, потому что он читает:
счетчик возврата для остатка + счетчик для rigth + 1
int count() {
return countFor( getLeftChild() ) + countFor( getRightChild() ) + 1;
}
private int countFor( Tree tree ) {
return tree == null ? 0 : tree.count();
}
Немного больше к грамотному программированию.
Кстати, мне не нравится соглашение getter/setter, которое обычно используется на Java, я думаю, что использование leftChild() будет лучше:
return countFor( leftChild() ) + countFor( rightChild() ) + 1;
Так же, как Хошуа Блох объясняет здесь http://www.youtube.com/watch?v=aAb7hSCtvGw в мин. 32:03
Если вы получите его, ваш код читает...
НО, я должен признать, что соглашение get/set теперь почти часть языка.:)
Для многих других частей следующая стратегия создает самодокументирующий код, который является чем-то хорошим.
Тони: Интересно, как вы ответили в интервью.
Что-то вроде этого должно работать:
int count()
{
int left = getLeftChild() == null ? 0 : getLeftChild().count();
int right = getRightChild() == null ? 0 : getRightCHild().count();
return left + right + 1;
}
return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;
Или что-то в этом роде.
class Tree {
Tree getRightChild() {
// Assume this is already implemented
}
Tree getLeftChild() {
// Assume this is already implemented
}
int count() {
return 1
+ getRightChild() == null? 0 : getRightChild().count()
+ getLeftChild() == null? 0 : getLeftChild().count();
}
}
Вы можете сосчитать дерево, пройдя через него способы. Просто обход предварительного порядка, код будет (на основе определенных вами функций):
int count() {
count = 1;
if (this.getLeftChild() != null)
count += this.getLeftChild().count();
if (this.getRightChild() != null)
count += this.getRightChild().count();
return count;
}
Внедрите метод:
public static int countOneChild(Node root)
{
...
}
который подсчитывает количество внутренних узлов в двоичном дереве, имеющем один дочерний элемент. Добавьте функцию в программу tree.java.
Я сделал это путем рекурсии предварительного заказа. Хотя он точно не соответствует формату интервью, используя localRoot, но я думаю, что вы поняли эту идею.
private int countNodes(Node<E> localRoot, int count) {
if (localRoot == null)
return count;
count++; // Visit root
count = countNodes(localRoot.left, count); // Preorder-traverse (left)
count = countNodes(localRoot.right, count); // Preorder-traverse (right)
return count;
}
public int countNodes() {
return countNodes(root, 0);
}
Это стандартная проблема рекурсии:
count():
cnt = 1 // this node
if (haveRight) cnt += right.count
if (haveLeft) cnt += left.count
return cnt;
Очень неэффективно и убийца, если дерево очень глубокое, но эта рекурсия для ya...
int count()
{
int retval = 1;
if(null != getRightChild()) retval+=getRightChild().count();
if(null != getLeftChild()) retval+=getLeftChild().count();
return retval;
}
Надеюсь, я не ошибся.
EDIT: Я действительно сделал.
Конечно, если вы хотите не посещать каждый node в своем дереве при подсчете, а время обработки для вас больше, чем память, вы можете обмануть, создав свои счета при создании своего дерева.
Имейте int count в каждом node, инициализируется одним, отображает количество узлов в поддерево, основанное на этом node.
Когда вы вставляете node, перед возврат из вашей рекурсивной вставки подстройте счетчик на текущий node.
то есть.
public void insert(Node root, Node newNode) {
if (newNode.compareTo(root) > 1) {
if (root.right != null)
insert(root.right, newNode);
else
root.right = newNode;
} else {
if (root.left != null)
insert(root.left, newNode);
else
root.left = newNode;
}
root.count++;
}
Тогда получение счета из любой точки просто связано с поиском node.count
У моей первой попытки не было ничего нового для добавления, но потом я начал задаваться вопросом о глубине рекурсии и можно ли переставить код, чтобы воспользоваться функцией оптимизации хвостового вызова последнего компилятора Java. Основной проблемой был нулевой тест, который можно решить с помощью NullObject. Я не уверен, что TCO может иметь дело с обоими рекурсивными вызовами, но она должна хотя бы оптимизировать последний.
static class NullNode extends Tree {
private static final Tree s_instance = new NullNode();
static Tree instance() {
return s_instance;
}
@Override
Tree getRightChild() {
return null;
}
@Override
Tree getLeftChild() {
return null;
}
int count() {
return 0;
}
}
int count() {
Tree right = getRightChild();
Tree left = getLeftChild();
if ( right == null ) { right = NullNode.instance(); }
if ( left == null ) { left = NullNode.instance(); }
return 1 + right.count() + left.count();
}
Точная реализация NullNode зависит от реализаций, используемых в Tree - если Tree использует NullNode вместо null, тогда, возможно, методы доступа к дочернему объекту должны вызывать исключение NullPointerException вместо возврата null. Во всяком случае, основная идея состоит в том, чтобы использовать NullObject, чтобы попытаться получить выгоду от TCO.
Вопросы, связанные с бинарным деревом, следует ожидать в интервью. Я бы сказал, чтобы уделить время перед любым следующим интервью и перейти через эту ссылку. Решено около 14 проблем. Вы можете посмотреть и как это сделать. Это даст вам представление о том, как в будущем решить проблему с бинарным деревом.
Я знаю, что ваш вопрос специфичен для метода count. Это также реализовано в ссылке, которую я предоставил
class Tree {
Tree getRightChild() {
// Assume this is already implemented
}
Tree getLeftChild() {
// Assume this is already implemented
}
int count() {
if(this.getLeftChild() !=null && this.getRightChild()!=null)
return 1 + this.getLeftChild().count() + this.getRightChild().count();
elseif(this.getLeftChild() !=null && this.getRightChild()==null)
return 1 + this.getLeftChild().count();
elseif(this.getLeftChild() ==null && this.getRightChild()!=null)
return 1 + this.getRightChild().count();
else return 1;//left & right sub trees are null ==> count the root node
}
}