Подсчет узлов в дереве в Java

int count()

{
   int retval = 1;
    if(null != getRightChild()) retval+=getRightChild().count();
    if(null != getLeftChild()) retval+=getLeftChild().count();
    return retval;

}

Бог я надеюсь, что не сделал ошибку.

РЕДАКТИРОВАНИЕ: Я сделал на самом деле.

Конечно, если Вы не хотите посещать каждый узел в своем дереве, когда Вы рассчитываете, и время обработки стоит больше Вам, чем память, можно обмануть путем создания количеств, поскольку Вы создаете свое дерево.

1. Имеют международное количество в каждом узле, инициализированном одному, какой respresents количество узлов в поддереве базировалось в том узле.

2. , Когда Вы вставляете узел, прежде, чем возвратиться из Вашей рекурсивной стандартной программы вставки, увеличивают количество в текущем узле.

т.е.

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

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;
}

Это - стандартная проблема рекурсии:

count():
    cnt = 1 // this node
    if (haveRight) cnt += right.count
    if (haveLeft)  cnt += left.count
return cnt;

Очень неэффективный, и уничтожитель, если дерево очень глубоко, но это - рекурсия для Вас...

Можно считать дерево путем пересечения его многие пути . Просто предварительно закажите обход, код был бы (на основе функций, которые Вы определили):

int count() {
    count = 1;
    if (this.getLeftChild() != null)
        count += this.getLeftChild().count();
    if (this.getRightChild() != null)
        count += this.getRightChild().count();
    return count;
}

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()
{
    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;

Или что-то как этот.

Мне нравится это лучше, потому что это читает:

счет возврата оставленного + значат право + 1

  int count() {
      return  countFor( getLeftChild() ) + countFor( getRightChild() ) + 1;
  }
  private int countFor( Tree tree )  { 
       return tree == null ? 0 : tree.count();
  }

Немного больше к грамотному программированию.

BTW, мне не нравится конвенция метода считывания/метода set, которая является таким образом наиболее часто используемая на Java, я думаю использование , leftChild () вместо этого был бы лучше:

  return countFor( leftChild() ) + countFor( rightChild() ) + 1;

Точно так же, как Hoshua Bloch объясняет здесь http://www.youtube.com/watch?v=aAb7hSCtvGw в минуту 32:03

, Если Вы добираетесь, это исправляет Ваши чтения кода...

, НО, я должен признать, что получить/установить конвенция является теперь почти частью языка. :)

Для многих других частей, в соответствии с этой стратегией создает сам документирующий код, который является чем-то хорошим.

Tony: Интересно, каков был Ваш ответ в интервью.

Тривиальное рекурсивное решение:

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;
}

, нужны ли Вам более эффективное или более изящное решение естественно, зависит от размера Ваших деревьев и о том, как часто Вы намереваетесь использовать эту стандартную программу. Rembemer, что сказал Hoare: "преждевременная оптимизация является корнем всего зла".

В моей первой попытке не было ничего нового, что можно было бы добавить, но затем я начал задаваться вопросом о глубине рекурсии и о том, можно ли изменить порядок кода, чтобы воспользоваться функцией оптимизации хвостового вызова последней версии компилятора 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.