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

Question

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

Реализуйте метод count (), который возвращает количество узлов в дереве. Если у узла нет ни левого, ни правого дочернего элемента, соответствующий метод getXXChild() вернет null

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
    // Implement me
  }
}

Моя причина задать вопрос просто любопытно увидеть правильное решение и тем самым измерить, насколько плохой был мой.

Ура, Tony

Answer 1

Вопросы, связанные с бинарным деревом, следует ожидать в интервью. Я бы сказал, что нужно уделить время перед любым следующим собеседованием и пройти по этой ссылке. Решено около 14 проблем. Вы можете посмотреть, как это делается. Это даст вам представление о том, как решить проблему с двоичным деревом в будущем.

Я знаю, что ваш вопрос относится к методу подсчета. Он также реализован в ссылке, которую я предоставил

Answer 2

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

Answer 3

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

1. Иметь число int в каждом узле, инициализируется одним, который представляет количество узлов в поддерево коренится в этом узле.

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

Answer 4

int count()

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

}

Боже, надеюсь, я не ошибся.

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

Answer 5

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

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

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