Суммирование всех узлов

Question

Это может быть простым исправлением - но я пытаюсь объединить все узлы (свойство Size из класса Node) в двоичном дереве поиска. Ниже в моем классе BST у меня пока есть следующее, но он возвращает 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);
    }

В моем классе Node у меня есть данные, в которых хранятся размер и имя в данных свойствах. Я просто пытаюсь сложить весь размер. Есть предложения или идеи?

Answer 1

Это потому, что вы возвращаете ноль, когда достигнете конечного узла. Вы должны возвращать размер, сохраненный в этом листовом узле.

Кроме того, если ваши нелистовые узлы также имеют размер, вам также необходимо их обработать таким образом:

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

Если ваши неконечные узлы не имеют размера, используйте:

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

Более элегантная версия первой:

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

Answer 2

Попробуйте это:

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

Единственное «значение», которое когда-либо возвращает исходный код, равно 0 - поэтому результат всегда равен 0.

Answer 3

Как насчет

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

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

Если свойство размера находится не на самом узле, как насчет этого?

    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

Может быть, вы имели в виду

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