wake-up-neo.net

Zählen von Knoten in einem Baum in Java

Zunächst schwöre ich, dass dies keine Hausaufgaben sind, sondern eine Frage, die mir in einem Interview gestellt wurde. Ich glaube, ich habe ein Chaos daraus gemacht (obwohl mir klar war, dass die Lösung eine Rekursion erfordert). Hier ist die Frage:

Implementieren Sie die Methode count (), die die Anzahl der Knoten in einer Baumstruktur zurückgibt. Wenn ein Knoten weder ein linkes noch ein rechtes untergeordnetes Element hat, gibt die entsprechende getXXChild()-Methode null zurück.

class Tree {

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

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

  int count() {
    // Implement me
  }
}

Mein Grund, die Frage zu stellen, ist einfach neugierig auf die richtige Lösung, um zu messen, wie schlecht meine war.

Prost, Tony

20
Tony
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;
}
32
Blorgbeard

Eine triviale rekursive Lösung:

int count() {
   Tree l = getLeftTree();
   Tree r = getRightTree();
   return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0);
}

Ein weniger trivialer, nicht rekursiver:

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

Letzteres ist wahrscheinlich etwas speichereffizienter, weil es Rekursion durch einen Stapel und eine Iteration ersetzt. Es ist wahrscheinlich auch schneller, aber ohne Messungen ist es schwer zu sagen. Ein wesentlicher Unterschied besteht darin, dass die rekursive Lösung den Stack verwendet, während die nichtrekursive Lösung den Heap zum Speichern der Knoten verwendet.

Edit: Hier ist eine Variante der iterativen Lösung, die den Stack weniger stark beansprucht:

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

Ob Sie eine effizientere oder elegantere Lösung benötigen, hängt natürlich von der Größe Ihrer Bäume und davon ab, wie oft Sie diese Routine verwenden möchten. Rembemer, was Hoare sagte: "vorzeitige Optimierung ist die Wurzel allen Übels."

19
David Hanak

Ich mag das besser, weil es liest:

zurückzählen für links + zählen für rechts + 1  

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

Ein bisschen mehr in Richtung gebildete Programmierung.

Übrigens, ich mag die Getter/Setter-Konvention, die so häufig auf Java verwendet wird, nicht. Ich denke, eine Verwendung von leftChild () wäre besser:

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

Genau wie Hoshua Bloch hier erklärt http://www.youtube.com/watch?v=aAb7hSCtvGw bei min. 32:03

Wenn Sie es richtig bekommen, liest Ihr Code ...

ABER, ich muss zugeben, dass die get/set-Konvention jetzt fast ein Teil der Sprache ist. :) 

Für viele andere Bereiche wird durch die Einhaltung dieser Strategie selbstdokumentierender Code erstellt, was etwas Gutes ist.

Tony: Ich frage mich, was war Ihre Antwort im Interview.

11
OscarRyz

So etwas sollte funktionieren:

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

    return left + right + 1;
}
4
return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;

Oder sowas ähnliches.

4
Steven Robbins
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();
  }
}
4
user66322

Implementiere die Methode:

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

das zählt die Anzahl der internen Knoten in einem binären Baum mit einem Kind. Fügen Sie die Funktion zum tree.Java-Programm hinzu.

2
morad nanz

Sie können den Baum zählen, indem Sie viele Möglichkeiten durchlaufen. Einfach vorbestellen, wäre der Code (basierend auf den von Ihnen definierten Funktionen):

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

Ich habe es durch Rekursion vorbestellt. Es folgt zwar nicht genau dem Interviewformat mit localRoot, aber ich denke, dass Sie die Idee bekommen.

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);
}
1
Tiago Redaelli

Dies ist ein Standardrekursionsproblem:

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

Sehr ineffizient und ein Killer, wenn der Baum sehr tief ist, aber das ist eine Rekursion für ...

0
Jeff Kotula

Wenn Sie vermeiden möchten, jeden Knoten in Ihrem Baum zu besuchen, während Sie zählen, und die Verarbeitungszeit für Sie mehr wert ist als Speicher, können Sie natürlich schummeln, indem Sie beim Erstellen Ihres Baums Ihre Anzahl erstellen.

  1. Haben Sie in jedem Knoten eine Int-Zahl, , Die auf Eins initialisiert ist, wobei Die Anzahl der Knoten in Des in diesem Knoten verwurzelten Teilbaums darstellt.

  2. Wenn Sie einen Knoten einfügen, bevor Von Ihrer Routine rekursives Einfügen Zurückkehrt, erhöhen Sie den Zählerstand am aktuellen Knoten .

d.h. 

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

Wenn Sie die Zählung von einem beliebigen Punkt abrufen, müssen Sie lediglich node.count nachschlagen

0
Ben Hardy
int count()

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

}

Ich hoffe, ich habe keinen Fehler gemacht.

EDIT: Ich habe es tatsächlich getan.

0
mannicken

Fragen zum Binärbaum sollten in einem Interview erwartet werden. Ich würde sagen, nehmen Sie sich vor jedem nächsten Interview Zeit und gehen Sie durch this link. Es wurden ungefähr 14 Probleme gelöst. Sie können sehen, wie die Lösung durchgeführt wird. Dies gibt Ihnen eine Vorstellung davon, wie Sie in Zukunft ein Problem mit dem Binärbaum lösen können.

Ich weiß, dass Ihre Frage spezifisch für die Count-Methode ist. Dies ist auch in dem von mir bereitgestellten Link implementiert

0
Barry

Mein erster Versuch hatte nichts Neues hinzuzufügen, aber dann begann ich mich über die Rekursionstiefe zu wundern und ob es möglich ist, den Code neu zu ordnen, um die Rückrufoptimierungsfunktion des neuesten Java-Compilers zu nutzen. Das Hauptproblem war der Nulltest - der mit einem NullObject gelöst werden kann. Ich bin nicht sicher, ob TCO beide rekursiven Anrufe verarbeiten kann, aber es sollte zumindest die letzten optimieren.

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

Die genaue Implementierung von NullNode hängt von den in Tree verwendeten Implementierungen ab. Wenn Tree NullNode anstelle von Null verwendet, sollten die untergeordneten Zugriffsmethoden möglicherweise NullPointerException auslösen, anstatt Null zurückzugeben. Die Hauptidee ist jedoch, ein NullObject zu verwenden, um zu versuchen, von den TCO zu profitieren.

0
richj
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
  }
}
0
amu