تصف هذه المقالة خوارزميات اجتياز العرض الأول للعمق والتوقيت الأول التي تنفذ شجرة ثنائية في جافا. شاركه للرجوع إليه ، على النحو التالي:
1. التحليل
إن الممارسة الشائعة لعدم توحيد العمق الأول للأشجار الثنائية هي تبني كومة ، والممارسة الشائعة المتمثلة في عدم توزيع اجتياز العرض الأول هي تبني قائمة انتظار.
اجتياز العمق الأول : يمكن اختراق كل مسار فرع ممكن حتى لا يمكن أن يكون عمقًا ، ولا يمكن الوصول إلى كل عقدة إلا مرة واحدة. تجدر الإشارة إلى أن اجتياز الشجرة الثنائية عمقًا مميزًا جدًا ويمكن تقسيمه إلى اجتياز ما قبل الترتيب ، اجتياز الوسيط ، والاختلاط اللاحق. الوصف المحدد هو كما يلي:
اجتياز الترتيب الأول : بالنسبة لأي شجرة فرعية ، قم أولاً بالوصول إلى الجذر ، ثم اجتياز الشجرة الفرعية اليسرى ، وأخيراً اجتياز الشجرة الفرعية اليمنى.
اجتياز الترتيب الأوسط : بالنسبة لأي شجرة فرعية ، اجتاز أولاً الشجرة الفرعية اليسرى ، ثم الوصول إلى الجذر ، وأخيراً اجتياز الشجرة الفرعية اليمنى.
اجتياز ما بعد الترتيب : بالنسبة لأي شجرة فرعية ، اجتازت الشجرة الفرعية اليسرى أولاً ، ثم اجتازت الشجرة الفرعية اليمنى ، وأخيراً الوصول إلى الجذر.
اتساع العرض الأول : المعروف أيضًا باسم التسلسل الهرمي ، والوصول إلى كل طبقة من الأعلى إلى الأسفل بدوره. في كل طبقة ، وصول العقد من اليسار إلى اليمين (أو من اليمين إلى اليسار). بعد الوصول إلى طبقة واحدة ، ستدخل الطبقة التالية حتى لا توجد عقد يمكن الوصول إليها.
2. أعط أمثلة
تتطلب شجرة الفرز الثنائية الموضحة في الشكل أدناه استخدام اجتياز ما قبل الطلب (العودية ، غير المتكررة) ، عبر الترتيب (العودية ، غير المثيرة للإعجاب) ، اجتياز ما بعد الحدود (العودية ، غير المليئة بالمرور) ، والتمرير العرضي.
① رمز المرجع
Package BinaryTreetRaversetest ؛ Import Java.Util.LinkedList ؛ استيراد java.util.queue ؛/** * عمق أولوية اجتياز واتساع أولوية التجارة من الأشجار الثنائية * @Author Fantasy * void invidence 1.0 2016/05 - 2016/10/07 */public class pinarnertraest { BinarySorttree <integer> tree = new BinarySorttree <integer> () ؛ tree.insertnode (35) ؛ tree.insertnode (20) ؛ tree.insertnode (15) ؛ tree.insertnode (16) ؛ tree.insertnode (29) ؛ tree.insertnode (28) ؛ tree.insertnode (30) ؛ tree.insertnode (40) ؛ tree.insertnode (50) ؛ tree.insertnode (45) ؛ tree.insertnode (55) ؛ system.out.print ("preorder traversal (العودية):") ؛ tree.preordertraverse (tree.getroot ()) ؛ System.out.println () ؛ system.out.print ("inderder termversal (العودية):") ؛ tree.inordertraverse (tree.getroot ()) ؛ System.out.println () ؛ system.out.println () ؛ system.out.print ("اجتياز ما بعد الطلب (العودية):") ؛ tree.postordertraverse (tree.getroot ()) ؛ system.out.println () ؛ system.out.print ("arversal recursive (غير متكرر):") ؛ tree.preordertraversenorecursion (tree.getroot ()) ؛ system.out.println () ؛ system.out.print ("inderder termversal (غير متكرر):") ؛ tree.inordertraversenorecursion (tree.getroot ()) ؛ System.out.println () ؛ system.out.println () ؛ System.out.print ("اجتياز ما بعد الطلب (غير متكرر):") ؛ tree.postordertraversenorecursion (tree.getRoot ()) ؛ system.out.println () ؛ system.out.print ("trenderpriority traversal:") ؛ tree.breadthfirsttraverse (tree.getroot ()) ؛ }}/*** node*/class node <e تمتد قابلة للمقارنة <e >> {e value ؛ عقدة <e> اليسار ؛ عقدة <e> اليمين ؛ العقدة (e قيمة) {this.value = value ؛ اليسار = فارغ ؛ اليمين = فارغ ؛ }}/** * استخدم تسلسلًا سابقًا لإنشاء شجرة فرز ثنائية (تُعرف أيضًا باسم شجرة البحث الثنائية) */class binarysorttree <e يمتد قابلة للمقارنة <e >> {node private <e> root ؛ BinarySorttree () {root = null ؛ } public void insertNode (e value) {if (root == null) {root = new node <e> (value) ؛ يعود؛ } العقدة <e> currentNode = root ؛ بينما (true) {if (value.compareto (currentNode.value)> 0) {if (currentNode.Right == null) {currentNode.Right = new node <e> (value) ؛ استراحة؛ } currentNode = currentNode.right ؛ } else {if (currentNode.left == null) {currentNode.left = new node <e> (value) ؛ استراحة؛ } currentNode = currentNode.left ؛ }}} العقدة العامة <e> getRoot () {return root ؛ } / ** * اجتياز المسبق للشجرة الثنائية (العودية) * param node * / public void preordertraverse (node <e> node) {system.out.print (node.value + "") ؛ if (node.left! = null) preorderTraverse (node.left) ؛ if (node.right! = null) preorderTraverse (node.right) ؛ } / ** * عبر الترتيب الشجرة الثنائية (العودية) * param node * / public void inordertraverse (node <e> node) {if (node.left! = null) inordertraverse (node.left) ؛ System.out.print (node.value + "") ؛ if (node.right! = null) inordertraverse (node.right) ؛ } / ** * اجتياز ما بعد الترتيب للشجرة الثنائية (العودية) * param node * / public void postordertraverse (node <e> node) {if (node.left! = null) postordertraverse (node.left) ؛ if (node.right! = null) postordertraverse (node.right) ؛ System.out.print (node.value + "") ؛ } / ** * اجتياز المسبق للشجرة الثنائية (غير متكرر) * param root * / public void preordertraversenorecursion (node <e> root) {linkedList <node <e >> stack = new LinkedList <عقدة <e>> () ؛ العقدة <e> currentNode = null ؛ stack.push (الجذر) ؛ بينما (! stack.isempty ()) {currentNode = stack.pop () ؛ System.out.print (currentNode.value + "") ؛ if (currentnode.right! = null) stack.push (currentNode.Right) ؛ if (currentNode.left! = null) stack.push (currentNode.left) ؛ }} / ** * عبر الترتيب عبر الشجرة الثنائية (غير متكرر) * param root * / public void inordertraversenorecursion (node <e> root) {LinkedList <node <e >> stack = new LinkedList <node <e >> () ؛ العقدة <e> currentNode = root ؛ بينما (currentNode! = null ||! stack.isempty ()) {// loop حتى عقدة الورقة اليسرى في شجرة الفرز الثنائية (CurrentNode null) بينما (currentNode! = null) {stack.push (currentNode) ؛ CurrentNode = currentNode.left ؛ } currentNode = stack.pop () ؛ System.out.print (currentNode.value + "") ؛ CurrentNode = currentNode.right ؛ }} / ** * اجتياز ما بعد الترتيب للشجرة الثنائية (غير متكررة) * param root * / public void postordertraversenorecursion (Node <e> root) {LinkedList <node <e>> stack = new linkedlist <node <e >> () ؛ العقدة <e> currentNode = root ؛ العقدة <e> rightNode = null ؛ بينما (currentNode! = null ||! stack.isempty ()) {// loop حتى عقدة الورقة في أقصى اليسار من شجرة الفرز الثنائية (CurrentNode null) بينما (currentNode! = null) {stack.push (currentNode) ؛ CurrentNode = currentNode.left ؛ } currentNode = stack.pop () ؛ // لا تحتوي العقدة الحالية على العقدة اليمنى أو العقدة السابقة (العقدة التي تم إخراجها) هي العقدة الصحيحة للعقدة الحالية ، ثم يتم إخراج العقدة الحالية بينما (currentnode.right == null || currentnode.right == rightnode) {system.out.print (currentnode.value + "") ؛ rightNode = currentNode ؛ if (stack.isempty ()) {return ؛ // مخرجات الجذر ، ينتهي اجتياز} currentNode = stack.pop () ؛ } stack.push (currentNode) ؛ // لا تزال هناك العقدة الصحيحة التي لا تتجاوز currentNode = currentNode.right ؛ }} / *** الشجرة الثنائية عبر العرض ، والمعروفة أيضًا باسم الشجرة الثنائية التسلفية الهرمية* param node* / public void residthfirsttraverse (node <e> root) {Queue <node <e >> Queue = new linkedlist <e e >> () ؛ العقدة <e> currentNode = null ؛ Queue.Offer (الجذر) ؛ بينما (! queue.isempty ()) {currentNode = queue.poll () ؛ System.out.print (currentNode.value + "") ؛ if (currentNode.left! = null) Queue.offer (currentNode.left) ؛ if (currentnode.right! = null) Queue.offer (currentNode.Right) ؛ }}}② نتيجة الإخراج
اجتياز مسبق (العودية): 35 20 15 16 29 28 30 40 40 50 45 55
عبر الترتيب (عودية): 15 16 20 28 29 30 35 40 45 50 55
اجتياز ما بعد الحدود (عودة): 16 15 28 30 29 20 45 55 50 40 35
اجتياز مسبق (غير متكرر): 35 20 15 16 29 28 30 40 50 45 55
عبر الترتيب (غير متكرر): 15 16 20 28 29 30 35 40 45 50 55
اجتياز ما بعد الحدود (غير متكرر): 16 15 28 30 29 20 45 55 50 40 35
اتساع أولوية اجتياز: 35 20 40 15 29 50 16 28 30 45 55
لمزيد من المعلومات حول خوارزميات Java ، يمكن للقراء المهتمين بهذا الموقع عرض الموضوعات: "بنية بيانات Java وبرنامج تعليمي الخوارزمية" ، "ملخص" Tips Java ".
آمل أن يكون هذا المقال مفيدًا لبرمجة Java للجميع.