كيفية صنع شجرة في C++؟

Question

كيف أقوم بإنشاء بنية بيانات شجرة في C++ تستخدم التكرارات بدلاً من المؤشرات؟لم أتمكن من العثور على أي شيء في المحكمة الخاصة بلبنان يمكنه القيام بذلك.ما أود القيام به هو أن أكون قادرًا على إنشاء الأشجار ومعالجتها على النحو التالي:

#include <iostream>
#include <tree>
using namespace std;

int main()
{
    tree<int> myTree;

    tree<int>::iterator i = myTree.root();
    *i = 42;

    tree<int>::iterator j = i.add_child();
    *j = 777;
    j = j.parent();

    if (i == myTree.root() && i == j) cout << "i and j are both pointing to the root\n";

    return 0;
}

---

شكرًا لك، Tree.hh يبدو أنه ما كنت أبحث عنه تمامًا.

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

الخريطة عبارة عن حاوية نقاطية تحتوي على أداء يضمن مطابقًا لتلك الموجودة في الشجرة:البحث اللوغاريتمي ، الإدراج اللوغاريتمي ، الحذف اللوغاريتمي ، الفضاء الخطي.داخليا غالبا ما يتم تنفيذها كأشجار أسود حمراء ، على الرغم من أن هذا ليس ضمانًا.ومع ذلك ، كمستخدم STL ، كل ما يجب أن تهتم به هو ضمانات الأداء لخوارزميات STL وهياكل البيانات.سواء تم تنفيذها كأشجار أو رجال خضراء صغار لا ينبغي أن يهمك.

لست متأكدًا مما إذا كانت الخريطة هي ما أحتاج إليه، ولكن شكرًا على المعلومات.سأتذكر استخدام الخرائط كلما أمكن ذلك بدلاً من تنفيذ الأشجار.

Answer 1

هنا الشجرة.hh وهو قريب قليلاً مما تريد القيام به ، على الرغم من أنه مختلف بعض الشيء.

هنا جزء من التعليمات البرمجية المستخرجة من موقعه على الانترنت.

int main(int, char **)
   {
   tree<string> tr;
   tree<string>::iterator top, one, two, loc, banana;

   top=tr.begin();
   one=tr.insert(top, "one");
   two=tr.append_child(one, "two");
   tr.append_child(two, "apple");
   banana=tr.append_child(two, "banana");
   tr.append_child(banana,"cherry");
   tr.append_child(two, "peach");
   tr.append_child(one,"three");

   loc=find(tr.begin(), tr.end(), "two");
   if(loc!=tr.end()) {
      tree<string>::sibling_iterator sib=tr.begin(loc);
      while(sib!=tr.end(loc)) {
         cout << (*sib) << endl;
         ++sib;
         }
      cout << endl;
      tree<string>::iterator sib2=tr.begin(loc);
      tree<string>::iterator end2=tr.end(loc);
      while(sib2!=end2) {
         for(int i=0; i<tr.depth(sib2)-2; ++i) 
            cout << " ";
         cout << (*sib2) << endl;
         ++sib2;
         }
      }
   }

الآن ما هو المختلف؟يكون تنفيذك أكثر بساطة عندما يتعلق الأمر بإلحاق عقدة على الشجرة.على الرغم من أن نسختك أبسط بلا شك، إلا أن مطور هذا lib ربما أراد الوصول إلى بعض المعلومات دون تصفح الشجرة، مثل حجم الشجرة على سبيل المثال.

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

Answer 2

لماذا تريد أن تفعل ذلك؟إذا كان هذا لأغراض التعلم، فيمكنك كتابة بنية بيانات الشجرة الخاصة بك.إذا كان هذا من أجل الاستفادة من بنية البيانات التي تحتوي على أنواع فهرس عشوائية، مُحسّنة للبحث وجيدة في الإدراج، ففكر في استخدام الخريطة.

الخريطة عبارة عن حاوية ترابطية تتمتع بضمانات أداء مماثلة لتلك الخاصة بالشجرة:البحث اللوغاريتمي، الإدراج اللوغاريتمي، الحذف اللوغاريتمي، الفضاء الخطي.داخليًا، غالبًا ما يتم تنفيذها كأشجار ذات لون أحمر وأسود، على الرغم من أن هذا ليس ضمانًا.ومع ذلك، باعتبارك مستخدم STL، كل ما يجب أن تهتم به هو ضمانات أداء خوارزميات STL وهياكل البيانات.سواء تم تنفيذها كأشجار أو رجال صغار، لا يهم بالنسبة لك.

كملاحظة جانبية، لا يوجد شيء اسمه وظيفة root().تحتوي جميع حاويات STL على وظيفة begin() التي تنفذ البداية المفاهيمية للحاوية.يعتمد نوع المكرر الذي يتم إرجاعه بواسطة هذه الوظيفة على خصائص الحاوية.