ما هي شجرة ثنائية؟ لن أقدمها هنا. يمكنك استخدام Baidu: شجرة ثنائية. هنا ، استخدم Java لتنفيذ "شجرة التعبير الثنائية".
تعريف الشجرة الثنائية التعبير
الخطوة الأولى هي فهم ماهية الشجرة الثنائية التعبير؟ على سبيل المثال ، التعبير: (A+B × (CD))-E/F. وضع الأرقام في عقدة الورقة والمشغل في عقدة الفرع يشكل شجرة ثنائية. لأنه يخزن تعبيرًا ، يطلق عليه "الشجرة الثنائية التعبير".
قد تكون أحذية الأطفال فضولية حول كيفية بناء ذلك؟ خذ 45+23*56/2-5 كمثال. أولاً ، أخرج الرقم الأول 45 ووضعه في عقدة الورقة. بعد مواجهة "+" ، ضعها على عقدة الفرع.
ثم ضع "23" ، "*" ، "56" ، "/" ، و "2" في التسلسل.
وضعت أخيرًا "-" و "5" ،
هذا تقريبا. (رسمت هذه الصور بنفسي ، إنها قبيحة ، فقط ألق نظرة عليها (⊙⊙))
خطوات لبناء شجرة ثنائية التعبير
1. إنشاء كائن عقدة ؛
2. تمييز المشغلين والبيانات وتخزينها في القائمة المقابلة (قائمة الانتظار) ؛
3. أخرج الرقمين الأولين ومشغل لتشكيل عقدة رقم جديدة ؛
4. كرر الخطوة 3 حتى ينتهي المشغل ؛
5. دع عقدة الجذر تساوي العقدة الأخيرة.
تنفيذ الشجرة الثنائية التعبير
أولاً ، قم بإنشاء فئة كائن العقدة ، بما في ذلك البيانات ، والشجرة الفرعية اليسرى ، والشجرة الفرعية اليمنى والعديد من المجموعات والحصول على الأساليب.
حزمة tets0714 ؛/** * فئة كائن العقدة * Author yuxiu * */عقدة الفئة العامة {// Data Private String Data ؛ // اليسار في الشجرة الفرعية العقدة الخاصة lchild ؛ // Right Subtree Private Node rchild ؛ node () {} node (سلسلة بيانات) {this.data = data ؛ } node (بيانات السلسلة ، العقدة lchild ، العقدة rchild) {super () ؛ this.data = البيانات ؛ this.lchild = lchild ؛ this.rchild = rchild ؛ } السلسلة العامة getData () {return data ؛ } العقدة العامة getLchild () {return lchild ؛ } العقدة العامة getRchild () {return rchild ؛ }}ثم بناء الشجرة الثنائية التعبير.
حزمة tets0714 ؛ استيراد java.util.arraylist ؛/** * التعبير فئة شجرة ثنائية * Author yuxiu * */public class formaluetree {private string s = "" ؛ جذر العقدة الخاص // ROOT NODE/*** إنشاء تعبير ثنائي شجرة* param str التعبير*/public void creattree (string str) {// إعلان قائمة صفيف ، مشغلات المتجر ، إضافة ، طرح ، مضاعفة وقسم ، ArrayList <String> cownerlist = new ArrayList <string> () ؛ // إعلان قائمة صفيف ، تخزين بيانات العقدة ، ArrayList <Node> numList = جديد ArrayList <Node> () ؛ // أولاً ، قم بتمييز المشغل والبيانات وتخزينه في القائمة المقابلة لـ (int i = 0 ؛ i <str.length () ؛ i ++) {char ch = str.charat (i) ؛ // جلب أحرف السلسلة if (ch> = '0' && ch <= '9') {s+= ch ؛ } آخر {numList.add (عقدة جديدة (s)) ؛ s = "" ؛ OperatorList.add (CH+"") ؛ }} // إضافة الرقم الأخير إلى Node Node NumList.add (عقدة (S) الجديدة) ؛ بينما (OperList.size ()> 0) {// الخطوة 3 ، كرر الخطوة الثانية حتى يتم الانتهاء من المشغل // ثانية ، أخرج الأرقام الأولى والمشغل لتشكيل عقدة رقم جديدة left = numList.Remove (0) ؛ العقدة اليمنى = numList.Remove (0) ؛ string apporator = OperatorList.Remove (0) ؛ عقدة Node = عقدة جديدة (oper ، يسار ، يمين) ؛ numList.add (0 ، العقدة) ؛ // تفضل العقدة الجديدة كأول عقدة ، ويتم تغيير العقدة السابقة مع الفهرس = 0 إلى الفهرس = 1} // الخطوة 4 ، دع عقدة الجذر تساوي الجذر العقدة الأخيرة = numList.get (0) ؛ } / *** Data Node Data* / public void output () {output (root) ؛ // إيقاف التجارة من عقدة الجذر}/*** بيانات عقدة الإخراج* param node*/public void output (node node) {if (node.getlchild ()! = null) {// إذا كانت عقدة ورقة ، فستقوم بإنهاء الإخراج (node.getlchild ()) ؛ } system.out.print (node.getData ()) ؛ // تتضمن المعاملة اجتيازًا مسبقًا (الجذر الأيسر واليمين) ، والتجبر في الطلب (الجذر الأيسر اليمين) ، و raversal postorder (الجذر الأيسر اليمين) إذا (node.getRchild ()! = null) {output (node.getrchild ()) ؛ }} public static void main (string [] args) {formaluetree tree = new formaluetree () ؛ tree.creattree ("45+23*56/2-5") ؛ // إنشاء الشجرة الثنائية لشجرة التعبير. أخيرًا ، يمكنك إخراج "45+23*56/2-5" في وحدة التحكم ، حسنًا. في الترتيب الأوسط المستخدم هنا ، يمكن للأصدقاء تجربة التأثير لاستخدام اجتياز ما قبل الترتيب وتجارة ما بعد الحدود. أما بالنسبة للالتحاق ، فسنتحدث عن ذلك لاحقًا.
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.