Comment calculer la profondeur d'un arbre de recherche binaire

Quelque chose comme ceci:

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

Et pour obtenir la somme des profondeurs de chaque enfant:

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

Maintenant pour un espoir instructif explication dans le cas où ce sont les devoirs. Compter le nombre de nœuds est assez simple. Tout d'abord, si le nœud n'est pas un nœud (node == null) elle retourne 0. Si c'est un noeud, il est d'abord le nombre de ses soi (l' 1), plus le nombre de noeuds à gauche de son sous-arbre, plus le nombre de nœuds dans son droit de sous-arbre. Une autre façon de penser, c'est que vous visitez chaque nœud via BFS, et ajoutez un à l'compter pour chaque nœud que vous visitez.

La Somme des profondeurs est similaire, sauf qu'au lieu d'ajouter un pour chaque nœud, le nœud ajoute la profondeur de son auto. Et il sait la profondeur de son auto parce que ses parents le dit. Chaque nœud sait que la profondeur de ses enfants sont sa propre profondeur, plus un, de sorte que lorsque vous avez la profondeur de la gauche et de la droite, les enfants d'un nœud, vous leur dire que leur profondeur est au courant du nœud de profondeur de plus de 1.

Et encore une fois, si le nœud n'est pas un nœud, il n'a pas de profondeur. Donc, si vous voulez la somme de la profondeur de tous le nœud racine enfants, vous passez dans le nœud racine et le nœud racine de la profondeur de la sorte: sumDepthOfAllChildren(root, 0)

La récursivité est utile, c'est juste une façon différente de penser les choses et faut de la pratique pour s'y habituer

Pour tout arbre, le nombre de nœuds est de 1 pour la racine et le nombre de nœuds du sous-arbre gauche, plus le nombre de nœuds du sous-arbre droit 🙂

Détails, comme vous assurer il ya effectivement est à gauche ou à droite de la sous-arborescence, sont "de gauche " au lecteur".

Cette solution est encore plus simple.

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

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

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