ในชีวิตการเขียนโปรแกรมเรามักจะพบโครงสร้างต้นไม้ ในช่วงไม่กี่วันที่ผ่านมาเราเพียงแค่ต้องใช้โครงสร้างต้นไม้ดังนั้นเราจึงบันทึกวิธีการและกระบวนการของเราเอง ตอนนี้สมมติว่ามีต้นไม้เช่นนี้ (ไม่สำคัญว่าจะเป็นต้นไม้ไบนารีหรือไม่หลักการเหมือนกัน)
1. ลำดับความสำคัญ
ตัวย่อภาษาอังกฤษคือ DFS คือการค้นหาครั้งแรกที่ลึกซึ้ง
การค้นหาที่ลึกซึ้งครั้งแรกเป็นวิธีที่ใช้กันทั่วไปในช่วงแรกของการพัฒนาซอฟต์แวร์รวบรวมข้อมูลการพัฒนา วัตถุประสงค์ของมันคือการไปถึงโหนดใบของโครงสร้างการค้นหา (เช่นไฟล์ HTML ที่ไม่มีการเชื่อมโยงหลายมิติใด ๆ ) ในไฟล์ HTML เมื่อมีการเลือกไฮเปอร์ลิงก์ไฟล์ HTML ที่เชื่อมโยงจะทำการค้นหาที่ลึกอันดับแรกนั่นคือห่วงโซ่แยกต่างหากจะต้องค้นหาเต็มก่อนที่จะค้นหาผลลัพธ์ไฮเปอร์ลิงก์ที่เหลืออยู่ การค้นหาลำดับความสำคัญเชิงลึกติดตามการเชื่อมโยงหลายมิติบนไฟล์ HTML จนกว่าจะไม่สามารถลึกลงไปอีกแล้วกลับไปยังไฟล์ HTML ที่แน่นอนและยังคงเลือกไฮเปอร์ลิงก์อื่น ๆ ในไฟล์ HTML เมื่อไม่มีการเชื่อมโยงหลายมิติอื่น ๆ การค้นหาได้สิ้นสุดลง กระบวนการนี้เป็นเพียงการเข้าไปลึกเข้าไปในทุกเส้นทางสาขาที่เป็นไปได้จนกว่าจะไม่สามารถลึกลงไปได้และแต่ละโหนดสามารถเข้าถึงได้เพียงครั้งเดียว สำหรับตัวอย่างข้างต้นผลลัพธ์ของการสำรวจความลึกครั้งแรกคือ: A, B, D, E, I, C, F, G, H. (สมมติว่าด้านซ้ายของโหนดเด็กถูกทิ้งไว้ก่อน)
ลำดับความสำคัญของความลึกใช้ในการสำรวจแต่ละโหนดและจำเป็นต้องมีโครงสร้างข้อมูลเช่นฮีป ลักษณะของสแต็คคือการไปก่อนแล้วออก กระบวนการข้ามทั้งหมดมีดังนี้:
ก่อนอื่นให้กด Node A ลงในกองซ้อน (A);
โผล่ขึ้นมาโหนด A และกดโหนดลูกของ C และ B ลงในกองในเวลาเดียวกัน ในเวลานี้ B อยู่ด้านบนของกองซ้อน (B, C);
ปรากฏขึ้นโหนด B และกดโหนดลูกของ B และ D ลงในกอง ในเวลานี้ D อยู่ด้านบนสุดของกองสแต็ก (D, E, C);
ป๊อปอัพโหนด D ไม่มีโหนดเด็กถูกกดและ E อยู่ที่ด้านบนของกองสแต็ก (E, C);
ปรากฏขึ้นโหนด e และกดโหนดลูกของฉันลงในสแต็ก (i, c);
... ลงในทางกลับกันและการเดินทางครั้งสุดท้ายเสร็จสมบูรณ์ รหัส Java มีดังนี้:
โมฆะสาธารณะ depthFirst () {stack <map <string, object >> nodeStack = ใหม่สแต็ก <แผนที่ <สตริง, วัตถุ >> (); แผนที่ <สตริง, วัตถุ> node = new hashmap <string, object> (); nodeStack.add (Node); ในขณะที่ (! nodeStack.isEmpty ()) {node = nodeStack.pop (); system.out.println (โหนด); // รับโหนดลูกของโหนด สำหรับต้นไม้ไบนารีมันคือการได้รับโหนดเด็กด้านซ้ายและโหนดลูกที่ถูกต้องของรายการโหนด <แผนที่ <สตริงวัตถุ >> เด็ก = getChildren (โหนด); ถ้า (เด็ก! = null &&! เด็ก ๆ2. ลำดับความสำคัญที่กว้าง
ตัวย่อภาษาอังกฤษคือ BFS ซึ่งหมายถึงการค้นหาครั้งแรกที่กว้าง ตามการทดสอบกระบวนการแต่ละชั้นของโหนดจะถูกเข้าถึงในทางกลับกันและหลังจากเข้าถึงหนึ่งเลเยอร์แต่ละโหนดสามารถเข้าถึงได้เพียงครั้งเดียว สำหรับตัวอย่างข้างต้นผลลัพธ์ของการสำรวจครั้งแรกที่กว้างคือ: A, B, C, D, E, F, G, H, I (สมมติว่าแต่ละชั้นของโหนดเข้าถึงได้จากซ้ายไปขวา)
ลำดับความสำคัญที่กว้างใช้ในการสำรวจแต่ละโหนดและจำเป็นต้องมีโครงสร้างข้อมูลเช่นคิว ลักษณะของคิวเป็นครั้งแรก-ออกก่อนและในความเป็นจริงมันยังสามารถใช้คิวสองปลาย ความแตกต่างคือโหนดสามารถแทรกและโผล่ขึ้นมาที่ตำแหน่งแรกของคิวสองปลาย กระบวนการข้ามทั้งหมดมีดังนี้:
แทรกครั้งแรกโหนด a ลงในคิวคิว (a);
ป๊อปอัพโหนด A และแทรกโหนดลูก B และ C ของ A ลงในคิว ในเวลานี้ B อยู่ที่จุดเริ่มต้นของคิวและ C อยู่ที่ปลายคิวคิว (B, C);
ปรากฏขึ้นโหนด B และแทรกโหนดลูก D และ E ของ B ลงในคิวในเวลาเดียวกัน ในเวลานี้ C อยู่ที่จุดเริ่มต้นของคิวและ E อยู่ที่ปลายคิวคิว (C, D, E);
ปรากฏขึ้นโหนด C และแทรกโหนดลูก f, g, h ของ c ลงในคิว ในเวลานี้ D อยู่ที่หัวของคิวและ H อยู่ที่ปลายคิวคิว (D, E, F, G, H);
ป๊อปอัพโหนด d, d ไม่มีโหนดลูกในเวลานี้ e อยู่ที่หัวของคิว, h อยู่ที่หางของคิวคิวคิว (e, f, g, h, h);
... ลงในทางกลับกันและการเดินทางครั้งสุดท้ายเสร็จสมบูรณ์ รหัส Java มีดังนี้:
โมฆะสาธารณะ BreadFirst () {deque > nodeDeque = new ArrayDeque - แผนที่ node = new hashmap - Nodedequ.add (Node); ในขณะที่ (! nodedeque.isempty ()) {node = nodedequ.peekfirst (); System.out.println (โหนด); // รับโหนดลูกของโหนด สำหรับต้นไม้ไบนารีโหนดเด็กซ้ายและโหนดลูกที่ถูกต้องของโหนดจะได้รับรายการของโหนด > เด็ก = getChildren (โหนด); ถ้า (เด็ก ๆ ! = null &&! children.isempty ()) {สำหรับ (แผนที่เด็ก: เด็ก) {nodedequ.add (เด็ก); }}}} // คิวสองปลายถูกใช้ที่นี่ซึ่งเหมือนกับการใช้คิว สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับตัวอย่างรหัสการใช้งาน Java ที่ลึกและกว้างเป็นครั้งแรกและฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!