Wie berechnet sich die Tiefe eines binären Suchbaums

Etwas wie dieses:

int countChildren(Node node)
{
    if ( node == null )
        return 0;
    return 1 + countChildren(node.getLeft()) + countChildren(node.getRight());
}

Und die Summe der tiefen der jedes Kind:

int sumDepthOfAllChildren(Node node, int depth)
{
    if ( node == null )
        return 0;  //starting to see a pattern?
    return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + 
                   sumDepthOfAllChildren(node.getRight(), depth + 1);
}

Nun für eine hoffentlich informative Erklärung in diesem Fall ist Hausaufgaben zu machen. Zählen Sie die Anzahl der Knoten ist ganz einfach. Vor allem, wenn der Knoten ist kein Knoten (node == null) es gibt 0 zurück. Wenn es ein Knoten, erste zählt seine selbst (die 1), plus die Anzahl der Knoten in seinem linken Teilbaum plus die Anzahl der Knoten in seinem rechten Teilbaum. Ein anderer Weg, um daran zu denken ist, die Sie besuchen, jeder Knoten über BFS und hinzufügen, um die Anzahl der für jeden Knoten, den Sie besuchen.

Die Summe der Tiefe ist ähnlich, außer, statt Sie lediglich eine für jeden Knoten, der Knoten fügt die Tiefe des seiner selbst. Und es weiß die Tiefe seiner selbst, weil seine Eltern es gesagt. Jeder Knoten weiß, dass der Tiefe sind es die Kinder sind, es sind eigene Tiefe plus eins, also wenn man die Tiefe der linken und rechten Kinder eines Knotens, die Sie Ihnen sagen, Ihre Tiefe ist der aktuelle Knoten der Tiefe plus 1.

Wieder, wenn der Knoten ist kein Knoten, es hat keine Tiefe. Also, wenn Sie wollen, dass die Summe der Tiefe aller der root-Knoten die Kinder, übergeben Sie den root-Knoten und dem root-Knoten der Tiefe etwa so: sumDepthOfAllChildren(root, 0)

Rekursion ist Recht nützlich, es ist einfach eine ganz andere Art des Denkens über die Dinge und braucht übung, sich daran zu gewöhnen

InformationsquelleAutor der Antwort David Brown

Für einen bestimmten Baum die Anzahl der Knoten ist 1 für die Wurzel und die Anzahl der Knoten im linken Teilbaum plus die Anzahl der Knoten im rechten Teilbaum 🙂

Details, wie Sie sicherstellen, dass es tatsächlich ist einen linken oder rechten Teilbaum, "bleibt dem Leser selbst überlassen".

InformationsquelleAutor der Antwort Carl Smotricz

Diese Lösung ist sogar noch einfacher.

public int getHeight(Node root)
{
    if(root!=null)
        return 1+ Math.max(getHeight(root.leftchild),getHeight(root.rightchild));
    else
        return 0;
}

InformationsquelleAutor der Antwort Soumya Kanti Naskar

int depth(treenode *p)
{
   if(p==NULL)return(0);
   if(p->left){h1=depth(p->left);}
   if(p=>right){h2=depth(p->right);}
   return(max(h1,h2)+1);
}

InformationsquelleAutor der Antwort GoswamiK

public int countNodes(Node root)
{  
   //Setup
   //assign to temps to avoid double call accessors. 
   Node left = root.getLeft();
   Node right = root.getRight();
   int count = 1; //count THIS node.

   //count subtrees
   if (left != null) count += countNodes(left);
   if (right != null) count += countNodes(right);

   return count;
}

InformationsquelleAutor der Antwort Chris Cudmore