شجرة هيكل الأشجار المبلغ الذي يتوسل إلى عقدة الجذر
-
12-09-2019 - |
سؤال
سأذهب إلى الخارج ويقول إنني لست أعظم عالم الرياضيات في العالم: 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
أنا قادر على تحديد أدنى مستوى الأعضاء (العقد ورقة)، عقدة الجذر والفروع نفسها. ليس لدي تحديد هوية حول ما إذا كان الفرع يحتوي على فروع أخرى مرتبطة بحد ذاته منخفضا أو مرتبطا مباشرة بعقدة أوراق. العلاقة هي أسفل إلى أعلى جدا إلى الجذر. أي: الفرع ليس لديه إشارة إلى من هم الأطفال، لكن الأطفال يعرفون من هو الوالد.
من فضلك إذا كان هناك شيء غير واضح سأحاول وشرح المشكلة بشكل أفضل.
سيكون موضع تقدير أي مساعدة.
المحلول
حسنا، يمنح اليسار هذه الطعنة.
أود أن أذهب حول هذا الأمر مع بعض الرمز الزائفي
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
نصائح أخرى
تريد تحديد مجموع كل العقد في الشجرة؟
يضفي المشي في الأشجار لحل متكرر أنيق:
public int SumTree (TreeNode n) {
if(n.isLeafNode) return n.value;
return SumTree(n.left) + SumTree(n.right);
}
على افتراض شجرة ثنائية.