ربما حاول الكثيرون العثور على بناء شجرة عامة ، لكن محرك البحث لم يجد سوى تلك الثنائية ... شجرة البحث الثنائية ، اجتياز الشجرة الثنائية والعديد من الخوارزميات الأخرى.
نعم ، في الواقع ، لا يتم استخدام الشجرة العامة في أي مكان ، والتجاوز بطيء ، وحالات الاستخدام صغيرة.
لذا ، طرحت هذا السؤال والآن سأشرح كيف يتم بناء الشجرة. لذلك ، من الناحية المثالية ، يجب أن تخزن بنية شجرة الشكل العام ثلاثة متغيرات:
- مؤشر الابن البكر
- مؤشر للأخ
- البيانات التي ستقوم بتخزينها
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;
يجب عليك أيضًا إنشاء دالة تعالج سلسلة المسار (+ bs ...). في كل مرة نبدأ في اجتياز الجذر ، إذا لم يتم إنشاؤه ، فإننا نطبع NULL (لا يمكننا فعل شيء). إذا لم يكن هناك ذروة ، فعلينا أن ننشئها. انتقل إلى إنشاء وظيفة شجرة والحصول على مؤشر إلى الجذر.
ملاحظة: عقدة ** شجرة يمر هيكل ، وليس نسخ. هذا يعطينا القدرة على تغيير ما لا يمكن القيام به ، على عكس إعلان شجرة Node *.
بشكل عام ، يجب أن نجد مؤشرًا إلى الأعلى ، نحتاج إلى إضافة ابن إليه:
Node* add_node(Node **tree, const char *a) { Node* t = *tree; int value; scanf("%d", &value); int i = 0; while (a[++i] != '\0') { if (a[i] == 'r') { *tree = create_tree(value);
بهذه الطريقة نبني شجرة.
PS هو مقالي الأول ، لذا يرجى عدم الحكم بدقة