شجرة هيكل الأشجار المبلغ الذي يتوسل إلى عقدة الجذر

Question

سأذهب إلى الخارج ويقول إنني لست أعظم عالم الرياضيات في العالم: D لذلك قد تكون هذه المشكلة بسيطة بالنسبة لمعظمكم. لسوء الحظ، إنه أمر يربكني واجهنا عدة طعنات في حلول عملية.

كما هو الحال مع أي شجرة، يمكن للمرء أن يكون لديه العديد من الفروع، يمكن أن تحتوي العديد من الفروع على المزيد من الفروع وما إلى ذلك حتى تنتهي مع عقدة ورقة. لدي معلومات حول كل ورقة تشير إلى قيمتها.

ما أطلبه هو تفسير واضح حول كيفية معالجة مشكلة تلخيص كل قيمة عقدة ورقة كإجمالي لفرعها (الأصل) والقيام بنفس الشيء بالنسبة للباقي ولكن لا تنسى أنه إذا تم مشاركة فرع من خلال فروع أخرى ملخص كل فرع منخفض المستوى والأوراق التي ترتبط مباشرة بحد ذاتها.

لتفسير أفضل:

Root
|----Branch
|         |-Leaf 10
|----Branch
|         |----Branch
|         |-Leaf 20 |-Leaf 30
|----Branch         |-Leaf 40
|         |----Branch
|                   |----Branch
|                             |----Leaf 50
|-Leaf 60

الهدف:

Root 210
|----Branch 10
|         |-Leaf 10
|----Branch 90
|         |----Branch 70
|         |-Leaf 20 |-Leaf 30
|----Branch 50      |-Leaf 40
|         |----Branch 50
|                   |----Branch 50
|                             |----Leaf 50
|-Leaf 60

أنا قادر على تحديد أدنى مستوى الأعضاء (العقد ورقة)، عقدة الجذر والفروع نفسها. ليس لدي تحديد هوية حول ما إذا كان الفرع يحتوي على فروع أخرى مرتبطة بحد ذاته منخفضا أو مرتبطا مباشرة بعقدة أوراق. العلاقة هي أسفل إلى أعلى جدا إلى الجذر. أي: الفرع ليس لديه إشارة إلى من هم الأطفال، لكن الأطفال يعرفون من هو الوالد.

من فضلك إذا كان هناك شيء غير واضح سأحاول وشرح المشكلة بشكل أفضل.

سيكون موضع تقدير أي مساعدة.

Answer 1

حسنا، يمنح اليسار هذه الطعنة.

أود أن أذهب حول هذا الأمر مع بعض الرمز الزائفي

foreach leaf in knownLeafs
    parent = leaf.parent //get the leaf parent
    parent.total = parent.total + leaf.value //add leaf value to parent total
    while parent.parent != null //loop until no more parents, this would be the root
    {
        current = parent
        parent = parent.parent //move up the structure
        parent.total = parent.total + current.total
    }
next leaf

ستحتاج إلى إنشاء وظيفة من شأنها أن تعطى عقدة، وإرجاع العقدة الأصل

عقدة getparentnodefrom (عقدة)

سيبدو رمز الزائفة الجديد شيئا كهذا

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent

parent.total = parent.total + leaf.value //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + current.total
}
next leaf

عذرا، خطأي، يجب عليك فقط نقل قيمة الورقة، وليس الإجماليات أيضا. انظر الورقة الجديدة المستخدمة.

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent
leafValue = leaf.value
parent.total = parent.total + leafValue //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + leafValue
}
next leaf

Answer 2

تريد تحديد مجموع كل العقد في الشجرة؟

يضفي المشي في الأشجار لحل متكرر أنيق:

public int SumTree (TreeNode n) {
    if(n.isLeafNode) return n.value;
    return SumTree(n.left) + SumTree(n.right);
}

على افتراض شجرة ثنائية.