1. المفهوم
تصبح شجرة البحث الثنائية أيضًا شجرة فرز ثنائية. إنه له سمة أنه إذا كان للعقدة عقدتين طفلتين ، فيجب أن تكون راضية. يجب أن تكون قيمة عقدة الطفل الأيسر أصغر من قيمة العقدة ، ويجب أن تكون قيمة عقدة الطفل اليمنى أكبر من قيمة العقدة. لإجراء مقارنات بين الأنواع غير البارسية ، يمكن تنفيذ واجهة المقارنة. في هذه المقالة ، يتم استخدام بيانات النوع int للتشغيل.
لتنفيذ شجرة ثنائية ، يجب أن تبدأ بزيادة. فقط عن طريق بناء الشجرة يمكنك استخدام عمليات أخرى.
2. بناء شجرة البحث الثنائية
عند الحديث عن زيادة الأشجار الثنائية ، يجب علينا أولاً بناء فصل يمثل عقدة. تحتوي فئة العقدة على عدة سمات ، وقيمة العقدة ، والعقدة الأصل ، والعقدة اليسرى ، والعقدة اليمنى للعقدة. الرمز كما يلي
عقدة فئة ثابتة {العقدة الوالد ؛ عقدة اليسار. عقدة الحق. int val العقدة العامة (العقدة الأصل ، العقدة اليسارية ، العقدة اليمنى ، int val) {super () ؛ this.parent = الوالدين ؛ this.leftchild = LeftChild ؛ this.rightchild = rightchild ؛ this.val = val ؛ } العقدة العامة (int val) {this (null ، null ، null ، val) ؛ } العقدة العامة (عقدة العقدة ، int val) {this (node ، null ، null ، val) ؛ }}هنا نستخدم طريقة كتابة الفصل الداخلي. بعد بناء قيمة العقدة ، سنبني الشجرة بأكملها. يجب أن يكون للشجرة أولاً عقدة جذر ، ثم تمتد إلى العقد الفرعية المتبقية. في هذه الشجرة ، هناك أيضًا بعض السمات ، مثل جذر عقدة الجذر الأساسي وحجم العنصر في الشجرة. إذا تم استخدام هاتين السمة ، يمكن إضافة سمة المقارنة ، أو قد يتم توفير تطبيق افتراضي. الرمز المحدد كما يلي
فئة عامة SearchBinaryTree {Private Node Root ؛ حجم الباحث الخاص ؛ Public SearchBinaryTree () {super () ؛ }}3. إضافة
عند إضافة عناصر ، يجب أن تفكر في تهيئة عقدة الجذر. بشكل عام ، هناك نوعان: عند تهيئة مُنشئ هذه الفئة ، سيتم تهيئة جذر عقدة الجذر. والثاني هو إضافة عقدة الجذر عند إضافة العنصر الأول. كلاهما يعمل من الناحية النظرية ، ولكن عادةً ما يستخدم نموذج التحميل الكسول الثاني.
عند إضافة عناصر ، هناك العديد من المواقف التي يجب مراعاتها
1. عند الإضافة ، حدد ما إذا كان يتم تهيئة الجذر. إذا لم تتم تهيئتها ، فسيتم تهيئتها. قم بتعيين القيمة إلى عقدة الجذر وأضف حجمًا واحدًا.
2. نظرًا لأن شجرة بحث الأشجار الثنائية تلبي أن قيمة عقدة الجذر أكبر من العقدة اليسرى وأصغر من العقدة اليمنى ، يجب مقارنة القيمة التي تم إدخالها مع عقدة الجذر أولاً. إذا كان كبيرًا ، فابحث في الشجرة الفرعية اليمنى. إذا كانت صغيرة ، فابحث في الشجرة الفرعية اليسرى. حتى عقدة الطفل.
يمكن لتطبيق الإدراج هنا تبني نوعين: واحد ، عودة ، اثنان ، تكرار (أي من خلال وضع الحلقة).
3.1. إدراج النسخة العودية
Boolean Public Add (int val) {if (root == null) {root = new node (val) ؛ حجم ++ ؛ العودة صحيح. } node node = getadapternode (root ، val) ؛ Node NewNode = New Node (Val) ؛ if (node.val> val) {node.leftchild = newNode ؛ newNode.Parent = العقدة ؛ } آخر إذا (node.val <val) {node.rightchild = newNode ؛ newNode.Parent = العقدة ؛ } else {// لا توجد معالجة للوقت} size ++ ؛ 19 return true ؛ } /*** احصل على عقدة الأصل للعقدة المراد إدراجها. ترضي العقدة الأصل إحدى الحالات التالية* 1. العقدة الأصل هي عقدة طفل* 2. قيمة عقدة الإدراج أصغر من العقدة الأصل ، لكن العقدة الأصل لا تحتوي على عقدة طفل يسارية* 3. قيمة عقدة الإدراج أكبر من العقدة الأصل ، لكن العقدة الوالدية لا تحتوي على نود الطفل الأيمن* 4. * 5. العقدة الأصل فارغة* إذا تم استيفاء إحدى الحالات الخمس المذكورة أعلاه ، فستتوقف بشكل متكرر. * param node * param val * @return */ private node getAdapternode (عقدة العقدة ، int val) {if (node == null) {return node ؛ } // insert في الشجرة الفرعية اليسرى ولكن لا يوجد شجرة فرعية اليسار ، if (node.val> val && node.leftchild == null) {return node ؛ } // insert في الشجرة الفرعية اليمنى ولكن لا يوجد شجرة فرعية يمين ، وأعداد أيضًا إذا (node.val <val && node.rightchild == null) {return node ؛ } // insert في الشجرة الفرعية اليمنى ولكن لا يوجد شجرة فرعية يمين ، وأعداد أيضًا إذا (node.val <val && node.rightchild == null) {return node ؛ } // insert في الشجرة الفرعية اليمنى ولكن لا يوجد شجرة فرعية يمين ، وأعداد أيضًا إذا (node.val <val && node.rightchild == null) {return node ؛ } // insert في الشجرة الفرعية اليمنى ولكن لا يوجد شجرة فرعية يمين ، وأعداد أيضًا إذا (node.leftchild == null && node.rightchild == null) {return node ؛ } if (node.val> val && node.leftchild! = null) {return getAdaptarnode (node.leftchild ، val) ؛ } آخر إذا (node.val <val && node.rightchild! = null) {return getAdaptarnode (node.rightchild ، val) ؛ } آخر {return node ؛ }}استخدم العودية ، وابحث أولاً عن نقطة نهاية العودية ، ثم تحويل المشكلة بأكملها إلى مشكلة فرعية. في الكود أعلاه ، يشبه المنطق تقريبًا: أولاً تحديد ما إذا كانت عقدة الجذر تهيئة ، وإذا لم تتم تهيئتها ، فسيتم تهيئتها ، وبعد الانتهاء ، تعود ، ثم استخدم وظيفة للحصول على العقدة المكيفة. ثم أدخل القيمة.
3.2. نسخة تكرارية
Public Boolean Put (int val) {return putval (root ، val) ؛ } Private Boolean putval (عقدة العقدة ، int val) {if (node == null) {// تهيئة عقدة الجذر = node node (val) ؛ الجذر = العقدة ؛ حجم ++ ؛ العودة صحيح. } temp = node ؛ العقدة P ؛ int t ؛ / ** * احصل على أفضل عقدة من خلال DO أثناء التكرار الحلقة ، */ do {p = temp ؛ t = temp.val-val ؛ if (t> 0) {temp = temp.leftchild ؛ } آخر إذا (t <0) {temp = temp.rightchild ؛ } آخر {temp.val = val ؛ العودة كاذبة }} بينما (temp! = null) ؛ Node NewNode = New Node (P ، Val) ؛ if (t> 0) {P.LeftChild = newNode ؛ } آخر إذا (t <0) {p.rightChild = newNode ؛ } size ++ ؛ العودة صحيح. }المبدأ هو في الواقع نفس العودية ، وهو الحصول على أفضل العقدة والعمل على تلك العقدة.
فيما يتعلق بالأداء ، فهو بالتأكيد أفضل إصدار تكراري ، لذلك بشكل عام ، هو الإصدار التكراري للعمل على البيانات.
4. حذف
يمكن القول أنه في تشغيل شجرة البحث الثنائية ، يكون الحذف هو الأكثر تعقيدًا ، وهناك العديد من المواقف التي يجب مراعاتها. بالطريقة التقليدية ، إذا قمت بحذف عقدة في شجرة البحث الثنائية ، فسوف تفكر بالتأكيد في المواقف الأربعة التالية.
1.
2. العقدة المراد حذفها هي فقط العقدة الطفل اليسرى ، مثل العقدة ب
3. العقدة المراد حذفها ليست سوى عقدة الطفل الصحيحة ، مثل العقدة F
4. العقدة المراد حذفها قد تركت العقد الفرعية اليسرى والعقد الطفل اليمنى ، مثل العقد A و C
في المواقف الثلاثة الأولى ، يمكن القول أنها بسيطة نسبيًا ، في حين أن الحالات الرابعة معقدة. دعونا نحلل أول واحد
إذا كانت هذه هي الحالة ، على سبيل المثال ، إذا تم حذف العقدة D ، فيمكن ضبط عقدة الطفل الأيسر للعقدة B على NULL ، وإذا تم حذف العقدة G ، يمكن ضبط عقدة الطفل اليمنى للعقدة F على NULL. أي جانب يجب تعيينه ، ومعرفة أي جانب تقع العقدة المحذوفة.
الطريقة الثانية لحذف العقدة B ، تحتاج فقط إلى تعيين العقدة اليسرى للعقدة A إلى العقدة D والعقدة الأصل للعقدة D إلى A. أي الجانب الذي يتم تعيينه يعتمد على أي جانب من العقدة المحذوفة على العقدة الأصل.
النوع الثالث هو نفس النوع الثاني.
النوع الرابع ، الذي هو معقد بعض الشيء كما ذكر من قبل ، هو حذف العقدة C ، تعيين العقدة الأصل للعقدة f على العقدة A ، اضبط العقدة اليسرى للعقدة f على العقدة e ، تعيين العقدة اليمنى من A إلى العقدة f ، اضبط العقدة الوالدية لـ e على node f (وهذا هو f n node c node) ، وهناك نوع آخر ، مباشرة. إذن أي واحد يجب استخدامه؟ إذا كانت عقدة الحذف هي عقدة الجذر ، فكيف يمكنني حذفها؟
بالنسبة للحالة الرابعة ، يمكنك التفكير في الأمر على هذا النحو: العثور على عقدة الخلف من C أو عقدة ، وحذف عقدة الخلف ، وتعيين قيمة العقدة الخلف على قيمة C أو العقدة. دعنا نلحق أولاً مفهوم العقد الخلف.
يجب أن تكون عقدة الخلف للعقدة في الشجرة بأكملها راضية. العقدة مع أصغر قيمة في مجموعة العقد تستحق العقدة هي العقدة الخلف. بالطبع ، قد لا يكون هناك عقد خلف.
ومع ذلك ، بالنسبة للحالة الرابعة ، يجب أن تكون العقدة الخفية موجودة ويجب أن تكون في الشجاعة الفرعية اليمنى ، كما أنها تلبي إحدى الحالات التي لا توجد فيها عقدة طفل أو عقدة طفل واحدة فقط. يمكن التفكير في هذا السبب المحدد ، لأن عقدة الخلف أكبر من العقدة C ، ولأن الأقسام الفرعية اليسرى واليسرى للعقدة C يجب أن توجد ، يجب أن تكون موجودة في القسم الفرعي الأيسر في الشجرة الفرعية اليمنى. على سبيل المثال ، عقدة خليفة C هي F ، وعقدة الخلف A IS E.
مع التحليل أعلاه ، يكون التنفيذ بسيطًا نسبيًا ، والرمز كما يلي
الحذف المنطقي العام (int val) {node node = getNode (val) ؛ if (node == null) {return false ؛ } node parent = node.parent ؛ Node LeftChild = node.leftchild ؛ عقدة rightchild = node.rightchild ؛ // جميع العقد الأصل التالية فارغة ، فهذا يعني أن العقدة المحذوفة هي عقدة الجذر إذا (LeftChild == null && rightchild == null) {// لا توجد عقد طفل إذا (الأصل! = null) {if (parent.leftchild == node) {parent.leftchild = null ؛ } آخر إذا (parent.rightChild == Node) {parent.RightChild = null ؛ }} آخر {// العقدة الأصل غير موجودة ، مما يعني أن العقدة المحذوفة هي جذر العقدة الجذر = null ؛ } العقدة = null ؛ العودة صحيح. } آخر إذا (LeftChild == null && rightchild! = null) {// فقط العقدة اليمنى if (parent! = null && parent.val> val) {// هناك عقدة الأصل ، وموضع العقدة هو الجانب الأيسر للعقدة الأصل. } آخر إذا (parent! = null && parent.val <val) {// هناك عقدة الأصل ، وموضع العقدة هو الجانب الأيمن من العقدة الأصل. rightchild = rightchild ؛ } آخر {root = rightchild ؛ } العقدة = null ؛ العودة صحيح. } آخر إذا (LeftChild! = null && rightchild == null) {// فقط العقدة اليسرى if (parent! = null && parent.val> val) {// هناك عقدة الأصل ، وموضع العقدة هو الجانب الأيسر من العقدة الوالدة. } آخر إذا (parent! = null && parent.val <val) {// هناك عقدة الأصل ، وموضع العقدة هو الجانب الأيمن من العقدة الأصل parent.rightchild = LeftChild ؛ } آخر {root = LeftChild ؛ } إعادة صواب ؛ } آخر إذا (LeftChild! = null && rightchild! = null) {// كلا العقدتين الطفل لهما خلف العقدة = getSuccessor (العقدة) ؛ // في هذه الحالة ، يجب أن يكون هناك عقدة خلف int temp = suckor.val ؛ Boolean Delete = Delete (temp) ؛ if (delete) {node.val = temp ؛ } خليفة = فارغ ؛ العودة صحيح. } إرجاع خطأ ؛ } /*** ابحث عن عقدة الخلف لعقدة العقدة* 1. أولاً حدد ما إذا كانت العقدة لديها شجرة فرعية يمين. إذا كان الأمر كذلك ، ابحث عن العقدة الخلف من الشجرة الفرعية اليسرى من العقدة اليمنى. إذا لم يكن كذلك ، انتقل إلى الخطوة التالية* 2. ابحث عن العقدة الأصل للعقدة. إذا كانت العقدة اليمنى للعقدة الأصل مساوية للعقدة ، فاستمر في البحث عن العقدة الأصل * حتى تصبح العقدة الأصل فارغة أو ابحث عن العقدة اليمنى التي لا تساوي العقدة. * العقل ، يجب أن تكون عقدة الخلف أكبر من العقدة. إذا كان هناك شجرة فرعية صحيحة ، فيجب أن توجد عقدة الخلف في الشجرة الفرعية الصحيحة. هذا هو السبب في الخطوة الأولى* إذا لم يكن هناك شجرة فرعية صحيحة ، فقد يكون هناك أيضًا عقدة جد للعقدة (أي العقدة الأصل للعقدة ، أو العقدة الأصل فوق العقدة الأصل). * البحث بشكل تكراري ، إذا كان هناك ، فإنه يعيد العقدة ، وإذا كان هناك ، فإنه يعيد null * param node * regurn */ private node getSuccessor (node node) {if (node.rightchild! = null) {node rightchild = node.rightchild ؛ بينما (rightchild.leftchild! = null) {rightchild = rightchild.leftchild ؛ } إرجاع Rightchild ؛ } node parent = node.parent ؛ بينما (الأصل! = null && (node == parent.rightchild)) {node = parent ؛ الوالدين = parent.parent ؛ } إرجاع الوالدين ؛ }للحصول على منطق محدد ، يرجى الرجوع إلى التحليل أعلاه. لن أصف النص هنا.
بالإضافة إلى هذا التنفيذ ، يتم توفير تطبيق آخر في مقدمة الخوارزمية.
إزالة منطقية عامة (int val) {node node = getNode (val) ؛ if (node == null) {return false ؛ } if (node.leftchild == null) {// 1. العقدة اليسرى غير موجودة ، قد توجد العقدة اليمنى ، بما في ذلك حالتين. كلا العقدتين غير موجودة ولا يوجد سوى العقدة اليمنى زرع (العقدة ، node.rightchild) ؛ } آخر إذا (node.rightchild == null) {// 2. يوجد الطفل الأيسر ، والعقدة اليمنى غير موجودة زرع (العقدة ، node.leftchild) ؛ } else {// 3. كلا العقدتين لهما Node Succistor = getSuccessor (Node) ؛ // الحصول على عقدة Node Succistor if (suckor.parent! = node) {// توجد عقدة الخلف في الشجرة الفرعية اليمنى للعقدة. زرع (خليفة ، خليفة. rightchild) ؛ // استبدل الخلف بالعقدة الطفل الصحيحة من الخلف الخطوة السابقة} زرع (العقدة ، الخلف) ؛ Suckor.LeftChild = node.leftchild ؛ levtor.leftchild.parent = خليفة ؛ } إعادة صواب ؛ } /*** استبدل Node Node بعقدة node* param node root root* param node node لحذف* param child node node node node node node node child node node child child transplant (node node ، atte ant the root the ant the ant the root te الخطوة* 2. حدد أن عقدة العقدة هي طفل العقدة الأصل (أي ، حدد ما إذا كانت العقدة هي العقدة اليمنى أو العقدة اليسرى) ،* بعد الحصول على النتيجة ، استبدل عقدة الطفل بعقدة عقدة ، أي ، إذا كانت العقدة المأمة هي العلامة العليا للطفل ، فستكون الطفل هي العقدة اليسرى بعد استبدالها ، وإلا العقدة*/ if (node.parent == null) {this.root = child ؛ } آخر if (node.parent.leftchild == node) {node.parent.leftchild = child ؛ } آخر if (node.parent.rightchild == node) {node.parent.rightchild = child ؛ } if (child! = null) {child.parent = node.parent ؛ }}5. البحث
البحث بسيط نسبيًا أيضًا ، ولكن في الواقع ، تم تنفيذه عند إضافته. في المواقف الفعلية ، يمكن استخراج هذا الجزء من طريقة منفصلة. الرمز كما يلي
العقدة العامة getNode (int val) {node temp = root ؛ int t ؛ do {t = temp.val-val ؛ if (t> 0) {temp = temp.leftchild ؛ } آخر إذا (t <0) {temp = temp.rightchild ؛ } آخر {return temp ؛ }} بينما (temp! = null) ؛ العودة لاغية. }6. اجتياز شجرة البحث الثنائي
بعد فهم خصائص شجرة البحث الثنائية ، من الواضح أن اجتياز الترتيب الوسيط يتم ترتيبه بالتسلسل من صغير إلى كبير. فيما يلي رمز اجتياز الطلب المتوسط المقدم هنا
public void print () {print (root) ؛ } private void print (node root) {if (root! = null) {print (root.leftchild) ؛ system.out.println (root.val) ؛ // إذا كان الموضع في الوسط ، فسيكون الترتيب في الوسط. إذا كان في المقدمة ، فهو في سابقة ، وإلا فهي طباعة لاحقة (root.rightchild) ؛ }} لخص
ما سبق هو تنفيذ Java لوظيفة شجرة البحث الثنائية التي أدخلها المحرر. آمل أن يكون ذلك مفيدًا للجميع. إذا كان لديك أي أسئلة ، يرجى ترك رسالة لي. سوف يرد المحرر على الجميع في الوقت المناسب!