質問
これは簡単な修正かもしれませんが、バイナリ検索ツリー上のすべてのノード(NodeクラスのSizeプロパティ)を合計しようとしています。私の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クラス内には、指定されたプロパティにサイズと名前を格納するデータがあります。全体のサイズを合計しようとしています。提案やアイデアはありますか?
解決
リーフノードに到達するとゼロを返すためです。そのリーフノードに保存されているサイズを返す必要があります。
さらに、非葉ノードにもサイズがある場合、同様に処理する必要があります。
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);
}
他のヒント
もしかするとあなたは
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
?
これを試してください:
private long sum(Node<T> thisNode)
{
if (thisNode == null)
return 0;
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
唯一の&quot; value&quot;元のコードが返す値は0であるため、結果は常に0です。
方法について
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;
}
所属していません StackOverflow