J'ai besoin d'aide pour la récursion. J'essaie d'effectuer un arbre binaire en C #, je me demande s'il est possible de démontrer tous les inondérateurs / post-mandataires et pré-commande Traversal avec une fonction récursive.
Je l'ai terminé pour la pré-commande, puis tentative d'inondation a donné une exception StackoverFlow, ma compréhension de l'arbre binaire est fragile au mieux, de sorte que toute aide serait très appréciée, même si cela semble être une question stupide.
Le code suivant est ce que j'utilise pour la traversée de pré-commande; merci d'avance, c'est vraiment quelque chose que j'ai du mal à me faire la tête et je ne suis même pas sûr que si c'est possible.
3 Réponses :
Inordorder est très similaire à ce que vous avez déjà, déplacez simplement votre code autour d'un peu dans l'endroit où vous manipulez le nœud actuel:
public void recursiveInorder(BinaryTreeNode root)
{
if (root.Left != null)
{
recursiveInorder(root.Left);
}
Console.Write(root.Data.ToString());
if (root.Right != null)
{
recursiveInorder(root.Right);
}
}
Merci beaucoup pour la réponse rapide, une chance que vous puissiez aussi me montrer Post-poste? Et toute autre, vous pourriez aider à expliquer comment cela fonctionne réellement pour moi? Je suis juste coincé à la fois sur la façon dont les arbres binaires fonctionnent et la façon dont la récupération fonctionne parce que votre réponse est parfaitement claire, je semble avoir du mal à comprendre quelque chose d'entourant ce sujet.
@STEFFUNAINAINE: Pensez-y pour une seconde: POST POST Commandez simplement le traitement du nœud actuel en dernier - alors où placeriez-vous votre console.write Déclaration? Découvrez également l'article Wikipedia que @Mitch liait ci-dessous.
Ha, je savais que ce serait simple et avec le lien d'article ci-dessous et votre réponse est vraiment très évidente. Merci beaucoup mate très appréciato;)
Nous pouvons ajouter une validation au début de la méthode pour vérifier si la racine est null.
La page wiki pour TRAVERSAL ARBRE Etats:
arbre binaire Traverser un arbre binaire non vide dans Pré-commande , effectuez les opérations suivantes de manière récursive à chaque nœud, à partir de avec le nœud racine:
- Visitez la racine.
- traverser le sous-arbre gauche.
- traverser le sous-arbre de droite.
traverser un arbre binaire non vide dans
Inordorder (symétrique), effectuer Les opérations suivantes récursives à chaque noeud:
- traverser le sous-arbre gauche.
- Visitez la racine.
- traverser le sous-arbre de droite.
traverser un arbre binaire non vide dans Postard , effectuez le Opérations suivantes récursives à chaque noeud:
- traverser le sous-arbre gauche.
- traverser le sous-arbre de droite.
- Visitez la racine.
[BTW, c'était la première recherche frappée.]
J'ai déjà reçu un document qui tente d'expliquer cela, je ne l'ai tout simplement pas obtenu, je voulais aussi une réponse plus humaine cependant que la poste que vous avez liée est très utile, donc merci beaucoup :)
class BstNode
{
public int data;
public BstNode(int data)
{
this.data = data;
}
public BstNode left;
public BstNode right;
}
class Program
{
public static void PreOrderTraversal(BstNode root)
{
if (root == null) return;
Console.WriteLine("PreOrderTraversal at node {0}", root.data); // process the root
PreOrderTraversal(root.left);// process the left
PreOrderTraversal(root.right);// process the right
}
public static void InOrderTraversal(BstNode root)
{
if (root == null) return;
InOrderTraversal(root.left);// process the left
Console.WriteLine("InOrderTraversal at node {0}", root.data); // process the root
InOrderTraversal(root.right);// process the right
}
public static void PostOrderTraversal(BstNode root)
{
if (root == null) return;
PostOrderTraversal(root.left);// process the left
PostOrderTraversal(root.right);// process the right
Console.WriteLine("PostOrderTraversal at node {0}", root.data); // process the root
}
}