Résumer tous les nœuds

Question

Cela peut être une solution simple - mais j'essaie de faire la somme de tous les nœuds (propriété Size de la classe Node) dans l'arborescence de recherche binaire. Ci-dessous dans ma classe de BST je le suivant jusqu'à présent, mais il retourne 0:

private long sum(Node<T> thisNode) 
    { 
     if (thisNode.Left == null && thisNode.Right == null) 
      return 0; 
     if (node.Right == null) 
      return sum(thisNode.Left); 
     if (node.Left == null) 
      return sum(thisNode.Right); 


     return sum(thisNode.Left) + sum(thisNode.Right); 
    } 

Dans ma classe Node I contiennent des données qui stocke la taille et le nom dans leurs propriétés données. J'essaie juste de faire la somme de toute la taille. Des suggestions ou des idées?

Answer 1

C'est parce que vous retournez zéro lorsque vous atteignez un nœud feuille. Vous devriez retourner la taille stockée dans ce noeud feuille.

En outre, si vos noeuds non-feuilles ont également une taille, vous aurez besoin de les traiter ainsi ainsi:

private long sum(Node<T> thisNode) 
{ 
    if (thisNode.Left == null && thisNode.Right == null) 
     return thisNode.Size; 
    if (node.Right == null) 
     return thisNode.Size + sum(thisNode.Left); 
    if (node.Left == null) 
     return thisNode.Size + sum(thisNode.Right); 
    return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right); 
} 

Si vos noeuds non-feuilles ne sont pas de taille, utilisez:

private long sum(Node<T> thisNode) 
{ 
    if (thisNode.Left == null && thisNode.Right == null) 
     return thisNode.Size; 
    if (node.Right == null) 
     return sum(thisNode.Left); 
    if (node.Left == null) 
     return sum(thisNode.Right); 
    return sum(thisNode.Left) + sum(thisNode.Right); 
} 

une version plus élégante de la première est:

private long sum(Node<T> thisNode) 
{ 
    if (thisNode == null) 
     return 0; 
    return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right); 
} 

Answer 2

Peut-être que vous vouliez dire

if (thisNode.Left == null && thisNode.Right == null) 
     return thisNode.Size; 

?

Answer 3

Que diriez-vous

private long Sum(Node<T> thisNode) 
{ 
    if(thisNode == null) 
    return 0; 

    return thisNode.Size + Sum(thisNode.Left) + Sum(thisNode.Right); 
} 

Si la propriété size n'est pas sur le nœud lui-même, qu'en pensez-vous?

public class Node<T> 
    { 
     public T Data; 
     public Node<T> Left; 
     public Node<T> Right; 

     public static void ForEach(Node<T> root, Action<T> action) 
     { 
      action(root.Data); 

      if (root.Left != null) 
       ForEach(root.Left, action); 
      if (root.Right != null) 
       ForEach(root.Right, action); 
     } 
    } 

    public interface IHasSize 
    { 
     long Size { get; } 
    } 

    public static long SumSize<T>(Node<T> root) where T : IHasSize 
    { 
     long sum = 0; 
     Node<T>.ForEach(root, delegate(T item) 
     { 
      sum += item.Size; 
     }); 
     return sum; 
    } 

Answer 4

Essayez ceci:

private long sum(Node<T> thisNode) 
    { 
     if (thisNode == null) 
      return 0; 
     return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right); 
    } 

La seule « valeur » que le code d'origine revient toujours est 0 - c'est pourquoi le résultat est toujours 0.