تقوم Java بتنفيذ شجرة البحث الثنائية وتنفذ البحث وإدراج وحذف العمليات على الشجرة (دمج وحذف ونسخ وحذف)
بادئ ذي بدء ، نحن بحاجة إلى فكرة ترميز ، على النحو التالي:
1. البحث: وفقًا لخصائص بيانات شجرة البحث الثنائية ، يمكننا تحقيق البحث بناءً على مقارنة القيمة للعقد. عندما تكون قيمة البحث أكبر من العقدة الحالية ، انتقل إلى اليمين ، والعكس صحيح!
2. أدخل: يجب أن نعلم أن جميع العقد المدرجة هي العقد ، لذلك نحتاج إلى العثور على موقع عقدة الورقة المراد إدراجها ، وفكرة الإدراج تتفق مع فكرة البحث.
3. حذف:
1) دمج وحذف: بشكل عام ، سيتم مواجهة المواقف التالية. تحتوي العقدة المحذوفة على شجرة فرعية يسارية ولكن لا يوجد شجرة فرعية يمين. في هذا الوقت ، يجب أن تشير العقدة الأم للعقدة الحالية إلى الشجرة الفرعية اليسرى للعقدة الحالية ؛ عندما يكون للعقدة المحذوفة شجرة فرعية اليمنى ولكن لا توجد شجرة فرعية يسارية ، يجب أن تشير العقدة الأصل للعقدة الحالية إلى الشجرة الفرعية اليمنى ؛ عندما تحتوي العقدة المحذوفة على شجرة فرعية يسارية وشجرة فرعية يمين ، يمكننا أن نجد العقدة الأقصى اليمنى من الشجرة الفرعية اليسرى للعقدة المحذوفة ، ثم اترك "المؤشر" الأيمن أو الأيسر من هذه العقدة إلى الشجرة الفرعية اليمنى للعقدة المحذوفة
2) النسخ والحذف: نسخ وحذف عمليات حذف بسيطة نسبيًا ، كما أنها عمليات الحذف الأكثر استخدامًا. هناك ما يقرب من ثلاث حالات: عندما لا تحتوي العقدة الحالية على شجرة فرعية اليسار ولديها شجرة فرعية يمين ، دع عقدة الجذر من الشجرة الفرعية اليمنى الحالية تستبدل العقدة المحذوفة ؛ عندما لا تحتوي العقدة الحالية على شجرة فرعية يمين ولديها شجرة فرعية يسارية ، دع عقدة الجذر من الشجرة الفرعية اليسرى الحالية واستبدل العقدة المحذوفة ؛ عندما يكون للعقدة المحذوفة حاليًا شجرة فرعية يسارية وشجرة فرعية يمين ، نحتاج إلى العثور على الشجرة الفرعية للعقدة المحذوفة ، وإيجاد العقدة في أقصى اليمين في الفرعية اليسرى وتعيين قيمة هذه العقدة إلى العقدة المحذوفة ، ومن ثم لا تنسى أن تسمح "المؤشر" بالمؤشر للوالد إلى مرونة المسمار في الواقع ، فهي في الحقيقة في الواقع ، معالجته). يمكنك أيضًا تنفيذ هذه العملية كعقدة قائمة بذاتها على عقدة أقصى اليسار من الشجرة الفرعية اليمنى للعقدة المحذوفة حاليًا.
بعد ذلك ، دعنا نضيف الرمز.
بادئ ذي بدء ، ## فئة عقدة شجرة البحث الثنائية ##
Package SearchBinaryTree ؛ SearchBinaryTreeNode من الفئة العامة <T> {T Data ؛ SearchBinaryTreeNode <T> LeftChild ؛ SearchBinaryTreeNode <T> RightChild ؛ public searchBinaryTreeNode () {this.data = null ؛ this.leftchild = this.rightchild = null ؛ } searchBinaryTreeNode (t da) {this.data = da ؛ this.leftchild = this.rightchild = null ؛ } searchBinaryTreeNode (t da) {this.data = da ؛ this.leftchild = this.rightchild = null ؛ } SearchBinaryTreeNode (t da ، searchBinaryTreeNode <T> يسار ، SearchBinaryTreeNode <T> يمين) {this.data = da ؛ this.leftchild = اليسار ؛ this.rightchild = الحق ؛ } public t getData () {return data ؛ } public void setData (t data) {this.data = data ؛ } public searchBinaryTreeNode <T> getleftchild () {return LeftChild ؛ } public void setleftchild (searchBinaryTreeNode <T> leftchild) {this.leftchild = leftchild ؛ } public searchBinaryTreeNode <T> getRightChild () {return rightchild ؛ } public void setRightChild (SearchBinaryTreeNode <T> rightchild) {this.rightChild = rightChild ؛ } public boolean isLeaf () {if (this.leftchild == null && this.rightchild == null) {return true ؛ } إرجاع خطأ ؛ }}تنفيذ شجرة بحث ثنائية
Package SearchBinaryTree ؛ SearchBinarytree الفئة العامة <T> {searchBinaryTreeNode <T> Root ؛ منطقية عامة isempty () {if (root == null) {return true ؛ } إرجاع خطأ ؛ } زيارة باطلة عامة (SearchBinaryTreeNode <T> root) {if (root == null) {system.out.println ("هذه الشجرة فارغة!") ؛ } system.out.println (root.getData ()) ؛ } public searchBinaryTreeNode <T> getRoot () {if (root == null) {root = new SearchBinaryTreeNode <T> () ؛ } جذر الإرجاع ؛ } public SearchBinaryTree () {this.root = null ؛ } /** إنشاء شجرة ثنائية* / public void createTree (SearchBinaryTreeNode <T> node ، t data) {if (root == null) {root = new SearchBinaryTreeNode <T> () ؛ } آخر {if (math.random ()> 0.5) {// إنشاء شجرة ثنائية بطريقة عشوائية if (node.leftchild == null) {node.leftchild = new searchBinaryTreeNode <T> (data) ؛ } آخر {createTree (node.leftchild ، data) ؛ }} آخر {if (node.rightchild == null) {node.rightChild = new SearchBinaryTreeNode <T> (data) ؛ } آخر {createTree (node.rightchild ، data) ؛ }}}}} /** ابحث في شجرة البحث الثانية* / public SearchBinaryTreeNode <T> Search (SearchBinaryTreeNode <T> root ، t value) {searchBinaryTreeNode <T> current = root ؛ بينما ((الجذر! = null) && (current.getData ()! = value)) {// تجدر الإشارة إلى أن الأدوية العامة في Java لا يمكنها مقارنة الأحجام. في الاستخدام الفعلي ، يمكننا استخدام أنواع البيانات الشائعة لاستبدال هذا العام ، لذلك لن تكون هناك أخطاء. Current = (value <current.getData ()؟ Search (current.leftchild ، value): search (current.rightchild ، value)) ؛ } إرجاع التيار ؛ } SearchBinaryTreeNode <T> insertNode (t value) {searchBinaryTreeNode <T> p = root ، pre = null ؛ بينما (p! = null) {pre = p ؛ // تجدر الإشارة إلى أن الأدوية الجينية في جافا لا يمكنها مقارنة الأحجام. في الاستخدام الفعلي ، يمكننا استخدام أنواع البيانات الشائعة لاستبدال هذا العام ، بحيث لن يكون هناك أي أخطاء إذا (p.getData () <value) {p = p.rightchild ؛ } آخر {p = p.leftchild ؛ }} if (root == null) {root = new SearchBinaryTreeNode <T> (value) ؛ } آخر إذا (pre.getData () <value) {pre.rightChild = new SearchBinaryTreeNode <T> (value) ؛ } آخر {pre.leftchild = new SearchBinaryTreeNode <T> (value) ؛ }} /** دمج وحذف* / public void deleteberging (searchBinaryTreeNode <T> node) {searchBinaryTreeNode <T> temp = node ؛ if (node! = null) {// إذا كانت العقدة المحذوفة لا تحتوي على شجرة فرعية يمين ، فاستخدم عقدة الجذر الخاصة بها في الشجرة الفرعية اليسرى لاستبدال العقدة المحذوفة إذا (node.rightchild! = null) {node = node.leftchild ؛ } آخر إذا (node.leftchild == null) {// إذا لم يكن للعقدة المحذوفة شجرة فرعية يسارية ، فاستخدم العقدة اليسرى مع عدد الكلمات بدلاً من العقدة المحذوفة = node.rightchild ؛ } آخر {// إذا كانت المسطحين الأيسر واليمين للعقد المحذوفة لها درجة حرارة = node.leftchild ؛ بينما (temp.rightchild! = null) {temp = temp.rightchild ؛ . درجة الحرارة = العقدة ؛ العقدة = node.leftchild ؛ } temp = null ؛ }} / * * copy and delete * / public void deletebycoping (searchBinaryTreeNode <T> node) {searchBinaryTreeNode <T> pre = null ؛ SearchBinaryTreeNode <T> temp = node ؛ // إذا لم يكن للعقدة المحذوفة شجرة فرعية يمين ، فاستخدم عقدة الجذر في الشجرة الفرعية اليسرى لاستبدال العقدة المحذوفة إذا (node.rightchild == null) {node = node.leftchild ؛ } آخر إذا (node.leftchild == null) {node = node.rightchild ؛ } آخر {// إذا كانت المسطحين الأيسر واليمين للعقد المحذوفة لها درجة حرارة = node.leftchild ؛ قبل = العقدة ؛ بينما (temp.rightchild! = null) {pre = temp ؛ temp = temp.rightchild ؛ // السفر للعثور على أقصى اليمين من الشجرة الفرعية اليسرى} node.data = temp.data ؛ // تنفيذ عملية المهمة if (pre == node) {pre.leftchild = node.leftchild ؛ } آخر {pre.rightchild = node.rightchild ؛ }} temp = null ؛ }}فئة الاختبار
Package SearchBinaryTree ؛ public class searchBinaryTreetest {public static void main (string [] args) {searchBinaryTree <integer> tree = new SearchBinaryTree <integer> () ؛ لـ (int i = 1 ؛ i <10 ؛ i ++) {tree.createTree (searchBinaryTreeNode <integer> () ، i) ؛ } // search tree.search (tree.root ، 7) ؛ // دمج وحذف tree.deleteBymerging (SearchBinaryTreeNode <integer> (8)) ؛ // copy and delete tree.deleteByCoping (New SearchBinaryTreeNode <integer> (6)) ؛ }}حسنًا ، هذا كل شيء!
المقالة أعلاه Java تنشئ شجرة بحث ثنائية وتنفيذ أمثلة عملية البحث والإدراج والحذف هي كل المحتوى الذي أشاركه معك. آمل أن تتمكن من إعطائك مرجعًا وآمل أن تتمكن من دعم wulin.com أكثر.