모든 노드를 요약합니다

Question

이것은 간단한 수정 일 수 있지만 이진 검색 트리의 모든 노드 (노드 클래스의 크기)를 합산하려고합니다. 아래에서 내 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);
    }

노드 클래스 내에 주어진 속성에 크기와 이름을 저장하는 데이터가 있습니다. 나는 단지 전체 크기를 합산하려고 노력하고 있습니다. 제안이나 아이디어가 있습니까?

Answer 1

잎 노드에 도달하면 0을 반환하기 때문입니다. 해당 리프 노드에 저장된 크기를 반환해야합니다.

또한 잎이 아닌 노드에도 크기가있는 경우 다음을 처리해야합니다.

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

아마도 당신은 의미합니다

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

?

Answer 3

이 시도:

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

원래 코드가 반환하는 유일한 "값"은 0이므로 결과는 항상 0입니다.

Answer 4

어때

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