ต้นไม้ไบนารีคืออะไร? ฉันจะไม่แนะนำที่นี่ คุณสามารถใช้ Baidu: ต้นไม้ไบนารี ที่นี่ใช้ Java เพื่อใช้ "Expression Binary Tree"
คำจำกัดความของต้นไม้ไบนารีนิพจน์
ขั้นตอนแรกคือการเข้าใจว่าต้นไม้ไบนารีแสดงออกคืออะไร? ตัวอย่างเช่นนิพจน์: (a+b × (cd))-e/f การวางตัวเลขในโหนดใบและตัวดำเนินการในโหนดสาขาจะสร้างต้นไม้ไบนารี เนื่องจากมันเก็บการแสดงออกจึงเรียกว่า "ต้นไม้ไบนารีนิพจน์"
รองเท้าบูทสำหรับเด็กอาจอยากรู้ว่าสิ่งนี้สร้างขึ้นได้อย่างไร? ใช้ตัวอย่าง 45+23*56/2-5 เป็นตัวอย่าง ก่อนอื่นนำหมายเลขแรก 45 ออกมาและวางไว้ในโหนดใบไม้ หลังจากพบ "+" วางไว้ในโหนดสาขา
จากนั้นใส่ "23", "*", "56", "/" และ "2" ตามลำดับ
ใส่ในที่สุด "-" และ "5"
นั่นคือประมาณว่า (ฉันวาดรูปเหล่านี้ด้วยตัวเองมันน่าเกลียดแค่ดูพวกเขา (⊙⊙))
ขั้นตอนในการสร้างต้นไม้ไบนารีนิพจน์
1. สร้างวัตถุโหนด
2. แยกแยะตัวดำเนินการและข้อมูลและจัดเก็บไว้ในรายการที่เกี่ยวข้อง (คิว);
3. นำตัวเลขสองตัวแรกออกมาและผู้ให้บริการเพื่อสร้างโหนดหมายเลขใหม่
4. ทำซ้ำขั้นตอนที่ 3 จนกว่าผู้ประกอบการจะเสร็จสิ้น
5. ให้โหนดรูทเท่ากับโหนดสุดท้าย
การใช้ต้นไม้ไบนารีนิพจน์
ขั้นแรกให้สร้างคลาส Object Node รวมถึงข้อมูลทรีย่อยด้านซ้ายทรีย่อยด้านขวาและหลายชุดและรับวิธีการ
แพ็คเกจ TETS0714;/** * คลาส Object Node * @author yuxiu * */โหนดคลาสสาธารณะ {// ข้อมูลสตริงข้อมูลส่วนตัว; // LEFT SUBTREE NODE ส่วนตัว lchild; // Subtree Right Private Node rchild; node () {} node (ข้อมูลสตริง) {this.data = data; } โหนด (ข้อมูลสตริง, โหนด lchild, โหนด rchild) {super (); this.data = ข้อมูล; this.lchild = lchild; this.rchild = rchild; } สตริงสาธารณะ getData () {ส่งคืนข้อมูล; } โหนดสาธารณะ getLchild () {return lchild; } โหนดสาธารณะ getRchild () {return rchild; -จากนั้นสร้างต้นไม้ไบนารีนิพจน์
แพ็คเกจ Tets0714; นำเข้า Java.util.arraylist;/** * การแสดงออกของคลาสไบนารีต้นไม้ * @author yuxiu * */คลาสสาธารณะ formaluetree {สตริงส่วนตัว s = ""; รูทโหนดส่วนตัว // root node/*** สร้าง expression binary tree* @param str expression*/public void creattree (string str) {// ประกาศรายการอาร์เรย์, ผู้ให้บริการ, เพิ่ม, เพิ่ม, ลบ, การคูณและการหาร, arraylist <String> operatorList = new ArrayList <String> (); // ประกาศรายการอาร์เรย์, เก็บข้อมูลโหนด, arraylist <node> numList = new ArrayList <Node> (); // ก่อนอื่นแยกแยะผู้ประกอบการและข้อมูลและจัดเก็บไว้ในรายการที่สอดคล้องกันสำหรับ (int i = 0; i <str.length (); i ++) {char ch = str.charat (i); // ดึงอักขระของสตริงถ้า (ch> = '0' && ch <= '9') {s+= ch; } else {numList.add (โหนดใหม่); s = ""; operatorlist.add (ch+""); }} // เพิ่มหมายเลขสุดท้ายลงในหมายเลข NODE NUMLIST.ADD (โหนดใหม่); ในขณะที่ (operlist.size ()> 0) {// ขั้นตอนที่ 3 ทำซ้ำขั้นตอนที่สองจนกว่าตัวดำเนินการจะเสร็จสิ้น // วินาทีให้นำตัวเลขสองตัวแรกออกมาและตัวดำเนินการเพื่อสร้างโหนดหมายเลขใหม่ซ้าย = numList.remove (0); โหนดขวา = numList.remove (0); String Operator = OperatorList.remove (0); โหนดโหนด = โหนดใหม่ (ทำงาน, ซ้าย, ขวา); numlist.add (0, โหนด); // ชอบโหนดใหม่เป็นโหนดแรกและโหนดก่อนหน้าด้วย index = 0 ถูกเปลี่ยนเป็น index = 1} // ขั้นตอนที่ 4 ให้โหนดรูทเท่ากับรูทโหนดสุดท้าย = numList.get (0); } / *** ข้อมูลโหนดเอาต์พุต* / โมฆะสาธารณะเอาต์พุต () {เอาต์พุต (รูท); // หยุด traversal จากโหนดรูท}/*** ข้อมูลโหนดเอาต์พุต* @param โหนด*/เอาต์พุตโมฆะสาธารณะ (โหนดโหนด) {ถ้า (node.getlchild ()! = null) {// ถ้าเป็นโหนดใบ } system.out.print (node.getData ()); // การทำธุรกรรมรวมถึงการเดินทางล่วงหน้า (รูทซ้ายและขวา), การเดินทางข้ามคำสั่ง (รูทซ้ายขวา), และการเดินทางผ่านการเดินทาง (ซ้ายรูทขวา) ถ้า (node.getrchild ()! = null) {เอาต์พุต (node.getRchild ()); }} โมฆะคงที่สาธารณะหลัก (สตริง [] args) {formaluetree tree = ใหม่ formaluetree (); tree.creattree ("45+23*56/2-5"); // สร้างทรีไบนารีของทรีนิพจน์เอาท์พุท (); // การตรวจสอบเอาต์พุต}} ในที่สุดคุณสามารถส่งออก "45+23*56/2-5" ในคอนโซลตกลง ในการเดินทางกลางลำดับกลางที่ใช้ที่นี่เพื่อนสามารถลองใช้สิ่งที่เอฟเฟ็กต์ใช้เพื่อใช้การเดินทางข้ามล่วงหน้าและโพสต์ออร์เดอร์ สำหรับ Traversal เราจะพูดถึงเรื่องนี้ในภายหลัง
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น