أشجار n-ary في ج

Question

ما الذي سيكون بمثابة استنزاف أنيق لشجرة N-ary بلغة C؟

خاصة ، أريد تنفيذ شجرة n-ary ، وليس التوازن الذاتي ، مع عدد غير مبين من الأطفال في كل عقدة ، حيث تحتوي كل عقدة على بنية محددة بالفعل ، مثل هذا على سبيل المثال:

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

Answer 1

كمرحلة أولى ، يمكنك ببساطة إنشاء ملف بنية (دعنا نسميها treenode) الذي يحمل ملف مهمة, ، وكذلك مجموعة من المؤشرات treenodeس. يمكن أن تكون هذه المجموعة إما صفيفًا (إذا ن ثابت) أو قائمة مرتبطة (إذا ن متغير). ستتطلب منك القائمة المرتبطة إعلان المزيد بنية (دعونا نسميها ListNode) مع treenode مؤشر للطفل الفعلي (جزء من الشجرة) ، ومؤشر إلى التالي ListNode في القائمة (لا شيء إذا في نهاية القائمة).

قد يبدو شيئًا كهذا:

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

struct TreeNode;

struct ListNode {
  struct TreeNode * child;
  struct ListNode * next;
};

struct TreeNode {
  struct task myTask;
  struct ListNode myChildList;
};

Answer 2

يمكن تمثيل أي شجرة N كأشجار ثنائية حيث يشير المؤشر الأيسر في كل عقدة إلى الطفل الأول ويشير المؤشر الأيمن إلى الأخ التالي.

             R                        R
           / | \                      |
          B  C  D                     B -- C -- D
         / \    |                     |         |
        E   F   G                     E -- F    G

لذلك ، ستكون قضيتك:

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

struct node {
  struct task taskinfo;
  struct node *firstchild;
  struct node *nextsibling;
};

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