تصف لغة جافا عمق وعرض شجرة ثنائية

يشرح:

عمق الشجرة الثنائية: يتم تشكيل مسار إلى الشجرة من عقدة الجذر إلى العقدة (بما في ذلك عقدة الجذر والأوراق) التي تمر بواسطة عقدة الورقة بدورها. طول المسار الأطول هو عمق الشجرة.
عرض شجرة ثنائية: كل طبقة من شجرة ثنائية لها عدد معين من العقد. يسمى عدد العقد في الطبقة مع أكبر عدد من العقد بعرض الشجرة الثنائية.

الفكرة: التنفيذ المتكرر.

1. يمكن اعتبار كل عقدة عقدة جذر
2. عمق عقدة الجذر (أي عقدة) يساوي الحد الأقصى لعمق الشجرة اليسرى أو اليمنى +1
3. ابدأ في اجتياز عقدة الجذر. إذا كنت تتجول إلى عقدة الورقة ، فإن العمق هو 0

 . } int dl = depth (root.leftchild) ؛ int dr = depth (root.rightchild) ؛ إرجاع DL> DR؟ DL+1: DR+1 ؛ }

2. عرض الشجرة الثنائية

الفكرة: أضف عدادًا أثناء اجتياز تسلسل الطبقة لتسجيل عدد العقد في كل طبقة

1. عندما تكون كل طبقة خارج قائمة الانتظار ، فإن عدد العقد في الطبقة التالية هو في الواقع حجم () قائمة الانتظار.
2. في نهاية كل عبور طبقة ، قارن الحد الأقصى للعرض مع العدد الحالي من العقد وتسجيل القيمة القصوى.

 عرض int ثابت عام (جذر العقدة) {if (root == null) return 0 ؛ قائمة الانتظار <Node> q = new LinkedList <Node> () ؛ q.add (root) ؛ int width = 1 ؛ q.poll () ؛ if (node.leftchild! = null) {q.add (node.leftchild) ؛} if (node.rightchild! = null) {Q.Add (node.rightchild) ؛}} len = q.size () ؛ بعد كل طبقة نهايات ، قم بتسجيل عدد الدودة في المرتبة التالية = ch. العرض: Q.Size () ؛} عرض الإرجاع ؛}

لخص

ما سبق هو كل شيء عن وصف لغة جافا لعمق وعرض الشجرة الثنائية. آمل أن يكون ذلك مفيدًا للجميع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!