Résumer tous les nœuds

Question

Il s’agit peut-être d’une solution simple - mais j’essaie de faire la somme de tous les nœuds (propriété Size de la classe Node) de l’arbre de recherche binaire. Ci-dessous, dans ma classe BST, j'ai les éléments suivants jusqu'à présent, mais renvoie 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 de nœuds, j'ai des données qui stockent la taille et le nom dans leurs propriétés. J'essaie juste de résumer la taille entière. 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.

De plus, si vos nœuds non-feuilles ont également une taille, vous devez également les traiter 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 n'ont 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 du premier 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

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 soit toujours égal à 0, c'est pourquoi le résultat est toujours égal à 0.

Answer 4

Que diriez-vous de

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 est-il?

    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;
    }