التنفيذ والعمليات الأساسية لشجرة الفرز الثنائية

تسمى شجرة الفرز الثنائية أيضًا شجرة البحث الثنائية. إنها إما شجرة فارغة أو شجرة ثنائية مع الخصائص التالية:

① إذا لم تكن الشجرة الفرعية اليسرى فارغة ، فإن قيم جميع العقد على الشجرة الفرعية اليسرى أصغر من قيم عقدة الجذر الخاصة بها ؛

② إذا كانت الشجرة الفرعية اليمنى ليست فارغة ، فإن قيم جميع العقد على الشجرة الفرعية اليمنى أكبر من قيم عقدة الجذر الخاصة بها ؛

tructes الفرعية اليسرى واليمين هي أيضا أشجار الفرز الثنائية على التوالي.

رمز التالي ينفذ:

• بناء الأشجار الثنائية
• الوسط ، الأمامي ، الخلفي والتسلسل الهرمي للشجرة الثنائية
• أقصى مسافة من العقد في شجرة ثنائية

 استيراد java.util.linkedList ؛ استيراد java.util.queue ؛ عقدة الفئة {public int data ؛ اليسار العقدة العامة ؛ العقدة العامة الحق ؛ العام int leftMaxDistance ؛ العام int rightMaxDistance ؛ العقدة العامة (int data) {this.data = data ؛ this.left = null ؛ this.right = null ؛ }}/*** Author ty* تنفيذ شجرة فرز ثنائية ، بما في ذلك الإدراج ، والتجارة في الطلب ، والتجارة المسبقة ، والتمرير بعد الترتيب ، وحساب أقصى مسافة لجميع العقد*/الطبقة العامة binarytree {private node root ؛ Public BinaryTree () {root = null ؛ } public void insert (int data) {node newNode = new node (data) ؛ if (root == null) root = newNode ؛ else {node current = root ؛ الوالد العقدة ؛ بينما (صواب) {// البحث عن موقع إدراج parent = current ؛ if (data <current.data) {current = current.left ؛ if (current == null) {parent.left = newNode ؛ يعود؛ }} آخر {current = current.right ؛ if (current == null) {parent.right = newNode ؛ يعود؛ }}}}}}} // إدخال القيم العددية لإنشاء شجرة buildtree buildtree (int [] int []) }}} // طريقة اجتياز الترتيب تنفذ بشكل متكرر void public inorder (node ​​localroot) {if (localroot! = null) {inorder (localroot.left) ؛ System.out.print (localroot.data+"") ؛ inorder (localroot.right) ؛ }} public void inorder () {this.inorder (this.root) ؛ } // طريقة اجتياز preorder تنفذ بشكل متكرر preorder predorder (node ​​localroot) {if (localroot! = null) {system.out.print (localroot.data+"") ؛ preorder (localroot.left) ؛ preorder (localroot.right) ؛ }} preor preorder () {this.preorder (this.root) ؛ } // طريقة اجتياز postorder تنفذ بشكل متكرر postorder postorder (Node localroot) {if (localroot! = null) {postorder (localroot.left) ؛ postorder (localroot.right) ؛ System.out.print (localroot.data+"") ؛ }} public void postorder () {this.postorder (this.root) ؛ } /*** شجرة ثنائية لطبقة الطبقة: ضع الآن عقدة الجذر في قائمة الانتظار ، ثم خذ عقدة من قائمة الانتظار في كل مرة لطباعة قيمة العقدة. * إذا كانت هذه العقدة تحتوي على عقدة طفل ، فضع عقدة طفلها في ذيل قائمة الانتظار حتى تصبح قائمة الانتظار فارغة*/ public void layertranverse () {if (this.root == null) ؛ قائمة الانتظار <Node> q = new LinkedList <Node> () ؛ Q.Add (this.root) ؛ بينما (! q.isempty ()) {node n = q.poll () ؛ System.out.print (N.Data+"") ؛ if (n.ft! = null) q.add (n.left) ؛ if (n.right! = null) Q.Add (n.right) ؛ }} private int maxlen = 0 ؛ private int max (int a ، int b) {return a> b؟ a: b ؛ } public void findMaxDistance (node ​​root) {if (root == null) return ؛ if (root.left == null) root.leftmaxDistance = 0 ؛ if (root.right == null) root.rightMaxDistance = 0 ؛ if (root.left! = null) findMaxDistance (root.left) ؛ if (root.right! = null) findMaxDistance (root.right) ؛ // احسب المسافة القصوى من عقدة الجذر في شجرة الكلمة اليسرى إذا (root.left! = null) root.leftmaxDistance = max (root.left.leftmaxdistance ، root.left.rightmaxdistance) +1 ؛ // احسب المسافة القصوى من عقدة الجذر في شجرة الكلمة اليمنى إذا (root.right! = null) root.rightMaxDistance = max (root.right.leftmaxdistance ، root.right.rightMaxDistance) +1 ؛ // احصل على أقصى مسافة لجميع العقد من الشجرة الثنائية إذا (root.leftmaxDistance+root.rightMaxDistance> maxlen) {maxlen = root.leftmaxdistance+root.rightMaxDistance ؛ }} public static void main (string [] args) {binarytree bitree = new BinaryTree () ؛ int [] data = {2،8،7،4،9،3،1،6،7،5} ؛ bitree.buildtree (البيانات) ؛ system.out.print ("in orderdal arversal of binary tree:") ؛ bitree.inorder () ؛ System.out.println () ؛ system.out.print ("اجتياز المسبق للشجرة الثنائية:") ؛ bitree.preorder () ؛ System.out.println () ؛ System.out.println () ؛ System.out.println () ؛ System.out.print ("اجتياز ما بعد الترتيب للشجرة الثنائية:") ؛ bitree.postorder () ؛ System.out.println () ؛ System.out.print ("ترتيب الطبقة من الشجرة الثنائية:") ؛ bitree.layertranverse () ؛ System.out.println () ؛ bitree.findMaxDistance (bitree.root) ؛ System.out.println ("أقصى مسافة من العقد في الشجرة الثنائية:"+bitree.maxlen) ؛ }}

ما سبق هو كل محتوى هذه المقالة. آمل أن يكون محتوى هذه المقالة من بعض المساعدة في دراسة أو عمل الجميع. آمل أيضًا دعم wulin.com أكثر!