تصنيف الأشجار الثنائية (عن طريق هيكل التخزين)
تصنيف الأشجار (عن طريق هيكل التخزين)
التخزين المتسلسل (ممثلها المصفوفات (شجرة ثنائية ثابتة))
تخزين السلسلة
بعض الجذور الثنائية الخاصة:
شجرة ثنائية كاملة ، شجرة ثنائية متوازنة (AVL) ، شجرة ثنائية ، Tri-Fork (مؤشر مع الأب)
شجرة البحث الثنائية أو شجرة البحث الثنائية (BST)
يظهر الشجرة الثنائية المستخدمة في الشكل التالي:
تنفيذ Java للشجرة الثنائية (بنية تخزين السلسلة)
class treenode {private int key = 0 ؛ بيانات السلسلة الخاصة = فارغة ؛ المنطقية الخاصة istvisted = false ؛ TreeNode private Leftchild = null ؛ TreeNode private rightchild = null ؛ Public TreeNode () {} public treenode (int key ، string data) {this.key = key ؛ this.data = البيانات ؛ this.leftchild = null ؛ this.rightchild = null ؛ } public int getKey () {return Key ؛ } public void setKey (int key) {this.key = key ؛ } السلسلة العامة getData () {return data ؛ } public void setData (string data) {this.data = data ؛ } public treenode getleftchild () {return leftchild ؛ } public void setleftchild (treeNode LeftChild) {this.leftchild = LeftChild ؛ } public treenode getRightChild () {return rightchild ؛ } public void setRightChild (treenode rightchild) {this.rightchild = rightchild ؛ } boolean public iSvisted () {return Isvisted ؛ } public void setVisted (boolean isvisted) {this.isvisted = isVisted ؛ }} الفئة العامة BinaryTree {private treenode root = null ؛ Public BinaryTree () {root = new treenode (1 ، "rootnode (a)") ؛ } public void createBinTree (treenode root) {// creation اليدوي (يظهر الهيكل في الشكل) treenode newNodeB = new treenode (2 ، "b") ؛ treenode newnodec = new treenode (3 ، "c") ؛ treenode newNoded = new treenode (4 ، "d") ؛ treenode newnodee = new treenode (5 ، "e") ؛ treenode newNodef = new treenode (6 ، "f") ؛ root.setleftchild (newNodeB) ؛ root.setRightChild (NewNodec) ؛ root.getleftchild (). setleftchild (newNoded) ؛ root.getleftchild (). setrightchild (newNodee) ؛ root.getRightChild (). setrightchild (newNodef) ؛ } boolean public isempty () {// حدد ما إذا كانت الشجرة الثنائية فارغة أو لا ترجع جذر == null ؛ } ارتفاع الباحث العام () {// أوجد ارتفاع عودة ارتفاع الشجرة (الجذر) ؛ } ارتفاع int العام (TreeNode sub treate) {if (sub -tree == null) return 0 ؛ // الطرف المتكرر: ارتفاع الشجرة الفارغة هو 0 آخر {int i = height (sub tree.getleftchild ()) ؛ int j = الارتفاع (tratree.getRightChild ()) ؛ العودة (أنا <ي)؟ J + 1: i + 1 ؛ }} size int public () {// ابحث عن عدد حجم العقد (الجذر) ؛ } حجم int العام (treenode sub treate) {if (sub -tree == null) return 0 ؛ else {return 1 + size (sub tree.getleftchild ()) + size (subtree.getRightChild ()) ؛ }} Public TreeNode Parent (عنصر treenode) {// إرجاع العقدة الأصل (root == null || root == element)؟ NULL: الوالد (الجذر ، العنصر) ؛ } Public TreeNode Parent (Treenode Subtree ، TreeNode element) {if (sub -tree == null) return null ؛ if (sub -tree.getleftchild () == element || sub -tree.getRightChild () == element) // inition ، return the addr addrate return sub trupe ؛ Treenode P ؛ // انظر أولاً في الشجرة الفرعية اليسرى. إذا لم يتم العثور عليها في الشجرة الفرعية اليسرى ، فانتقل إلى الشجرة الفرعية اليمنى للعثور على IF ((P = PARTER (PARTERE.GETLEFTCHILD () ، element))! = null) // البحث بشكل متكرر عن الإرجاع P ؛ else // البحث بشكل متكرر عن Parent Parent (truptree.getRightChild () ، element) ؛ } TreeNode Leftchild (عنصر treeNode) {// إرجاع الإرجاع الفرعي الأيسر (العنصر! = null)؟ element.getleftchild (): null ؛ } treenode public truperchild (عنصر treeNode) {// إرجاع الإرجاع الفرعي الأيمن (العنصر! = null)؟ element.getRightChild (): null ؛ } public treenode getRoot () {// الحصول على جذر Root Node Retrore ؛ } تدمير الفراغ العام (TreeNode sub -treet) {// الوظيفة الخاصة: حذف الشجرة الفرعية مع الشجرة الفرعية الجذر if (sub treat! = null) {destroy (sub -tree.getleftchild ()) ؛ // حذف تدمير الشجرة الفرعية اليسرى (truptree.getRightChild ()) ؛ // حذف الشجرة الفرعية اليمنى // حذف الشجرة الفرعية ؛ // حذف الشجرة الفرعية للعقدة الجذر = فارغة ؛ }} public void traverse (treenode sub-tree) {system.out.println ("key:" + subtree.getKey () + "-name:" + subtree.getData ()) ؛ Traverse (trantree.getleftchild ()) ؛ Traverse (trantree.getRightChild ()) ؛ } predorder preorder public (treenode sub -tree) {// root first (trupree! = null) {visted (trantree) ؛ preorder (subtree.getleftchild ()) ؛ preorder (subtree.getRightChild ()) ؛ }} public void inorder (treeNode sub tretree) {// medium root if (sub treat! = null) {inorder (subtree.getleftchild ()) ؛ تفجير (شجرة فرعية) ؛ inorder (sub -tree.getRightChild ()) ؛ }} public void postorder (treenode sub -tree) {// post root if (sub -tree! = null) {postorder (sub -tree.getleftchild ()) ؛ postorder (subtree.getRightChild ()) ؛ تفجير (شجرة فرعية) ؛ }} public void LevelOrder (TreeNode sub treate) {// piriphery} insert boolean public (عنصر treenode) {// إدراج return true ؛ } find Boolean Public (عنصر treenode) {// Find Return True ؛ } شهدت الفراغ العام (treenode sub treate) {sub -tree.setVisted (true) ؛ System.out.println ("KEY:" + sub-tree.getKey () + "-name:" + subtree.getData ()) ؛ } public static void main (string [] args) {binartree bt = new BinaryTree () ؛ Bt.Createbintree (bt.root) ؛ System.out.println ("حجم الشجرة هو" + bt.size ()) ؛ system.out.println ("ارتفاع الشجرة هو" + bt.height ()) ؛ System.out.println ("********* preorder (preorder) [Abdecf] Transfer **************") ؛ bt.preorder (bt.root) ؛ system.out.println ("********* recide الجذر (الترتيب الداخلي) [dbeacf] نقل ****************") ؛ bt.inorder (bt.root) ؛ System.out.println ("********* آخر جذر (أمر آخر) [debfca] نقل ****************") ؛ bt.postorder (bt.root) ؛ }} نتائج الإخراج:
حجم الشجرة 6
ارتفاع الشجرة 3
******* الجذر الأول (preorder) [Abdecf] traversal ****************
المفتاح: 1-name: rootnode (أ)
المفتاح: 2-name: ب
المفتاح: 4-اسم: د
المفتاح: 5-name: e
المفتاح: 3-اسم: ج
المفتاح: 6-name: f
******* الجذر المتوسط (الترتيب الأوسط) [DBEACF] اجتياز ********************
المفتاح: 4-اسم: د
المفتاح: 2-name: ب
المفتاح: 5-name: e
المفتاح: 1-name: rootnode (أ)
المفتاح: 3-اسم: ج
المفتاح: 6-name: f
******* الجذر الأخير (أمر ما بعد) [debfca] traversal ******************
المفتاح: 4-اسم: د
المفتاح: 5-name: e
المفتاح: 2-name: ب
المفتاح: 6-name: f
المفتاح: 3-اسم: ج
المفتاح: 1-name: rootnode (أ)
آمل أن يكون هذا المقال مفيدًا للطلاب الذين يدرسون برمجة Java.