Resumindo todos os nós
Pergunta
Isto pode ser uma solução simples - mas eu estou tentando somar juntos todos os nós (propriedade Tamanho da classe Node) na árvore de busca binária. Abaixo na minha classe BST Eu tenho o seguinte até agora, mas ele retorna 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);
}
Dentro de minha classe Node eu tenho dados que armazena Tamanho e nome em suas propriedades dadas. Eu só estou tentando resumir o tamanho inteiro. Todas as sugestões ou idéias?
Solução
É porque você está retornando zero quando você chegar a um nó folha. Você deve estar retornando o tamanho armazenado nesse nó folha.
Além disso, se seus nós não-folha também têm um tamanho, você vai precisar para processá-los bem assim:
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);
}
Se os nós não-folha não tem tamanho, use:
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);
}
A versão mais elegante do primeiro é:
private long sum(Node<T> thisNode)
{
if (thisNode == null)
return 0;
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
Outras dicas
Talvez você quis dizer
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
?
Tente isto:
private long sum(Node<T> thisNode)
{
if (thisNode == null)
return 0;
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
O único "valor" que o código original nunca retorna é 0 -. É por isso que o resultado é sempre 0
Como cerca
private long Sum(Node<T> thisNode)
{
if( thisNode == null )
return 0;
return thisNode.Size + Sum(thisNode.Left) + Sum(thisNode.Right);
}
Se a propriedade tamanho não é no próprio nó, o que sobre isso?
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;
}