Frage zu Baum Datenstruktur, Drucken jeder Ebene Summe (Ebene Summe = Summe der Geschwister-Daten)?

Question

Unten habe ich ein Stück Code geschrieben, um diese Frage zu beantworten. Colud Sie bitte sagen Sie mir 1) Wenn Sie finden Sie irgendwelche Fehler in meinem Code 2) alle andere beste Lösung?

Frage: Frage zu Baum Datenstruktur, Drucken jeder Ebene Summe (Ebene Summe = Summe der Geschwister-Daten)?

struct tree{ 
      int data; 
      struct *left; 
      struct *right; 
}; 

API ProType ist Hohlraum EachLevelSum (struct Baum * root);

Meine Antwort ist

void EachLevelSum(struct tree *root) 
{ 
    static int level=0; 
    static int a[100] = {0}; // I am assuming , at MAX 100 levels in tree 

    if(root == NULL) 
    { 
      return; 
    } 
    else 
    { 
      a[level += root->data; 

      level++; 
      EachLevelSum(root->left); 
      level--;  

      level++; 
      EachLevelSum(root->right); 
      level--;  

      if(level == 0) 
      { 
       int i; 
       for(i=0; i<100 && a[i]!=0 ; i++) 
       { 
        printf("\n level: %d sum = %d", i, a[i]); 
       } 

      } 
    } 

} 

Answer 1

Ich denke, das ist ziemlich gut! Ich kann jedoch ein oder zwei Dinge sagen, die Ihnen helfen können, es zu verbessern.

1 - Die Verwendung von statischen Variablen. Es ist nicht verboten, aber Sie sollten dies vermeiden. Nun, wie wäre es, wenn Ihre Lösung rekursiv ist und Sie zwischen den Aufrufen Daten benötigen?

Der allgemeine Ansatz besteht darin, eine zweite Funktion zu verwenden, die den rekursiven Aufruf umschließt und zusätzliche Parameter an ihn übergibt. In Ihrem Fall:

void eachLevelSum(struct tree*); 
static void eachLevelSumRecursive(struct tree*, int level, int* results); 

Und dann so etwas wie:

void eachLevelSum(struct tree* t) { 
    int results[100]; 
    eachLevelSumRecursive(t, 0, results); 

    return; 
} 

Dann in Ihrer rekursive Funktion, wenn Sie in Rekursion gehen, können Sie die Ebene Parameter wie Pegel + 1 anstatt das zu tun Ebene passieren ++ und level-- = D like this:

eachLevelSumRecursive(t->left, level + 1, results); 
eachLevelSumRecursive(t->right, level + 1, results); 

Beachten Sie, das ist nicht nur ein bisschen sauberer, es hat andere Vorteile. Dieser Ansatz kann beispielsweise in einer Multithread-Umgebung verwendet werden, während der andere nicht verwendet werden kann, da er auf statischen Variablen beruht.

2 - Möglicherweise möchten Sie Ihre Struktur mit typedefs und Funktionen, die die Struktur ändern, weiter einkapseln. Wenn Sie mehr Informationen dazu benötigen, fragen Sie nach. Für deine Übung ist es jedoch überhaupt nicht notwendig.

3 - Denken Sie daran, dass Funktionsnamen normalerweise mit Kleinbuchstaben beginnen.

Und das ist alles, was ich zu sagen habe, ist Ihr Code ziemlich sauber! Herzliche Glückwünsche!

Answer 2

ich vermeiden würde Ebene als eine globale Variable. In diesem speziellen Fall ist es nicht so wichtig, da es keine Komplikation des Threading oder ähnliches gibt. Aber es ist gut, es zu einer Gewohnheit zu machen, globale Variablen zu vermeiden.

Es ist immer eine lokale Variable als ein globales, zu verwenden, wenn Sie zu verwenden, um eine globale Variable haben und Sie müssen vorsichtig sein.

Ich würde Ebene als Argument in der Methode hinzufügen, und statt level ++ und level--, ich werde einfach level + 1 an den Methodenaufruf übergeben.

Answer 3

Ihr Code scheint es richtig zu machen. In Englisch Ihre logischen Zustände -

Für jede Ebene, die Sie in den Baum hinabsteigen (links und rechts), den Überblick über Ihre Tiefe und fügen data zu einem globalen Summen Nachführgröße a.

Es sei denn, Sie machen erhebliche Änderungen an der Struktur - das ist der einzige Weg, es zu tun (das ich mir vorstellen kann)

Answer 4

Ich denke, Ihr Code ist gut.

Als Alternative können Sie die BFS-Suche verwenden: http://en.wikipedia.org/wiki/Breadth-first_search. Hier ist die Probe C# -Code

class Tree 
    { 
     public int data; 
     public Tree Left; 
     public Tree Right; 


      static int[] levels = new int[100]; 

      static void EachLevelSum(Tree root) 
      { 
       // keeps track of each tree node's level 
       Dictionary<Tree, int> treeLevels = new Dictionary<Tree,int>(); 
       treeLevels.Add(root, 0); 

       // Do a BFS search and update the level of each node 
       Queue<Tree> trees = new Queue<Tree>(); 
       trees.Enqueue(root); 

       while (trees.Count != 0) 
       { 
        Tree node = trees.Dequeue(); 
        int level = treeLevels[node]; 
        if (node.Left != null) 
        { 
         treeLevels.Add(node.Left, level + 1); 
         trees.Enqueue(node.Left); 
        } 
        if (node.Right != null) 
        { 
         treeLevels.Add(node.Right, level + 1); 
         trees.Enqueue(node.Right); 
        } 
       } 
       foreach (Tree node in treeLevels.Keys) 
       { 
        int level = treeLevels[node]; 
        levels[level] += node.data; 
       } 

      } 
    }