Суммируем все узлы
Это может быть простое исправление, но я пытаюсь суммировать все узлы (свойство 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 у меня есть данные, которые хранят размер и имя в своих заданных свойствах. Я просто пытаюсь суммировать весь размер. Есть предложения или идеи?
Ответы 4
Может ты имел в виду
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
?
Это потому, что вы возвращаете ноль, когда достигаете листового узла. Вы должны вернуть размер, хранящийся в этом листовом узле.
Кроме того, если ваши нелистовые узлы также имеют размер, вам также необходимо обработать их таким образом:
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);
}
Тогда как вы ожидаете, что сумма волшебным образом появится? Не можете получить доступ к свойству размера, содержащему объект из узла?
Вы были правы ... очевидно, что к нему нельзя получить доступ, поэтому я просто внес небольшие изменения и получил его!
Как насчет
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;
}
Попробуй это:
private long sum(Node<T> thisNode)
{
if (thisNode == null)
return 0;
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
Единственное «значение», которое когда-либо возвращает исходный код, - это 0, поэтому результат всегда равен 0.
Класс Node не содержит свойства Size - вместо этого он находится в другом классе, который я вызываю и создаю в форме. Например, в форме у меня будет: NameAndSize obj_NS = new NameAndSize («Имя», 320); затем в форме я бы вызвал sum (), чтобы вернуть сумму всех объектов Size.