หนึ่งคำจำกัดความต้นไม้เรียงลำดับไบนารี
1. คำจำกัดความของต้นไม้เรียงลำดับไบนารี <br /> ต้นไม้เรียงลำดับไบนารี (ต้นไม้เรียงลำดับไบนารี) หรือที่เรียกว่าต้นไม้ค้นหาไบนารี มันถูกกำหนดเป็น: ต้นไม้เรียงลำดับไบนารีหรือต้นไม้ที่ว่างเปล่าหรือต้นไม้ไบนารีที่ตรงกับคุณสมบัติต่อไปนี้:
①หากทรีย่อยด้านซ้ายไม่ว่างค่าของโหนดทั้งหมดในทรีย่อยด้านซ้ายจะเล็กกว่าค่าของโหนดรูท
②หากทรีย่อยด้านขวาไม่ว่างค่าของโหนดทั้งหมดในทรีย่อยด้านขวาจะมากกว่าค่าของโหนดรูท
subtrees subtrees ซ้ายและขวาตัวเองเป็นต้นไม้เรียงลำดับแบบไบนารี
คุณสมบัติข้างต้นเรียกว่าคุณสมบัติต้นไม้เรียงลำดับไบนารี (คุณสมบัติ BST) ดังนั้นต้นไม้เรียงลำดับไบนารีจึงเป็นต้นไม้ไบนารีที่ตอบสนองคุณสมบัติ BST
2. คุณสมบัติของต้นไม้การเรียงลำดับไบนารี <br /> โอนทรีเรียงลำดับไบนารีในลำดับกลางและลำดับการเดินทางผ่านลำดับกลางที่ได้คือลำดับที่เพิ่มขึ้นตามลำดับ
3. ใส่ต้นไม้เรียงลำดับไบนารี <br /> ใส่โหนดใหม่ลงในต้นไม้เรียงลำดับไบนารีเพื่อให้แน่ใจว่าต้นไม้ไบนารีที่แทรกยังคงตรงตามคำจำกัดความของต้นไม้เรียงลำดับไบนารี
กระบวนการแทรก:
หากต้นไม้เรียงลำดับไบนารีว่างเปล่าโหนด *S จะถูกแทรกลงในต้นไม้ที่ว่างเปล่าเป็นโหนดรูท
เมื่อมันไม่ว่างให้เปรียบเทียบคีย์คำหลัก s-> ที่จะใส่กับคีย์คำหลักทรีรูทคีย์เวิร์ด t-> คีย์ ถ้า s-> key = t-> คีย์ไม่จำเป็นต้องแทรก ถ้าคีย์ s-> <t-> จะถูกแทรกลงในทรีย่อยด้านซ้ายของรูท ถ้า s-> key> t-> คีย์มันจะถูกแทรกลงในทรีย่อยด้านขวาของรูท กระบวนการแทรกในทรีย่อยเหมือนกับกระบวนการแทรกในต้นไม้ สิ่งนี้จะดำเนินต่อไปจนกว่าโหนด *s จะถูกแทรกลงในต้นไม้เรียงลำดับไบนารีเป็นใบไม้ใหม่หรือจนกว่าต้นไม้จะพบว่ามีโหนดที่มีคำหลักเดียวกัน
4. ค้นหาแผนผังการเรียงลำดับไบนารี <br /> โดยสมมติว่าตัวชี้รูทของทรีเรียงลำดับไบนารีคือรูทและค่าคำหลักที่กำหนดคือ k อัลกอริทึมการค้นหาสามารถอธิบายได้ว่า::
①ตั้งค่าเริ่มต้น: q = root;
②ถ้า k = q -> คีย์การค้นหาจะสำเร็จและอัลกอริทึมจะสิ้นสุดลง;
③มิฉะนั้นถ้า k <q －＞ คีย์และทรีย่อยด้านซ้ายของ Q ไม่ว่างเปล่าทรีย่อยด้านซ้ายของ Q จะถูกส่งไปยัง Q จากนั้นขั้นตอน②; มิฉะนั้นการค้นหาจะล้มเหลวและอัลกอริทึมจะสิ้นสุดลง
④มิฉะนั้นถ้า k＞ q －＞ คีย์และทรีย่อยด้านขวาของ Q ไม่ว่างเปล่าทรีย่อยที่ถูกต้องของ Q จะถูกส่งไปยัง Q จากนั้นขั้นตอน②; มิฉะนั้นการค้นหาจะล้มเหลวและอัลกอริทึมจะสิ้นสุดลง
5. การลบต้นไม้เรียงลำดับไบนารี <br /> สมมติว่าโหนดที่ถูกลบคือ *p และผู้ปกครองคือ *f ซึ่งไม่ได้หายไปในทั่วไป สมมติว่า *p เป็นลูกซ้ายของ *f ต่อไปนี้แบ่งออกเป็นสามสถานการณ์:
⑴ถ้าโหนด *P เป็นโหนดใบคุณจะต้องแก้ไขตัวชี้ของโหนดพาเรนต์ *f
⑵หากโหนด *p มีเฉพาะทรีย่อยด้านซ้ายหรือเฉพาะทรีย่อยด้านขวาของ PR จากนั้นเพียงแค่ทำให้ PL หรือ PR เป็นทรีย่อยด้านซ้ายของโหนดพาเรนต์
⑶หากทรีทรีย่อยซ้ายและขวาของโหนด *p ไม่ว่างเปล่าก่อนอื่นให้ค้นหาลำดับก่อนหน้า (หรือตัวตายตัวแทน) โหนด *s ของ *p (โปรดทราบว่า *s คือโหนดขวาสุดที่ต่ำที่สุดในทรีย่อยด้านซ้ายของ *p และโดเมนโซ่ด้านซ้าย ไปยังห่วงโซ่ด้านขวาของโหนดบรรพบุรุษก่อนหน้าของ *P ②แทนที่ *P ด้วยโหนดลำดับก่อนหน้า *s ของ *P (นั่นคือคัดลอกข้อมูลของ *S ลงใน *P) และห่วงโซ่ทรีย่อยด้านซ้ายของ *S ไปทางซ้าย (หรือขวา) ของห่วงโซ่ของโหนดแม่ *q ของ *s
6. การสำรวจต้นไม้ไบนารี <br /> มีสามวิธีในการสำรวจต้นไม้ไบนารีดังนี้:
(1) การสั่งซื้อล่วงหน้า (DLR) ก่อนการเข้าถึงโหนดรูทก่อนจากนั้นจะข้ามทรีย่อยด้านซ้ายและในที่สุดก็ข้ามทรีย่อยด้านขวา รูทตัวย่อ - ซ้าย - ขวา
(2) In-order traversal (LDR), traversal แรกผ่านทรีย่อยด้านซ้ายจากนั้นเข้าถึงโหนดรูทและในที่สุดก็ข้ามทรีย่อยด้านขวา หมายเหตุย่อ: ซ้ายรากขวา
(3) โพสต์ลำดับการเดินทาง (LRD), ผ่านทรีย่อยด้านซ้ายก่อนจากนั้นข้ามทรีย่อยด้านขวาและในที่สุดก็เข้าถึงโหนดรูท ตัวย่อซ้ายขวา
2. การเขียนรหัส
1. คำจำกัดความของคลาสโหนดต้นไม้ 0
แพ็คเกจ com.lin; / ** * ฟังก์ชั่นสรุป: */ คลาสสาธารณะ treenode {ข้อมูลจำนวนเต็มสาธารณะ; /* โหนดพาเรนต์ของโหนดนี้*/ Public Treenode Parent; /*โหนดลูกซ้ายของโหนดนี้*/ สาธารณะ treenode ซ้าย; /*โหนดลูกขวาของโหนดนี้*/ สาธารณะ treenode สาธารณะ; Public Treenode (ข้อมูลจำนวนเต็ม) {this.data = ข้อมูล; } @Override สตริงสาธารณะ toString () {return "treenode [data =" + data + "]"; - 2. คำจำกัดความของต้นไม้เรียงลำดับไบนารี
แพ็คเกจ com.lin; /*** ฟังก์ชั่นสรุป: Sort/Balanced Binary Tree*/Public Class Searchtree {Public Treenode Root; สาธารณะขนาดยาว / ** * เพิ่มโหนดลงในทรี * @param data * @return การแทรกบูลีนส่งคืนจริง */ บูลีนสาธารณะ addTreenode (ข้อมูลจำนวนเต็ม) {ถ้า (null == รูท) {root = new treenode (ข้อมูล); System.out.println ("ข้อมูลถูกแทรกลงในต้นไม้ไบนารีที่สมดุล"); กลับมาจริง; } treenode treenode = new treenode (data); // ข้อมูลที่จะแทรก treenode currentNode = root; treenode parentnode; ในขณะที่ (จริง) {parentNode = currentNode; // บันทึกโหนดพาเรนต์ // ข้อมูลที่แทรกมีขนาดเล็กกว่าโหนดพาเรนต์ถ้า (currentNode.data> data) {currentNode = currentNode.left; // โหนดลูกด้านซ้ายของโหนดพาเรนต์ปัจจุบันว่างเปล่าถ้า (null == currentNode) {parentNode.left = treenode; treenode.parent = parentNode; System.out.println ("ข้อมูลถูกแทรกลงในแผนผังไบนารีได้สำเร็จ"); ขนาด ++; กลับมาจริง; } // ข้อมูลที่แทรกมีขนาดใหญ่กว่าโหนดพาเรนต์} อื่นถ้า (currentNode.data <data) {currentNode = currentNode.right; // โหนดลูกที่ถูกต้องของโหนดพาเรนต์ปัจจุบันว่างเปล่าถ้า (null == currentNode) {parentNode.right = treenode; treenode.parent = parentNode; System.out.println ("ข้อมูลจะถูกแทรกลงในแผนผังไบนารีได้สำเร็จ"); ขนาด ++; กลับมาจริง; }} else {system.out.println ("ข้อมูลอินพุตเหมือนกับข้อมูลของโหนด"); กลับเท็จ; }}} / ** * @param data * @return treenode * / public treenode findTreenode (ข้อมูลจำนวนเต็ม) {ถ้า (null == รูท) {return null; } treenode current = root; ในขณะที่ (ปัจจุบัน! = null) {ถ้า (current.data> data) {current = current.left; } อื่นถ้า (current.data <data) {current = current.right; } else {return current; }} return null; - นี่คือวิธีการเพิ่มและค้นหา
3. การเดินทางด้านหน้ากลางและด้านหลัง
แพ็คเกจ com.lin; นำเข้า java.util.stack; / *** ฟังก์ชั่นสรุป:*/ คลาสสาธารณะ treeorder {/ *** การใช้งานซ้ำของการเดินทาง preorder traversal* @author linbingwen* @since 29 สิงหาคม 2015* @param treenode*/ โมฆะสาธารณะคงที่ preortermethodone (treenode) {ถ้า (null! = treenode) if (null! = treenode.left) {preordermethodone (treenode.left); } if (null! = treenode.right) {preordermethodone (treenode.right); }}} / *** การวนลูปเพื่อใช้งาน preorder traversal* @param treenode* / โมฆะสาธารณะคงที่ preordermethodtwo (treenode treenode) {ถ้า (null! = treenode) {stack <Treenode> stack = ใหม่สแต็ก <treenode> (); stack.push (treenode); ในขณะที่ (! stack.isempty ()) {treenode tempnode = stack.pop (); System.out.print (tempnode.data + ""); // โหนดลูกที่ถูกต้องไม่เป็นโมฆะใส่โหนดลูกที่ถูกต้องใน if (null! = tempNode.right) {stack.push (tempnode.right); } // หลังจากวางโหนดลูกที่ถูกต้องใส่โหนดลูกซ้ายและใช้ถ้า (null! = tempnode.left) {stack.push (tempnode.left); }}}} / *** ใช้งานซ้ำในการเดินทางตามลำดับ* @param treenode* / public static void medordermethodone (treenode treenode) {ถ้า (null! = treenode) {ถ้า (null! = treenode.left) {medordermethodone } system.out.print (treenode.data + ""); if (null! = treenode.right) {MedorderMethodone (treenode.right); }}} / *** การใช้งานวนรอบการเดินทางตามลำดับ* @param treenode* / โมฆะสาธารณะคงที่ MedorderMethodtwo (treenode treenode) {สแต็ก <Treenode> สแต็ก = สแต็กใหม่ <Treenode> (); treenode current = treenode; ในขณะที่ (ปัจจุบัน! = null ||! stack.isempty ()) {ในขณะที่ (ปัจจุบัน! = null) {stack.push (ปัจจุบัน); current = current.left; } if (! stack.isempty ()) {current = stack.pop (); System.out.print (current.data+""); current = current.right; }}} / *** ใช้การเดินทางแบบโพสต์ลำดับซ้ำ* @param treenode* / โมฆะสาธารณะคงที่ postorderMethodone (treenode treenode) {ถ้า (null! = treenode) {ถ้า (null! = treenode.left) {postorderMethodone (treenode. } if (null! = treenode.right) {postorderMethodone (treenode.right); } system.out.print (treenode.data + ""); }} / *** การวนลูปเพื่อใช้งานโพสต์ลำดับการเดินทาง* @param treenode* / โมฆะคงที่สาธารณะ postorderMethodtwo (treenode treenode) {ถ้า (null! = treenode) {stack <Treenode> stack = ใหม่ stack <treenode> (); treenode current = treenode; treenode rightNode = null; ในขณะที่ (ปัจจุบัน! = null ||! stack.isempty ()) {ในขณะที่ (ปัจจุบัน! = null) {stack.push (ปัจจุบัน); current = current.left; } current = stack.pop (); ในขณะที่ (ปัจจุบัน! = null && (current.right == null || current.right == rightNode)) {system.out.print (current.data + ""); rightNode = ปัจจุบัน; if (stack.isempty ()) {system.out.println (); กลับ; } current = stack.pop (); } stack.push (ปัจจุบัน); current = current.right; - 4. วิธีใช้
แพ็คเกจ com.lin; / ** * ฟังก์ชั่นสรุป: */ คลาสสาธารณะ searchTreetest {/ ** * @param args */ โมฆะคงที่สาธารณะหลัก (สตริง [] args) {searchtree tree = ใหม่ searchtree (); tree.addtreenode (50); tree.addtreenode (80); tree.addtreenode (20); tree.addtreenode (60); tree.addtreenode (10); tree.addtreenode (30); tree.addtreenode (70); tree.addtreenode (90); tree.addtreenode (100); tree.addtreenode (40); System.out.println ("======================================================================================================================== - - - - - - System.out.println ("================================================== - - - - - - - TreeOrder.postorderMethodone (tree.root); System.out.println ("=================================================================================================================== - - - - - - System.out.println ("================================================== - - - - - - - TreeOrder.MedOrderMethodtwo (tree.root);ผลลัพธ์ผลลัพธ์:
ในทำนองเดียวกันกระบวนการค้นหามีดังนี้:
treenode node = tree.findTreenode (100); System.out.println (โหนด);
ผลลัพธ์ถูกต้อง
ข้างต้นเป็นการแนะนำรายละเอียดเกี่ยวกับต้นไม้เรียงลำดับแบบไบนารี Java ฉันหวังว่ามันจะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน