يظهر التمثيل المرئي للمفاهيم التي تمت مناقشتها في الشكل أدناه:
يشرح هذا الدليل عملية طباعة جميع العقد الورقية للشجرة الثنائية من خلال تغطية الأقسام المذكورة أدناه:
- كيفية التعرف على العقد الورقية؟
- كيفية طباعة كافة العقد الورقية لشجرة ثنائية من اليسار إلى اليمين في جافا سكريبت؟
- نصيحة إضافية: طباعة العقد الورقية لشجرة ثنائية من الاتجاه الأيمن إلى اليسار
- خاتمة
كيفية التعرف على العقد الورقية؟
ال ' ورقة 'العقد هي تلك التي لا تحتوي على عقد فرعية، أو على وجه التحديد التي تحتوي على' ارتفاع ' ل ' 0 '. إذا كانت العقدة تحتوي على ' ارتفاع ' أكثر من ' 0 'ثم يمكن أن تكون تلك العقدة هي العقدة الداخلية أو العقدة الجذرية. ال ' ورقة عادةً ما يتم تعقب العقد لتحديد المصدر الأصلي الذي تم إنشاء هذه العقدة منه. يتم استخدامه في الغالب في خوارزميات البحث أو اكتشاف الأخطاء للعثور على سبب الخطأ أو المشكلة.
كيفية طباعة كافة العقد الورقية لشجرة ثنائية من اليسار إلى اليمين في جافا سكريبت؟
هناك طريقتان ' العودية ' و ' ترابطي 'لتحديد جميع العقد الورقية المتوفرة في الشجرة الثنائية المتوفرة بالشكل المطلوب' غادر ' ل ' يمين ' اتجاه. يتم توضيح التنفيذ العملي لهذه الأساليب في الأقسام المذكورة أدناه:
- طباعة جميع العقد الورقية للشجرة الثنائية من اليسار إلى اليمين بشكل متكرر
- طباعة كافة العقد الورقية لشجرة ثنائية باستخدام النهج التكراري
الطريقة الأولى: طباعة كافة العقد الورقية للشجرة الثنائية من اليسار إلى اليمين بشكل متكرر
النهج العودي يختار كافة العقد في أ خوارزمية البحث بالعمق الأول الطريقة التي تعبر أولاً العقد الموجودة على الجانب الأيسر بالكامل ثم العقدة الوسطى والعقد الموجودة على الجانب الأيمن في النهاية. يتم تنفيذ هذه العملية بشكل متكرر لكل عقدة وعندما لا يكون هناك مزيد من اجتياز ' ورقة يتم تحديد العقد. لفهم هذا المفهوم بشكل أفضل، قم بزيارة مقتطف الشفرة أدناه:
فصل العقدة{
البناء ( )
{
هذا . محتوى = 0 ;
هذا . غادر = باطل ;
هذا . يمين = باطل ;
}
} ;
حيث عرضLeafNodes = ( عقدة الجذر ) =>
{
لو ( عقدة الجذر == باطل )
يعود ;
لو ( عقدة الجذر. غادر == باطل && عقدة الجذر. يمين == باطل )
{
وثيقة. يكتب ( عقدة الجذر. محتوى + ' ' ) ;
يعود ;
}
لو ( عقدة الجذر. غادر != باطل )
this.displayLeafNodes ( عقدة الجذر. غادر ) ;
لو ( عقدة الجذر. يمين != باطل )
this.displayLeafNodes ( عقدة الجذر. يمين ) ;
}
كان SampleNode = ( فال ) =>
{
كان tempNode = جديد العقدة ( ) ;
tempNode. محتوى = فال ;
tempNode. غادر = باطل ;
tempNode. يمين = باطل ;
يعود tempNode ;
}
كان rootNode = provNode ( 3 ) ;
عقدة الجذر. غادر = provNode ( 6 ) ;
عقدة الجذر. يمين = provNode ( 9 ) ;
عقدة الجذر. غادر . غادر = provNode ( 12 ) ;
عقدة الجذر. غادر . يمين = provNode ( خمسة عشر ) ;
عقدة الجذر. غادر . يمين . يمين = provNode ( 24 ) ;
عقدة الجذر. يمين . غادر = provNode ( 18 ) ;
عقدة الجذر. يمين . يمين = provNode ( واحد وعشرين ) ;
this.displayLeafNodes ( عقدة الجذر ) ;
شرح كتلة التعليمات البرمجية أعلاه مذكور أدناه:
- أولاً، قم بإنشاء فئة باسم ' العقدة '، الذي ينشئ عقدة جديدة ويحدد قيمتها على' 0 '. المرفقة ' غادر ' و ' يمين 'تم تعيين العقد الجانبية على' باطل 'بشكل افتراضي باستخدام مُنشئ الفصل.
- بعد ذلك، حدد ' عرض الأوراق () 'وظيفة تقبل معلمة واحدة من' عقدة الجذر '. تعتبر هذه القيمة البارامترية بمثابة العقدة المحددة حاليًا للشجرة الثنائية.
- داخل الدالة ' لو 'يتم استخدام العبارة للتحقق مما إذا كان' عقدة الجذر 'فارغة أم لا. في حالة ' باطل 'توقف التنفيذ الإضافي لتلك العقدة. وفي الحالة الأخرى، فإن العقدة الجذرية ' غادر ' و ' يمين 'يتم فحص العقد الجانبية بحثًا عن' باطل '. إذا كان كلاهما خاليًا، فإن قيمة ذلك ' العقدة ' تتم طباعته.
- إذا كان ' غادر ' أو ' يمين 'العقدة ليست 'فارغة'، ثم قم بتمرير هذا الجانب من العقدة إلى ' عرض الأوراق () وظيفة 'للعملية العودية.
- تحديد وظيفة جديدة باسم ' عقدة () ' الذي يقبل المعلمة الوحيدة لـ ' فال '. داخل الوظيفة، قم بإنشاء مثيل جديد لـ ' العقدة 'فئة اسمها' tempNode '. تعيين المعلمة ' فال 'كقيمة لخاصية الفئة' محتوى ' وضبط ' غادر ' و ' يمين 'العقد الجانبية إلى' باطل ' بشكل افتراضي.
- وأخيرًا، قم بإنشاء كائن باسم ' عقدة الجذر 'ل' عقدة () ' وقم بتمرير قيمة العقدة كمعلمة الوظيفة هذه. قم بإنشاء العقد الجانبية اليمنى واليسرى عن طريق إضافة ' غادر ' و ' يمين 'الكلمات الرئيسية ذات 'rootNode' وتعيين قيمتها باستخدام نفس الوظيفة ' عقدة () '.
- ال ' غادر 'يعني الموضع الأيسر للعقدة الجذرية و' اليسار الأيسر 'الموضع يعني يسار اليسار ويتم تطبيق نفس النهج في حالة' يمين ' و ' يمين '
- بعد تعريف الشجرة، قم بتمرير 'rootNode' كوسيطة لـ ' عرضالعقد الرصاص () وظيفة لتحديد وطباعة جميع العقد الورقية للشجرة التي تم إنشاؤها.
يؤكد الإخراج الذي تم إنشاؤه بعد التجميع أنه تم استرداد العقدة الطرفية للشجرة المقدمة وطباعتها عبر وحدة التحكم:
الطريقة الثانية: طباعة جميع العقد الورقية للشجرة الثنائية باستخدام النهج التكراري
ال ' ترابطي 'المنهج هو النهج الأكثر كفاءة، فهو يستخدم مفهوم' يدفع ' و ' موسيقى البوب ' لتحديد ' ورقة 'العقد. النقاط الرئيسية أو عمل هذا النهج مذكورة أدناه:
فصل العقدة{
البناء ( قيمة )
{
هذا . بيانات = قيمة ;
هذا . غادر = باطل ;
هذا . يمين = باطل ;
}
} ;
حيث عرضLeafNodes = ( عقدة الجذر ) =>
{
لو ( ! عقدة الجذر )
يعود ;
اسمحوا القائمة = [ ] ;
قائمة. يدفع ( عقدة الجذر ) ;
بينما ( قائمة. طول > 0 ) {
عقدة الجذر = قائمة [ قائمة. طول - 1 ] ;
قائمة. موسيقى البوب ( ) ;
لو ( ! عقدة الجذر. غادر && ! عقدة الجذر. يمين )
وثيقة. يكتب ( عقدة الجذر. بيانات + ' ' ) ;
لو ( عقدة الجذر. يمين )
قائمة. يدفع ( عقدة الجذر. يمين ) ;
لو ( عقدة الجذر. غادر )
قائمة. يدفع ( عقدة الجذر. غادر ) ;
}
}
كان rootNode = جديد العقدة ( 3 ) ;
عقدة الجذر. غادر = جديد العقدة ( 6 ) ;
عقدة الجذر. يمين = جديد العقدة ( 9 ) ;
عقدة الجذر. غادر . غادر = جديد العقدة ( 12 ) ;
عقدة الجذر. غادر . يمين = جديد العقدة ( خمسة عشر ) ;
عقدة الجذر. غادر . يمين . يمين = جديد العقدة ( 24 ) ;
عقدة الجذر. يمين . غادر = جديد العقدة ( 18 ) ;
عقدة الجذر. يمين . يمين = جديد العقدة ( واحد وعشرين ) ;
this.displayLeafNodes ( عقدة الجذر ) ;
شرح الكود أعلاه مكتوب أدناه:
- أولاً قم بإنشاء ' العقدة 'فئة تتلقى معلمة واحدة' قيمة ' والتي تم تعيينها كقيمة للعقدة التي تم إنشاؤها حديثًا، ويتم تعيين الجانبين الأيسر والأيمن على قيمة خالية. تماما كما فعلت في المثال أعلاه.
- بعد ذلك، قم بإنشاء وظيفة ' عرض الأوراق () 'التي تقبل معلمة واحدة من' عقدة الجذر '. تعتبر هذه 'العقدة الجذرية' بمثابة الشجرة الثنائية ويتم فحص فراغها أولاً.
- إذا لم تكن العقدة فارغة، فستظهر قائمة فارغة تسمى ' قائمة ' يتم إنشاؤه و' عقدة الجذر 'يتم إدراج المعلمة فيه باستخدام' يدفع() ' طريقة.
- ثم '' بينما() 'يتم استخدامه والذي يتم تنفيذه حتى طول' قائمة '. داخل الحلقة، العنصر الموجود في أسفل الشجرة أو ' قائمة 'تتم إزالته باستخدام' البوب () ' طريقة.
- والآن أصبح وجود '' غادر ' و ' يمين تم التحقق من جوانب 'rootNode'، وإذا لم يكن كلا الجانبين موجودين، فهذا يعني أنه لا يوجد لديه عقدة فرعية. بعد ذلك، يتم عرض هذه العقدة على الشاشة ويتم تحديدها على أنها عقدة طرفية.
- إذا كانت هناك عقدة على الجانب الأيسر أو الأيمن فهذا يعني أن لديها أطفال. ثم أن ' غادر ' و ' يمين 'يتم دفع العقدة إلى' قائمة ' لمزيد من العملية للعثور على العقدة الورقية.
- في النهاية، قم بإنشاء شجرة ثنائية مخصصة عن طريق تمرير قيم العقدة كمعلمات لـ ' العقدة 'منشئ الفصل. بعد الإنشاء، قم بتمرير الشجرة 'rootNode' كوسيطة لـ ' عرض الأوراق () ' وظيفة.
يُظهر الإخراج الذي تم إنشاؤه بعد التجميع أنه تمت طباعة العقد الورقية للشجرة المقدمة:
نصيحة إضافية: طباعة العقد الورقية لشجرة ثنائية من الاتجاه الأيمن إلى اليسار
لاسترداد جميع العقد الطرفية التي لا تحتوي على عقد فرعية في ' يمين ' ل ' غادر الاتجاه، النهج العودي هو الأكثر الموصى به بسبب سهولته. على سبيل المثال، سيتم استخدام نفس الشجرة التي تمت مناقشتها في الأقسام أعلاه لاسترداد العقدة الطرفية ولكن في ' يمين ' إلى ' غادر 'الاتجاه كما هو موضح أدناه:
فصل العقدة{
البناء ( قيمة )
{
هذا . بيانات = قيمة ;
هذا . غادر = باطل ;
هذا . يمين = باطل ;
}
} ;
عرض الدالةLeafNodes ( جذر )
{
لو ( جذر == باطل )
{
يعود ;
}
لو ( جذر. غادر == باطل && جذر. يمين == باطل )
{
وثيقة. يكتب ( جذر. بيانات + ' ' ) ;
يعود ;
}
لو ( جذر. يمين != باطل )
{
this.displayLeafNodes ( جذر. يمين ) ;
}
لو ( جذر. غادر != باطل )
{
this.displayLeafNodes ( جذر. غادر ) ;
}
}
كان rootNode = جديد العقدة ( 3 ) ;
عقدة الجذر. غادر = جديد العقدة ( 6 ) ;
عقدة الجذر. يمين = جديد العقدة ( 9 ) ;
عقدة الجذر. غادر . غادر = جديد العقدة ( 12 ) ;
عقدة الجذر. غادر . يمين = جديد العقدة ( خمسة عشر ) ;
عقدة الجذر. غادر . يمين . يمين = جديد العقدة ( 24 ) ;
عقدة الجذر. يمين . غادر = جديد العقدة ( 18 ) ;
عقدة الجذر. يمين . يمين = جديد العقدة ( واحد وعشرين ) ;
this.displayLeafNodes ( عقدة الجذر ) ;
يعمل الكود المذكور أعلاه على النحو التالي:
- أولا الطبقة ' العقدة 'يتم إنشاؤه باستخدام المُنشئ الافتراضي لإضافة عقدة جديدة في الشجرة فقط الرابط الموجود في الأمثلة أعلاه.
- التالي ' عرضالعقد الرصاص () 'يتم إنشاء وظيفة تقبل معلمة واحدة من' عقدة الجذر '. يتم فحص هذه المعلمة لـ ' باطل 'الشرط عبر' لو ' إفادة.
- إذا كانت العقدة المقدمة غير صحيحة، فستكون ' غادر ' و ' يمين 'يتم فحص العقد الجانبية بحثًا عن' باطل ' حالة. إذا كان كلاهما خاليًا، فسيتم تحديد العقدة على أنها ' ورقة 'العقدة وطباعتها على صفحة الويب.
- بعد ذلك قم بتمرير ' يمين ' و ' غادر 'العقد من' عقدة الجذر ' إلى ' عرض الأوراق () ' وظيفة.
- قم بتخصيص موضع كل عقدة عن طريق إنشاء المثيلات باستخدام ' جديد 'الكلمة الرئيسية و' العقدة() 'المنشئ وتحديد الموضع كمعلمة المنشئ.
- ال ' غادر 'يعني الموضع الأيسر للعقدة الجذرية و' اليسار الأيسر 'الوضع يعني اليسار أو اليسار. ويتم تطبيق نفس النهج في حالة ' يمين ' و ' يمين '.
- وأخيراً قم بتمرير ' عقدة الجذر ' كحجة لـ ' عرضLeafNode() ' وظيفة.
يُظهر الإخراج الذي تم إنشاؤه أن العقد الورقية تتم طباعتها في الاتجاه من اليمين إلى اليسار.
يتعلق الأمر كله بطباعة جميع العقد الورقية للشجرة الثنائية في أي اتجاه مرغوب.
خاتمة
لطباعة جميع العقد الطرفية لشجرة ثنائية، قم بإنشاء فئة عشوائية تقوم بإنشاء وتعيين قيم لعقد الشجرة. بعد ذلك، قم بإنشاء دالة عشوائية تقبل عقدة واحدة من الشجرة في تسلسل هرمي من الأعلى إلى الأسفل. تحتوي هذه الوظيفة على عدة ' لو 'الشروط التي تتحقق مما إذا كان' العقدة 'ليس فارغًا ولا يحتوي على عقد في' غادر ' و ' يمين '، فإن تلك العقدة تعتبر بمثابة' ورقة ' ويتم عرضها على وحدة التحكم. لقد شرح هذا الدليل إجراء طباعة جميع العقد الورقية للشجرة الثنائية من اليسار إلى اليمين أو من اليمين إلى اليسار.