Подтвердить что ты не робот

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

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

Внедрить метод 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, Тони

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ответ 2

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

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

Если вам нужно более эффективное или более элегантное решение, естественно, зависит от размера ваших деревьев и от того, как часто вы собираетесь использовать эту процедуру. Ремеммер, что сказал Хоар: "преждевременная оптимизация - это корень всего зла".

Ответ 3

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

счетчик возврата для остатка + счетчик для 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 теперь почти часть языка.:)

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

Тони: Интересно, как вы ответили в интервью.

Ответ 4

Что-то вроде этого должно работать:

int count()
{
    int left = getLeftChild() == null ? 0 : getLeftChild().count();
    int right = getRightChild() == null ? 0 : getRightCHild().count();

    return left + right + 1;
}

Ответ 5

return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;

Или что-то в этом роде.

Ответ 6

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

Ответ 7

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

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

Ответ 8

Внедрите метод:

public static int countOneChild(Node root)
{
    ...
}

который подсчитывает количество внутренних узлов в двоичном дереве, имеющем один дочерний элемент. Добавьте функцию в программу tree.java.

Ответ 9

Я сделал это путем рекурсии предварительного заказа. Хотя он точно не соответствует формату интервью, используя 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);
}

Ответ 10

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

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

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

Ответ 11

int count()

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

}

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

EDIT: Я действительно сделал.

Ответ 12

Конечно, если вы хотите не посещать каждый 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

Ответ 13

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

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

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

Ответ 15

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