C# Itération de grand arbre

Question

J'ai un grand ensemble de résultats assemblé dans une relation parent/enfant. J'ai besoin de marcher dans l'arbre et afficher les résultats à l'utilisateur.

Je l'ai fait avant d'utiliser la récursivité, mais parce que mon jeu de résultats peut être grand, je veux éviter la possibilité de recevoir une exception StackOverflowException.

J'ai trouvé le suivant example sur MSDN qui utilise une pile. Le problème que j'ai est parce qu'une pile est le dernier entré, le premier, mes données n'apparaissent pas correctement. Je voudrais que ça ressemble à ce qui suit:

LeveL 1 
Level 1.1 
Level 1.1.1 
Level 1.1.2 
Level 1.2 
Level 1.2.1 
Level 1.2.2 

Mais il ressemble à:

LeveL 1 
Level 1.2 
Level 1.2.2 
Level 1.2.1 
Level 1.1 
Level 1.1.2 
Level 1.1.1 

Toutes les idées?

Voici un exemple de mon code. En supposant que le DataTable dt a les colonnes suivantes: ID, ParentID et texte

private struct Item 
    { 
     public string Text; 
     public int ID; 
     public int ParentID; 
    } 

    private void BuildView() 
    { 
     Stack<Item> itemTree = new Stack<Item>(40); 

     //Get All Parent Nodes 
     DataView dv = new DataView(dt); 
     dv.RowFilter = "ParentID = 0"; 

     //Add the parent nodes to the stack 
     foreach (DataRowView drv in dv) 
     { 
      Item item = new Item(); 
      item.Text = drv["Text"].ToString(); 
      item.ID = drv["ID"].ToString(); 
      item.ParentID = drv["ParentID"].ToString(); 
      itemTree.Push(item); 
     } 

     //Go through the stack one node at a time 
     while (itemTree.Count > 0) 
     { 
      Item currentItem = itemTree.Pop(); 
      Debug.WriteLine(currentItem.Text); 

      //Get children of current node 
      dv.RowFilter = String.Format("ParentID = {0}", currentItem.ID); 
      if (dv.Count > 0) 
      { 
       //Add child nodes to the stack 
       foreach (DataRowView drvChild in dv) 
       { 
        Item item = new Item(); 
        item.Text = drvChild["Text"].ToString(); 
        item.ID = drvChild["ID"].ToString(); 
        item.ParentID = drvChild["ParentID"].ToString(); 
        itemTree.Push(item); 
       } 
      } 
     } 

    } 

Answer 1

Poussez vos articles sur la pile dans l'ordre inverse, soit 2 avant 1.

Exemple:

// suppose I want to push children[] onto the stack 

for (int i = children.Length - 1; i >= 0; i--) 
{ 
    stack.Push(children[i]); 
} 

Pour ce faire, dans votre code, essayez la déclaration for-each suivante:

foreach (DataRowView drvChild in dv.Reverse()) 

Answer 2

Dans l'algorithme actuel, vous allez à l'enfant dès la première.

Faites-le gauche enfant en premier. C'est tout.

Par exemple, dans votre code il peut y avoir quelque chose comme:

node = node.rightChild() 

Modifier à

node = node.leftChild() 

Ceci est la solution générale pour ce genre de questions.

Étant donné que l'implémentation MSDN n'expose pas ce type de code, je ne peux pas commenter cela.

Answer 3

Si c'est simplement la commande qui vous préoccupe, passez de l'utilisation d'une pile à l'utilisation d'une file d'attente. Ils sont identiques pour des raisons pratiques, à la différence qu'une file d'attente est la première en premier.

Answer 4

En changeant mon itération des nœuds enfants dans l'ordre inverse, ils affichent comme vous le souhaitez

//Add child nodes to the stack 
for (int i = dv.Count - 1; i >= 0; i--) 
{ 
    DataRowView drvChild = dv[i]; 
    Item item = new Item(); 
    item.Text = drvChild["Text"].ToString(); 
    item.ID = drvChild["ID"].ToString(); 
    item.ParentID = drvChild["ParentID"].ToString(); 
    itemTree.Push(item); 
}