ตัวอย่างของอัลกอริทึมการสำรวจความลึกและความกว้างเป็นครั้งแรก

บทความนี้อธิบายถึงอัลกอริธึมการสำรวจการสำรวจแบบสำรวจและกว้างก่อนที่จะใช้ทรีไบนารีในชวา แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:

1. การวิเคราะห์

การปฏิบัติทั่วไปของการไม่กลับคืนสู่ความลึกของการสำรวจความลึกครั้งแรกของต้นไม้ไบนารีคือการใช้สแต็กและการปฏิบัติทั่วไปของการไม่กลับคืนสู่ความกว้างของการเดินทางครั้งแรกที่กว้างเป็นครั้งแรกคือการใช้คิว

การสำรวจความลึกครั้งแรก : เส้นทางสาขาที่เป็นไปได้แต่ละเส้นทางสามารถแทรกซึมได้จนกว่าจะไม่สามารถลึกลงไปได้และแต่ละโหนดสามารถเข้าถึงได้เพียงครั้งเดียว ควรสังเกตว่าการสำรวจความลึกครั้งแรกของต้นไม้ไบนารีนั้นค่อนข้างพิเศษและสามารถแบ่งย่อยออกเป็นช่วงการเดินทางผ่านการเดินทางผ่านการเดินทางผ่านช่วงกลางและการสำรวจที่ตามมา คำอธิบายเฉพาะมีดังนี้:

ลำดับแรกเดินทางข้าม : สำหรับทรีย่อยใด ๆ ให้เข้าถึงรูทก่อนจากนั้นสำรวจทรีย่อยด้านซ้ายและในที่สุดก็ข้ามทรีย่อยด้านขวา

Middle Order Traversal : สำหรับทรีย่อยใด ๆ ให้สำรวจทรีย่อยด้านซ้ายก่อนจากนั้นเข้าถึงรูทและในที่สุดก็ข้ามทรีย่อยด้านขวาของมัน

โพสต์ลำดับการเดินทาง : สำหรับทรีย่อยใด ๆ ให้สำรวจทรีย่อยด้านซ้ายก่อนจากนั้นสำรวจทรีย่อยด้านขวาของมันและในที่สุดก็เข้าถึงรูท

การสำรวจแบบกว้างก่อน : หรือที่รู้จักกันในชื่อลำดับชั้นเข้าถึงแต่ละชั้นจากบนลงล่างในทางกลับกัน ในแต่ละเลเยอร์โหนดเข้าถึงจากซ้ายไปขวา (หรือจากขวาไปซ้าย) หลังจากเข้าถึงหนึ่งเลเยอร์คุณจะเข้าสู่เลเยอร์ถัดไปจนกว่าจะไม่มีโหนดที่สามารถเข้าถึงได้

2. ให้ตัวอย่าง

แผนผังการเรียงลำดับไบนารีที่แสดงในรูปด้านล่างจำเป็นต้องใช้การสำรวจล่วงหน้า (แบบเรียกซ้ำไม่ซ้ำ), การเดินทางแบบตามลำดับ

①รหัสอ้างอิง

 Package BinaryTreetRaversetest; นำเข้า Java.util.linkedList; นำเข้า java.util.queue;/** * ลำดับความสำคัญของการสำรวจความลึกและการสำรวจความสำคัญของต้นไม้ไบนารี * @authortor * @version 1.0 2016/10/05 {BinarySortTree <Integer> Tree = New BinarySortTree <Integer> (); tree.insertNode (35); tree.insertNode (20); tree.insertNode (15); tree.insertNode (16); tree.insertNode (29); tree.insertNode (28); tree.insertNode (30); tree.insertNode (40); tree.insertNode (50); tree.insertNode (45); tree.insertNode (55); System.out.print ("preorder traversal (ซ้ำ):"); tree.preordertraverse (tree.getroot ()); System.out.println (); System.out.print ("In-order traversal (ซ้ำ):"); tree.inordertraverse (tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("โพสต์สั่งการเดินทาง (ซ้ำ):"); tree.postordertraverse (tree.getroot ()); System.out.println (); System.out.print ("precursive traversal (non-recursive):"); tree.preordertraversenorecursion (tree.getroot ()); System.out.println (); System.out.print ("In-order traversal (ไม่ซ้ำ):"); tree.inordertraversenorecursion (tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("โพสต์สั่งการเดินทาง (ไม่ซ้ำ):"); tree.postordertraversenorecursion (tree.getroot ()); System.out.println (); System.out.print ("Breadthpriority Traversal:"); tree.breadthfirsttraverse (tree.getroot ()); }}/*** โหนด*/คลาสโหนด <E ขยายการเปรียบเทียบ <E >> {ค่า e; โหนด <e> ซ้าย; โหนด <E> ขวา; โหนด (ค่า e) {this.value = value; ซ้าย = null; ขวา = null; }}/** * ใช้ลำดับก่อนหน้าเพื่อสร้างต้นไม้เรียงลำดับไบนารี (หรือที่รู้จักกันในชื่อแผนผังไบนารี) */คลาสไบนารี BinarySortTree <E ขยายเทียบเคียงได้ <e>> {โหนดส่วนตัว <E> รูท; BinarySortTree () {root = null; } โมฆะสาธารณะ insertNode (ค่า e) {ถ้า (root == null) {root = new node <e> (ค่า); กลับ; } โหนด <E> currentNode = root; ในขณะที่ (จริง) {ถ้า (value.Compareto (currentNode.Value)> 0) {ถ้า (currentNode.right == null) {currentNode.right = new Node <E> (value); หยุดพัก; } currentNode = currentNode.right; } else {ถ้า (currentNode.left == null) {currentNode.left = new node <e> (value); หยุดพัก; } currentNode = currentNode.left; }}} โหนดสาธารณะ <e> getRoot () {return root; } / ** * การสั่งซื้อล่วงหน้าของทรีไบนารี (ซ้ำ) * @param โหนด * / โมฆะสาธารณะ preortertraverse (โหนด <e> โหนด) {system.out.print (node.value + ""); if (node.left! = null) preordertraverse (node.left); if (node.right! = null) preordertraverse (node.right); } / ** * traversal คำสั่งซื้อของต้นไม้ไบนารี (ซ้ำ) * @param node * / โมฆะสาธารณะ inorderTraverse (โหนด <E> โหนด) {ถ้า (node.left! = null) inorderTraverse (node.left); System.out.print (node.value + ""); if (node.right! = null) InorderTraverse (node.right); } / ** * การเดินทางหลังการสั่งซื้อของทรีไบนารี (ซ้ำ) * @param โหนด * / โมฆะสาธารณะ postorderTraverse (โหนด <E> โหนด) {ถ้า (node.left! = null) postorderTraverse (node.left); if (node.right! = null) postorderTraverse (node.right); System.out.print (node.value + ""); } / ** * การสั่งซื้อล่วงหน้าของต้นไม้ไบนารี (ไม่ซ้ำ) * @param root * / โมฆะสาธารณะ preordertraversenorecursion (Node <e> root) {linkedList <node <e>> stack = new LinkedList <node <e>> (); โหนด <E> currentNode = null; stack.push (รูท); ในขณะที่ (! stack.isempty ()) {currentNode = stack.pop (); System.out.print (currentnode.value + ""); if (currentNode.right! = null) stack.push (currentNode.right); if (currentNode.left! = null) stack.push (currentNode.left); }} / ** * traversal คำสั่งซื้อของต้นไม้ไบนารี (ไม่ซ้ำ) * @param root * / โมฆะสาธารณะ inorderTraversenorecursion (Node <e> รูท) {linkedList <node <e>> stack = new LinkedList <node <e>> (); โหนด <E> currentNode = root; ในขณะที่ (currentNode! = null ||! stack.isEmpty ()) {// loop จนกระทั่งโหนดใบซ้ายสุดที่ต้นไม้เรียงลำดับไบนารี (currentNode เป็น null) ในขณะที่ (currentNode! = null) {stack.push (currentNode); currentNode = currentNode.left; } currentNode = stack.pop (); System.out.print (currentnode.value + ""); currentNode = currentNode.right; }} / ** * การเดินทางหลังการสั่งซื้อของต้นไม้ไบนารี (ไม่ซ้ำ) * @param root * / โมฆะสาธารณะ postorderTraversenorecursion (Node <e> รูท) {linkedList <node <e >> stack = new LinkedList <node <e>> (); โหนด <E> currentNode = root; โหนด <E> rightNode = null; ในขณะที่ (currentNode! = null ||! stack.isEmpty ()) {// loop จนกระทั่งโหนดใบที่ปลายด้านซ้ายสุดของทรีเรียงลำดับไบนารี (currentNode คือ null) ในขณะที่ (currentNode! = null) {stack.push (currentNode); currentNode = currentNode.left; } currentNode = stack.pop (); // โหนดปัจจุบันไม่มีโหนดที่ถูกต้องหรือโหนดก่อนหน้า (โหนดที่ได้รับเอาต์พุต) เป็นโหนดขวาของโหนดปัจจุบันจากนั้นโหนดปัจจุบันจะถูกส่งออกในขณะที่ (currentNode.right == null || currentNode.right == rightNode) rightNode = currentNode; if (stack.isempty ()) {return; // outputs รูทปลาย traversal} currentNode = stack.pop (); } stack.push (currentNode); // ยังมีโหนดที่เหมาะสมที่ไม่ผ่าน currentNode = currentNode.right; }} / *** ต้นไม้ไบนารีทราเวิร์สแบบกว้างก่อนหรือที่รู้จักกันในชื่อต้นไม้ไบนารีทราเวอเรลแบบลำดับชั้น* @param โหนด* / โมฆะสาธารณะ BreadthFirstTraverse (Node <e> ราก) {คิว <node <e>> queue = new LinkedList <node โหนด <E> currentNode = null; queue.offer (รูท); ในขณะที่ (! queue.isempty ()) {currentNode = queue.poll (); System.out.print (currentnode.value + ""); if (currentNode.left! = null) queue.offer (currentNode.left); if (currentNode.right! = null) queue.offer (currentNode.right); -

②ผลลัพธ์ผลลัพธ์

Prederger Traversal (ซ้ำ): 35 20 15 16 29 28 30 40 50 45 55
การเดินทางตามลำดับ (การเรียกซ้ำ): 15 16 20 28 29 30 35 40 45 50 55
Postorder Traversal (การเรียกซ้ำ): 16 15 28 30 29 20 45 55 50 40 35
การสั่งซื้อล่วงหน้า (ไม่ซ้ำ): 35 20 15 16 29 28 30 40 50 45 55
การเดินทางตามลำดับ (ไม่ซ้ำ): 15 16 20 28 29 30 35 40 45 50 55
Postorder Traversal (ไม่ซ้ำ): 16 15 28 30 29 20 45 55 50 40 35
การสำรวจความสำคัญแบบกว้าง: 35 20 40 15 29 50 16 28 30 45 55

สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป

ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน