Et, enfin, la fonction principale de la construction de l'arbre suivant, qui couvre l'ensemble de la validité de possibilités (vide nœud, nœud avec deux enfants, nœud, sans enfants, nœud avec un droit à l'enfant et à nœud avec un gauche de l'enfant):
10/ \
720/ \
399
\
4
\
6
Le code pour construire l'arbre et le rapport de la somme à différents points est indiquée ici:
int main (void){//Empty tree first.
tNode *root =0;
std::cout << sum (root)<<'\n';//Then a tree with single node (10).
root = addNode (0,' ',10);
std::cout << sum (root)<<'\n';//Then one with two subnodes (10, 7, 20).
addNode (root,'L',7);
addNode (root,'R',20);
std::cout << sum (root)<<'\n';//Then, finally, the full tree as per above.
addNode (root->left,'L',3);
addNode (root->left->left,'R',4);
addNode (root->left->left->right,'R',6);
addNode (root->right,'R',99);
std::cout << sum (root)<<'\n';return0;}
Ce sorties (la bonne):
01037149
ne pas la dernière ligne de retour de la somme(noeud->gauche) + somme(node->droite) + node->val; Oui, m'a pris à la mi-edit. Je venais juste de se demander où est la valeur du nœud actuel a été en provenance de... Fixe maintenant 🙂 Merci beaucoup Paxdiablo. Btw, c'est un algorithme O(n) droit? Depuis qu'il visite chacune des n nœuds qu'une seule fois. Oui, il est O(n). J'ai dû penser à ce sujet depuis des arbres binaires sont normalement O(log n), mais c'est pour une recherche, pas de récupération. La traversée de chaque nœud est en effet O(n).
De la même manière que la recherche de l'arbre, ou l'affichage de chaque nœud, ou de tout autre arbre à l'échelle de l'opération: visite du nœud actuel, visite de la gauche du sous-arbre (de manière récursive), et de visiter le droit de sous-arbre (de manière récursive).
Essentiellement, quelque chose comme ceci:
intTreeNode::calculateSum()const{int sum =this->value;if(this->left != NULL) sum +=this->left ->calculateSum();if(this->right != NULL) sum +=this->right->calculateSum();return sum;}
En raison de la if vérifie la récursivité finira par le fond lorsqu'il atteint les nœuds avec pas à gauche ou à droite des enfants (les nœuds feuilles).
Tandis que le TSL est plus complexe et concise les mécanismes pour ce faire, il a très vite pris la direction de la productivité juste pour apprendre à utiliser un manuel boucle dessus d'un récipient, quelque chose comme:
Tree::value_type total =Tree::value_type();for(Tree::const_iterator i = tree.begin(); i != tree.end();++i)
total +=*i;
Cela suppose que votre arbre binaire est un STL::map, ou si vous allez fournir un itérateur concept pour votre propre mise en œuvre....
Je ne voudrais pas donner cela comme une réponse à la question de l'entrevue Je souhaite que cette été ma première pensée. +1. Un arbre en C++ peut être juste une autre séquence. l'impression dépend de la phraséologie. Demandé "la somme des nœuds d'un arbre binaire", disant: "en C++ de la STL, std::map<> est le Standard de l'arbre binaire; à l'aide de son public interface simple, de manière générale, pour la somme de nœuds est XXX. Il est tout aussi applicable à d'autres itérateur-sportives abstractions." alors je pense que ce serait une saine réponse. Sachant que les gens pensent d'abord à la STL niveau (ou supérieur Modèle de Conception de niveau, le cas échéant), c'est rassurant. Au pire, l'enquêteur peut demander plus explicitement pour le récursive approche décrite dans d'autres réponses à cette question, ou que vous voulez comparer les deux. Montrant une bonne connaissance de C++/STL n'est pas de montrer une bonne connaissance des algorithmes et structures de données, et je suis prêt à parier que c'est la dernière solution à laquelle une question d'entrevue se réfère. Mettre une autre manière, on vous demande un algorithme... pourquoi ne pas le rendre générique en fait, le TSL a tendance à? Avoir quelqu'un à démontrer qu'ils savent que la std::map<> est un arbre qui est déjà un grand pas dans la bonne direction. Bref... j'ai présenté la possibilité - à chaque lecteur ici de décider si ils aimeraient l'utiliser au moment de l'entrevue et comment le faire, ou ce qu'il en ferait un candidat de le faire.
Utiliser l'une de l'Arbre Transversal techniques(Dans l'ordre, en Pré-commande, Post-order) à visiter, chaque nœud et de stocker la somme dans une variable.
Vous pouvez trouver plus de détails sur l'arbre transversal dans ce wiki
Répondre à des questions est bon, mais cette question a déjà des réponses très similaires code. Toute nouvelle réponse devrait ajouter différentes méthodes ou ajouter une meilleure explication de pourquoi la méthode est bonne. Un code de réponse, comme celui-ci, qui ne fait que répéter ce qui a déjà été fourni ajoute rien d'utile.
L'élégante solution récursive (en pseudo-code):
alors utilisez simplement:
Ce gère correctement le cas d'une valeur NULL nœud racine.
Et si vous voulez le voir en action en C++, voici le code à l'aide de cet algorithme. Tout d'abord, la structure d'un nœud et le
sum
fonction:Puis le code ci-dessous est un harnais de test de code pour l'insertion de nœuds:
Et, enfin, la fonction principale de la construction de l'arbre suivant, qui couvre l'ensemble de la validité de possibilités (vide nœud, nœud avec deux enfants, nœud, sans enfants, nœud avec un droit à l'enfant et à nœud avec un gauche de l'enfant):
Le code pour construire l'arbre et le rapport de la somme à différents points est indiquée ici:
Ce sorties (la bonne):
Oui, m'a pris à la mi-edit. Je venais juste de se demander où est la valeur du nœud actuel a été en provenance de... Fixe maintenant 🙂
Merci beaucoup Paxdiablo. Btw, c'est un algorithme O(n) droit? Depuis qu'il visite chacune des n nœuds qu'une seule fois.
Oui, il est O(n). J'ai dû penser à ce sujet depuis des arbres binaires sont normalement O(log n), mais c'est pour une recherche, pas de récupération. La traversée de chaque nœud est en effet O(n).
OriginalL'auteur paxdiablo
Traverse l'arbre dans n'importe quel ordre (pre, post). Au lieu de l'impression, le nœud de calculer le total.
OriginalL'auteur Manoj R
De la même manière que la recherche de l'arbre, ou l'affichage de chaque nœud, ou de tout autre arbre à l'échelle de l'opération: visite du nœud actuel, visite de la gauche du sous-arbre (de manière récursive), et de visiter le droit de sous-arbre (de manière récursive).
Essentiellement, quelque chose comme ceci:
En raison de la
if
vérifie la récursivité finira par le fond lorsqu'il atteint les nœuds avec pas à gauche ou à droite des enfants (les nœuds feuilles).OriginalL'auteur John Kugelman
Tandis que le TSL est plus complexe et concise les mécanismes pour ce faire, il a très vite pris la direction de la productivité juste pour apprendre à utiliser un manuel boucle dessus d'un récipient, quelque chose comme:
Cela suppose que votre arbre binaire est un STL::map, ou si vous allez fournir un itérateur concept pour votre propre mise en œuvre....
Je souhaite que cette été ma première pensée. +1. Un arbre en C++ peut être juste une autre séquence.
l'impression dépend de la phraséologie. Demandé "la somme des nœuds d'un arbre binaire", disant: "en C++ de la STL, std::map<> est le Standard de l'arbre binaire; à l'aide de son public interface simple, de manière générale, pour la somme de nœuds est XXX. Il est tout aussi applicable à d'autres itérateur-sportives abstractions." alors je pense que ce serait une saine réponse. Sachant que les gens pensent d'abord à la STL niveau (ou supérieur Modèle de Conception de niveau, le cas échéant), c'est rassurant. Au pire, l'enquêteur peut demander plus explicitement pour le récursive approche décrite dans d'autres réponses à cette question, ou que vous voulez comparer les deux.
Montrant une bonne connaissance de C++/STL n'est pas de montrer une bonne connaissance des algorithmes et structures de données, et je suis prêt à parier que c'est la dernière solution à laquelle une question d'entrevue se réfère.
Mettre une autre manière, on vous demande un algorithme... pourquoi ne pas le rendre générique en fait, le TSL a tendance à? Avoir quelqu'un à démontrer qu'ils savent que la std::map<> est un arbre qui est déjà un grand pas dans la bonne direction. Bref... j'ai présenté la possibilité - à chaque lecteur ici de décider si ils aimeraient l'utiliser au moment de l'entrevue et comment le faire, ou ce qu'il en ferait un candidat de le faire.
OriginalL'auteur Tony Delroy
Utiliser l'une de l'Arbre Transversal techniques(Dans l'ordre, en Pré-commande, Post-order) à visiter, chaque nœud et de stocker la somme dans une variable.
Vous pouvez trouver plus de détails sur l'arbre transversal dans ce wiki
OriginalL'auteur aeh
OriginalL'auteur Andrew Watson
OriginalL'auteur Antoniet Ama Aggrey