2
votes

Comprendre le comptage des arbres de recherche binaire

J'ai du mal à comprendre comment cette méthode d'arbre de recherche binaire compte les nœuds, j'ai regardé de nombreux exemples en ligne, mais je n'en trouve pas qui explique exactement ce qui se passe.

Voici un exemple: p >

int CountNodes(node*root)
{
if(root==NULL)
    return 0;
if(root->left!=NULL)
{
    n=n+1;
    n=CountNodes(root->left);
}
if(root->right!=NULL)
{
    n=n+1;
    n=CountNodes(root->right);
}
return n;
}

C'est ainsi que je comprends le processus de cette méthode, et peut-être que quelqu'un peut m'aider à comprendre où je me trompe.

La méthode est appelée de l'extérieur d'elle-même à partir d'un objet BTS; "tree.nodes () etc".
int leftNodes est déclaré et mis à 0.
S'il y a un nœud gauche (supposons qu'il y en ait un), alors la valeur de leftNodes sera affectée à la valeur de retour de l'appel aux nœuds ();
L'appel récursif passera à nouveau par la méthode des nœuds, en attribuant à nouveau leftNodes à zéro.

Donc, ce que je ne comprends pas, c'est où la variable leftNodes est incrémentée? Il semble que cela ne fait que récurer à nouveau dans la méthode, mais la valeur ne change pas, et de la façon dont je vois leftNodes et rightNodes seront toujours 0.

J'ai trouvé un autre exemple de comptage BTS, celui-ci utilisant C ++

public int nodes() {
    int leftNodes = 0;

    if (left != null) {
        leftNodes = left.nodes();
    }
    int rightNodes = 0;

    if (right != null) {
        rightNodes = right.nodes();
    }
    return leftNodes + rightNodes + 1;
}

Je trouve cette méthode beaucoup plus facile à suivre, car n est clairement incrémenté à chaque fois qu'un nœud est trouvé.

Ma question est de savoir comment est le leftNodes / rightNodes valeur incrémentée dans l'appel récursif?

java recursion dynamic-programming binary-search-tree

1 commentaires

La partie + 1 est le cas de base pour la gauche, la droite et le courant. il est appelé une fois pour chaque nœud du sous-arbre, ce qui donne le nombre total de nœuds du sous-arbre. Et dans le cas où gauche ou droite est nul, il renvoie simplement 0 pour la gauche ou la droite.

3 Réponses :

3
votes

Vous devriez penser à la fin de la récursivité.

Supposons que vous ayez un seul nœud sans enfants.

Les deux gauche et droite code > serait null , donc vous ne ferez aucun appel récursif.

Vous retournerez

leftNodes + rightNodes + 1; // 1 + 1 + 1 == 3

Maintenant, supposons que vous avoir un arbre simple qui se compose d'une racine, un enfant gauche et un enfant droit.

Lorsque vous appelez nodes () pour la racine de cet arbre, les deux left et right ne sont pas nuls, nous appellerons donc à la fois left.nodes () et right.nodes () . Comme les enfants gauche et droit sont des nœuds feuilles (c'est-à-dire qu'ils n'ont pas d'enfants), les appels récursifs pour les deux renverront 1, comme expliqué ci-dessus.

Par conséquent, lorsque les appels récursifs reviendront, nous retournerons

leftNodes + rightNodes + 1; // 0 + 0 + 1 == 1

qui est le nombre de nœuds dans notre arbre.

0 commentaires

1
votes

Il s'agit d'une implémentation basique de inorder traversal . Pour chaque nœud, il va à l'enfant gauche jusqu'à ce qu'il ne reste plus d'enfant gauche (à cause de la récursivité, pensez comme à chaque visite d'un nœud, il est poussé vers une pile). Ensuite, il répète la même procédure pour le haut de la pile jusqu'à ce qu'il n'y ait plus d'élément dans la pile (notez encore que, Stack est utilisé pour simplifier les choses par rapport à la récursivité). Ce faisant, il incrémente fondamentalement la somme totale de un pour chaque nœud qu'il visite.

0 commentaires

2
votes

Les variables leftNodes et rightNodes sont locales à la méthode nodes () ce qui signifie qu'il existe une instance différente de ces variables pour chacun appel de la méthode.

Ainsi, lorsque vous appelez récursivement la méthode (avec left.nodes () par exemple), la valeur de leftNodes est la même avant et après l'appel récursif car elle (l'appel) aura une instance de leftNodes (et rightNodes ).

0 commentaires