إنشاء الأشجار الثنائية ورموز مثال اجتياز مختلفة في جافا

هذا سؤال شائع للمقابلة ، مثل الحصول على اجتياز التسلسل الهرمي للشجرة الثنائية من خلال الترتيب المسبق والترتيب للشجرة الثنائية ، إلخ.

preorder + الترتيب الأوسط -> بناء

لنفترض أن هناك الآن شجرة ثنائية ، على النحو التالي:

في هذا الوقت ، يكون ترتيب اجتياز:

 preorder: gdafemhz inorder: adefghmz postorder: aefdhzmg

الآن قم بإعطاء ترتيب مسبقًا وترتيبًا (inorder) ، أو إنشاء شجرة ثنائية أو ترتيب (inorder) وبعد الترتيب (postorder) ، قم بإنشاء شجرة ثنائية ، فهي في الواقع هي نفسها

تعريف عقدة الشجرة:

 شجرة الفئة {char val ؛ شجرة اليسار ؛ شجرة يمين ؛ شجرة (char val ، شجرة اليسار ، الشجرة يمينًا) {this.val = val ؛ this.left = left ؛ this.right = right ؛

تحقيق إنجازات:

 BuildTree BuildTree الثابتة العامة (char [] preorder ، char [] inorder) {// preorder هو تسلسل preorder // inorder هو التسلسل الأوسط إذا (preorder == null || preorder.length == 0) {return null ؛} tree root = new tree (preorder [0]) ؛ لـ (char i = 0 ؛ i <inorder.length ؛ i ++) {if (inorder [i] == root.val) {inorderIndex = i ؛}} // tratree sub traute و insereex preorderleft char [] char [] 1+inorderIndex ، preorder.length) ؛ // الجزء الفرعي الأيسر والجزء الفرعي الأيمن من inorder char [] inorderleft = arrays.copyofrange (inorder ، 0 ، inorderIndex) ؛ char [] BuildTree (preorderleft ، inorderleft) ؛ Tree RightChild = BuildTree (preorderRight ، inorderRight) ؛ root.left = LeftChild ؛ root.right = rightchild ؛ Return Root ؛}

في الواقع هو نفسه لإنشاء طلب متوسط + بعد الترتيب. لن أكتبها هنا

العديد من الترافاز

بعد الترتيب

 postorderprint postorderprint الثابتة العامة (Tree Root) {// tairversal اللاحقة // الجذور اليسرى اليسرى واليمين إذا (root.left! = null) {postorderPrint (root.left) ؛ } if (root.right! = null) {postorderPrint (root.right) ؛ } system.out.print (root.val + "") ؛ }

تعلم من مثال واحد والترتيب هو نفس الترتيب في الوسط. لن أكتبها هنا

طبقة تسلسل اجتياز

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

 public static void layerorderprint (tree root) {if (root == null) {return ؛ } // قائمة انتظار Sequence Termence Termence <Tree> qe = new LinkedList <Tree> () ؛ qe.add (الجذر) ؛ بينما (! qe.isempty ()) {tree node = qe.poll () ؛ system.out.print (node.val + "") ؛ if (node.left! = null) {qe.add (node.left) ؛ } if (node.right! = null) {qe.add (node.right) ؛ }}}

عمق واتساع الأولوية

في الواقع ، إنه مجرد قول مختلف. أولوية العمق هي اجتياز التمرير المسبق ، والأولوية الواسعة هي اجتياز الطبقة.

 الفراغ الثابت العام deepfirstprint (جذر الشجرة) {// عبور الأولوية العميقة يعادل عبور المسبق // حتى تتمكن من استخدام التمرير المسبق بشكل مباشر إذا (root == null) {return ؛ } system.out.print (root.val + "") ؛ if (root.left! = null) {deepfirstPrint (root.left) ؛ } if (root.right! = null) {deepfirstPrint (root.right) ؛ }} public static static void deepfirstprintnonerec (tree root) {// الشكل غير المتجانس لتجاوز أولوية العمق إذا (root == null) {return ؛ } stack <tree> st = new stack <tree> () ؛ St.add (الجذر) ؛ بينما (! st.isempty ()) {tree node = st.pop () ؛ system.out.print (node.val + "") ؛ // عاد المكدس إلى الداخل وأولي // أضف الطفل الأيمن أولاً ثم الطفل الأيسر إذا (node.right! = null) {st.Add (node.right) ؛ } if (node.left! = null) {st.Add (node.left) ؛ }}}

الوظيفة الرئيسية:

 public static void main (string [] args) {char [] preorder = "gdafemhz" .tochararray () ؛ char [] inorder = "adefghmz". tochararray () ؛ Tree Root = main.buildtree (preorder ، inorder) ؛ // main.postorderPrint (root) ؛ // postorder traversal // main.layerorderPrint (root) ؛ // طبقة تسلسل اجتياز // main.deepfirstprint (root) ؛ // priorit deep traversal // main.deepfirstprintnonerec (root) ؛ // النسخة غير المثيرة للعمق الأول}

لخص

ما ورد أعلاه هو كل شيء عن إنشاء الأشجار الثنائية ورموز مثال اجتياز مختلفة في جافا. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى هذا الموقع:

" مقدمة لطريقتين للنسخ المتطابق في جافا برمجة الأشجار الثنائية "

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

مسار شجرة جافا ثنائي ومثال كود

إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!