واحد ، تعريف شجرة الفرز الثنائي
1. تعريف شجرة الفرز الثنائي <br /> شجرة فرز ثنائي (شجرة الفرز الثنائي) ، والمعروفة أيضًا باسم شجرة البحث الثنائية. يتم تعريفه على أنه: شجرة فرز ثنائية أو شجرة فارغة ، أو شجرة ثنائية تلبي الخصائص التالية:
① إذا لم تكن الشجرة الفرعية اليسرى فارغة ، فإن قيم جميع العقد على الشجرة الفرعية اليسرى أصغر من قيمة عقدة الجذر ؛
② إذا لم تكن الشجرة الفرعية اليمنى فارغة ، فإن قيم جميع العقد على الشجرة الفرعية اليمنى أكبر من قيم عقدة الجذر ؛
tructes الفرعية اليسرى واليمين نفسها هي كل شجرة فرز ثنائية.
يشار إلى الخصائص أعلاه باسم خاصية شجرة الفرز الثنائية (خاصية BST) ، وبالتالي فإن شجرة الفرز الثنائية هي في الواقع شجرة ثنائية ترضي خاصية BST.
2. خصائص شجرة الفرز الثنائية <br /> نقل شجرة الفرز الثنائية بالترتيب المتوسط ، وتسلسل اجتياز الترتيب المتوسط الناتج هو تسلسل ترتيب تدريجي.
3. أدخل شجرة الفرز الثنائية <br /> أدخل عقدة جديدة في شجرة الفرز الثنائية ، لضمان أن شجرة الثنائية المدرجة لا تزال تلبي تعريف شجرة الفرز الثنائية.
عملية إدراج:
إذا كانت شجرة الفرز الثنائية فارغة ، يتم إدخال العقدة في الشجرة الفارغة كعقدة الجذر ؛
عندما لا يكون فارغًا ، قارن مفتاح الكلمة الرئيسية S-> المراد إدراجها باستخدام مفتاح الكلمة الأساسية لجذر الشجرة T->. إذا كان المفتاح s-> = t-> ، فلا داعي لإدراجه. إذا كان مفتاح S-> <T-> ، يتم إدخاله في الشجرة الفرعية اليسرى من الجذر. إذا كان مفتاح S-> T-> ، يتم إدراجه في الشجرة الفرعية اليمنى للجذر. عملية الإدراج في الشجرة الفرعية هي نفس عملية الإدراج في الشجرة. يستمر هذا حتى يتم إدراج العقدة في شجرة الفرز الثنائية كورقة جديدة ، أو حتى يتم العثور على الشجرة على عقد مع نفس الكلمات الرئيسية.
4. ابحث عن شجرة الفرز الثنائية <br /> على افتراض أن مؤشر الجذر لشجرة الفرز الثنائية هو جذر وقيمة الكلمة الرئيسية المعطاة هي k ، يمكن وصف خوارزمية البحث على النحو التالي:
① تعيين القيمة الأولية: q = الجذر ؛
② إذا كان k = q -> مفتاح ، يكون البحث ناجحًا وينتهي الخوارزمية ؛
③ خلاف ذلك ، إذا لم يكن مفتاح K <q －＞ والشجرة الفرعية اليسرى من Q فارغة ، يتم إرسال الشجرة الفرعية اليسرى من Q إلى Q ثم الخطوة ② ؛ خلاف ذلك ، يفشل البحث وينتهي الخوارزمية ؛
④ خلاف ذلك ، إذا كان مفتاح K ＞ Q ، والشجرة الفرعية اليمنى من Q ليست فارغة ، يتم إرسال الشجرة الفرعية اليمنى من Q إلى Q ثم الخطوة ② ؛ خلاف ذلك ، يفشل البحث وينتهي الخوارزمية.
5. حذف شجرة الفرز الثنائية <br /> لنفترض أن العقدة المحذوفة هي *p والآباء *f ، والتي لا تضيع في عمومية. افترض أن *P هو الطفل الأيسر لـ *f ، ويتم تقسيم ما يلي إلى ثلاث حالات:
⑴ إذا كانت العقدة *P عبارة عن عقدة ورقة ، فأنت بحاجة فقط إلى تعديل مؤشر العقدة الأم *f.
⑵ إذا كانت العقدة *P تحتوي فقط على الشجرة الفرعية اليسرى أو فقط في الشجرة الفرعية اليمنى ، فما عليك سوى جعل PL أو PR الشجرة الفرعية اليسرى من العقدة الأم.
⑶ إذا لم تكن الأشقتين الفرعية اليسرى واليمين من العقدة *p فارغة ، فابحث أولاً عن سلف الترتيب الأوسط (أو الخلف) من *p (لاحظ أن *s هي العقدة السفلية اليمنى في الشجرة الفرعية اليسرى من *p ، ومجال السلسلة اليمنى فارغة) ، ثم هناك طريقان: ① اسمحوا للدراسة الفرعية اليسرى *p مباشرة إلى السلسلة اليسرى من العدودة اليسرى *p ، و f ، و إلى السلسلة اليمنى من *P's Middle Order Comester Node *s. ② استبدل *P بعقدة سلف الترتيب الأوسط *S من *p (أي ، انسخ بيانات *s إلى *p) ، وسلسلة الشجرة الفرعية اليسرى من *s إلى سلسلة اليسار (أو اليمين) للعقدة الأصل *Q من *s.
6. اجتياز الأشجار الثنائية <br /> هناك ثلاث طرق لاجتياز الأشجار الثنائية ، على النحو التالي:
(1) اجتياز التمرير المسبق (DLR) ، أولاً الوصول إلى عقدة الجذر ، ثم اجتياز الشجرة الفرعية اليسرى ، وأخيراً اجتياز الشجرة الفرعية اليمنى. جذر مختصر - يسار - يمين.
(2) اجتياز الترتيب (LDR) ، أول اجتياز الشجرة الفرعية اليسرى ، ثم الوصول إلى عقدة الجذر ، وأخيراً اجتياز الشجرة الفرعية اليمنى. ملاحظة مختصرة: اليمين الأيسر.
(3) اجتياز ما بعد الترتيب (LRD) ، والعبور أولاً في الشجرة الفرعية اليسرى ، ثم اجتياز الشجرة الفرعية اليمنى ، وأخيراً الوصول إلى عقدة الجذر. جذر اليمين الأيسر المختصر.
2. كتابة الكود
1. تعريف فئة عقدة الشجرة 0
حزمة com.lin ؛ / ** * ملخص الوظيفة: */ الفئة العامة treeNode {بيانات عدد صحيح عامة ؛ /* العقدة الأصل من هذه العقدة*/ Public TreeNode Parent ؛ /*اليسار عقدة الطفل من هذه العقدة*/ اليسار treeNode العام ؛ /*عقدة الطفل الصحيح لهذه العقدة*/ treenode public right ؛ public treenode (بيانات عدد صحيح) {this.data = data ؛ } Override public string toString () {return "treenode [data =" + data + "]" ؛ }} 2. تعريف شجرة الفرز الثنائية
حزمة com.lin ؛ /*** ملخص الوظيفة: فرز/شجرة ثنائية متوازنة*/فئة عامة SearchTree {public treenode root ؛ الحجم الطويل العام ؛ / ** * أضف عقدة إلى TREE * PARAM DATA * RETURN BOOLEAN إدخال TRUE */ Public Boolean AddTreeNode (بيانات Integer) {if (null == root) {root = new treenode (data) ؛ System.out.println ("تم إدراج البيانات بنجاح في الشجرة الثنائية المتوازنة") ؛ العودة صحيح. } treenode treenode = treeNode جديد (بيانات) ؛ // يتم إدراج البيانات treeNode currentNode = root ؛ Treenode ParentNode ؛ بينما (true) {parentNode = currentNode ؛ // احفظ عقدة الأصل // البيانات التي تم إدخالها أصغر من العقدة الأصل if (currentnode.data> data) {currentNode = currentNode.left ؛ . treenode.parent = parentNode ؛ System.out.println ("تم إدراج البيانات بنجاح في شجرة البحث الثنائية") ؛ حجم ++ ؛ العودة صحيح. } // البيانات التي تم إدخالها أكبر من العقدة الأصل} أخرى إذا (currentNode.data <data) {currentNode = currentNode.right ؛ . treenode.parent = parentNode ؛ System.out.println ("يتم إدراج البيانات بنجاح في شجرة البحث الثنائية") ؛ حجم ++ ؛ العودة صحيح. }} آخر {system.out.println ("بيانات الإدخال هي نفس بيانات العقدة") ؛ العودة كاذبة }}} / ** * param data * return treenode * / public treenode findTreeNode (Integer Data) {if (null == root) {return null ؛ } treenode current = root ؛ بينما (current! = null) {if (current.data> data) {current = current.left ؛ } آخر إذا (current.data <data) {current = current.right ؛ } آخر {return current ؛ }} الإرجاع null ؛ }} فيما يلي طريقة للإضافة والبحث
3. الجبهة والمتوسطة والخلفية اجتياز
حزمة com.lin ؛ استيراد java.util.stack ؛ / *** ملخص الوظيفة:*/ public class treeorder {/ *** التنفيذ المتكرر لـ preorder traversal* author linbingwen* since 29 أغسطس ، 2015* param treenode*/ public static void preordermethodone (treenode treenode) {if (null! = treenode) if (null! = treenode.left) {preorderMethodone (treeNode.left) ؛ } if (null! = treenode.right) {preorderMethodone (treeNode.Right) ؛ }}} / *** LOOPING لتنفيذ تمرير preorder* param treenode* / public static void preorderMethodTwo (treenode treenode) {if (null! = treenode) {stack <Treenode> stack = new stack <Treenode> () ؛ stack.push (treenode) ؛ بينما (! stack.isempty ()) {treenode tempnode = stack.pop () ؛ System.out.print (tempnode.data + "") ؛ // عقدة الطفل الصحيحة ليست فارغة ، ضع عقدة الطفل الصحيحة في if (null! = tempnode.right) {stack.push (tempnode.right) ؛ } // بعد وضع عقدة الطفل الأيمن ، ضع عقدة الطفل اليسرى ، واتخذها إذا (null! = tempnode.left) {stack.push (tempnode.left) ؛ }}}} / *** تنفيذ متكرر عبر الترتيب* param treenode* / public static void medordermethodone (treenode treenode) {if (null! = treenode) {if (null! = treenode.left) {medordermethodone (treenode.left) ؛ } system.out.print (treenode.data + "") ؛ if (null! = treenode.right) {medordermethodone (treenode.right) ؛ }}} / *** تنفيذ LOOP في الترتيب عبر الترتيب* param treenode* / public static void medordermethodtwo (treenode treenode) {stack <TreeNode> stack = new stack <Treenode> () ؛ TreeNode Current = TreeNode ؛ بينما (current! = null ||! stack.isempty ()) {بينما (current! = null) {stack.push (current) ؛ الحالي = current.left ؛ } if (! stack.isempty ()) {current = stack.pop () ؛ System.out.print (current.data+"") ؛ الحالي = current.right ؛ }}} / *** تنفيذ متكرر بعد الترتيب* param treeNode* / public static void postordermethodone (treenode treenode) {if (null! = treenode) {if (null! = treenode.left) {treenode.left) ؛ } if (null! = treenode.right) {postorderMethodone (treeNode.Right) ؛ } system.out.print (treenode.data + "") ؛ }} / *** looping لتنفيذ traversal بعد الترتيب* param treeNode* / public static void postordermethodtwo (treenode treenode) {if (null! = treenode) {stack <Treenode> stack = new stack <treenode> () ؛ TreeNode Current = TreeNode ؛ treenode rightNode = null ؛ بينما (current! = null ||! stack.isempty ()) {بينما (current! = null) {stack.push (current) ؛ الحالي = current.left ؛ } current = stack.pop () ؛ بينما (current! = null && (current.right == null || current.right == rightNode)) {system.out.print (current.data + "") ؛ RightNode = الحالي ؛ if (stack.isempty ()) {system.out.println () ؛ يعود؛ } current = stack.pop () ؛ } stack.push (current) ؛ الحالي = current.right ؛ }}}} 4. كيفية الاستخدام
حزمة com.lin ؛ / ** * ملخص الوظيفة: */ الفئة العامة SearchTreetest {/ ** * param args */ public static void main (string [] args) {searchtree tree = new SearchTree () ؛ tree.addtreeNode (50) ؛ tree.addtreeNode (80) ؛ tree.addtreeNode (20) ؛ tree.addtreeNode (60) ؛ tree.addtreeNode (10) ؛ tree.addtreeNode (30) ؛ tree.addtreeNode (70) ؛ tree.addtreeNode (90) ؛ tree.addtreeNode (100) ؛ tree.addtreeNode (40) ؛ System.out.println("===================================================================================================== ========================================================== =========================================================== ========================================================== =========================================================== =========================================================== =========================================================== System.out.println ("============================================== ================================================================ ================================================================ ================================================================ ================================================================ ================================================================ ================================================================ ================================================================ Treeorder.postorderMethodone (tree.root) ؛ System.out.println("====================================================================================================== =========================================================== ============================================================= =========================================================== ============================================================= =========================================================== ============================================================= System.out.println ("============================================== ================================================================ ================================================================ ================================================================ ================================================================ ================================================================ ================================================================ ================================================================ treeorder.medordermethodtwo (tree.root) ؛نتيجة الإخراج:
وبالمثل ، فإن عملية البحث هي كما يلي:
treenode node = tree.findtreeNode (100) ؛ System.out.println (Node) ؛
النتيجة صحيحة
ما سبق هو مقدمة مفصلة لشجرة فرز جافا الثنائية. آمل أن يكون ذلك مفيدًا لبرمجة Java الخاصة بكل شخص.