تلخيص كافة العقد

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

وانها لأنك تعود الصفر عندما تصل إلى عقدة ورقة. يجب أن تكون إعادة حجم المخزنة في تلك العقدة ورقة.

وبالإضافة إلى ذلك، إذا كان لدى العقد غير طرفية بك أيضا حجم، ستحتاج إلى معالجتها، وكذلك على النحو التالي:

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