Fasst man alle Knoten

Question

Dies kann eine einfache Lösung sein - aber ich versuche, alle Knoten zu summieren zusammen (Größe Eigenschaft aus der Klasse Node) auf dem binären Suchbaum. Unten in meiner BST Klasse weit folgend ich habe so, aber es gibt 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);
    }

Im Rahmen meiner Node-Klasse habe ich Daten, die in ihren gegebenen Eigenschaften Größe und Namen speichern. Ich versuche nur, die gesamte Größe zu summieren. Irgendwelche Vorschläge oder Ideen?

Answer 1

Es ist, weil Sie Null sind Rückkehr, wenn Sie einen Blattknoten erreichen. Sie sollten die Größe in diesem Blattknoten gespeichert werden, zurück.

Darüber hinaus, wenn Ihr Nicht-Blattknoten auch eine Größe haben, müssen Sie sie auch so verarbeiten:

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

Wenn Ihr Nicht-Blattknoten haben keine Größe, zu verwenden:

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

Eine elegantere Version der erste ist:

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

Answer 2

Vielleicht bedeuten Du

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

Answer 3

Versuchen Sie folgendes:

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

Der einzige „Wert“, dass der ursprüngliche Code immer 0 zurück - deshalb ist das Ergebnis immer 0

.

Answer 4

Wie wäre es

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

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

Wenn die Größe Eigenschaft ist nicht auf den Knoten selbst, was ist das?

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