1

これは簡単な修正かもしれませんが、バイナリ サーチ ツリーのすべてのノード (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 クラス内には、指定されたプロパティに Size と Name を格納する Data があります。私は全体のサイズを合計しようとしています。提案やアイデアはありますか？

4

4 に答える 4

2

これは、リーフ ノードに到達したときにゼロを返しているためです。そのリーフ ノードに格納されているサイズを返す必要があります。

さらに、非リーフ ノードにもサイズがある場合は、次のように処理する必要があります。

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);
}
于 2008-10-23T05:35:32.200 に答える
1

多分あなたは意味した

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

?

于 2008-10-23T05:30:51.647 に答える
1

どうですか

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

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

size プロパティがノード自体にない場合、これはどうですか?

    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;
    }
于 2008-10-23T05:35:38.550 に答える
1

これを試して：

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

元のコードが返す唯一の「値」は 0 です。そのため、結果は常に 0 です。

于 2008-10-23T05:36:32.510 に答える