منظر عام للشجرة والتنفيذ والمزيد

ربما حاول العديد من الأشخاص العثور على بنية شجرة عامة، لكن محرك البحث وجد فقط تلك الثنائية... شجرة البحث الثنائية، واجتياز الشجرة الثنائية والعديد من الخوارزميات الأخرى.
نعم، في الواقع، لا يتم استخدام الشجرة العامة في أي مكان، والاجتياز بطيء، وحالات الاستخدام صغيرة.

لذا سألت نفسي هذا السؤال والآن سأشرح كيف يتم بناء الشجرة. لذلك، من الناحية المثالية، يجب أن يخزن هيكل الشجرة العام ثلاثة متغيرات:

• مؤشر للابن الأكبر
• المؤشر للأخ
• البيانات التي ستقوم بتخزينها

struct Tnode {
    int key;
    struct Tnode *son;
    struct Tnode *brother;
};
typedef struct Tnode Node;

لنعلن عن مؤشر إلى القمة:

Node *tree = NULL;

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

• + 2 (أو +ssbb 2) - الإدراج في شجرة (بالنسبة للشجرة العامة، يتم تحديد المسار بواسطة الخط، حيث r هو إنشاء الجذر، s هو الانتقال إلى الابن الأكبر، b هو الانتقال إلى أخ)؛

سأعطي مثالا:

+r 1
+ 2
+ 3
+ 3
+s 5
+sb 6
+sb 7

وستكون النتيجة شجرة مثل هذا:

1
  2
    5
  3
    6
    7
  3

أولاً، لنقم بإنشاء وظيفة تضيف قمة، أي تخصيص ذاكرة للقمة وتمرير مؤشر إلى هذه القمة (في البداية غير متصلة بأي شيء).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //обнуляем указатели к братьям и сыновьям, независимая вершина, которая хранит value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

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

لاحظ أن Node**tree تقوم بتمرير البنية، وليس نسخها. يمنحنا هذا القدرة على تغيير الأشياء التي لا يمكننا فعلها باستخدام إعلان Node *tree.

بشكل عام، يجب أن نجد مؤشرًا للقمة التي نحتاج إلى إضافة الابن إليها:

Node* add_node(Node **tree, const char *a) {
  Node* t = *tree;
  int value;
  scanf("%d", &value);
  int i = 0;
      while (a[++i] != ' ') {
        if (a[i] == 'r') {
            *tree = create_tree(value); // создаем корень
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // функция, которая возвращает указатель на сына
            continue;
          return NULL; //иначе NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) //возвращает указатель на брата t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // мы перешли к вершине, к которой хотели 
   //и теперь идем к последнему ее сыну,
   //чтобы добавить в конец списка
    t->brother = create_tree(value);
    return t->brother;
    }
    else {//если сына нет, то создадим его
      t->son = create_tree(value);
      return t->son;
    }
}

هذه هي الطريقة التي نبني بها شجرة.

ملحوظة: هذا هو مقالي الأول، لذا يرجى عدم الحكم بقسوة شديدة

المصدر: www.habr.com