เชี่ยวชาญอัลกอริธึมเชิงลึกโครงสร้างต้นไม้ JavaScript ในบทความเดียว

ต้นไม้คืออะไร

ในชีวิตจริง ฉันเชื่อว่าทุกคนคุ้นเคยกับต้นไม้ ไม่ว่าจะเป็นต้นหลิว ต้นป็อปลาร์ หรือต้นพีช อาจกล่าวได้ว่าต้นไม้สามารถพบเห็นได้ทั่วไปในโลก คอมพิวเตอร์ ของแบบจำลองโครงสร้างลำดับชั้น

ดังที่แสดงด้านล่าง:

โครงสร้างแบบต้นไม้มีการใช้งานหลายอย่าง ตัวอย่างเช่น โครงสร้างองค์กรของบริษัทสามารถแสดงด้วยแบบต้นไม้ได้ ดังที่แสดงด้านล่าง:

นอกเหนือจากโครงสร้างองค์กรแล้ว สิ่งต่างๆ เช่น แผนภูมิลำดับวงศ์ตระกูล จังหวัด และเมือง ฯลฯ สามารถแสดงได้โดยใช้โครงสร้างแผนภูมิ

คำศัพท์เกี่ยวกับต้นไม้

มีคำศัพท์สำหรับต้นไม้หลายคำ ดังแสดงด้านล่าง

• Tree : ชุดจำกัดของโหนด n (n≥0) เมื่อ n=0 เรียกว่าแผนผังว่าง ระดับ
• ของโหนด : จำนวนทรีย่อย ของโหนด ตัวอย่างเช่น ระดับของโหนด B คือ 2 และ ระดับของโหนด A คือ 3;
ระดับของ
• tree :
• ระดับ สูงสุดระหว่างโหนดทั้งหมดของ tree. ตัวอย่างเช่น ในรูปด้านบน ระดับของ tree คือ 3;
• เรียกอีกอย่างว่าโหนดใบ ;
• โหนดย่อย : ดังแสดงในรูปด้านบน
• โหนดพี่น้อง : ดังแสดงในภาพด้านบน
• โหนดราก : ดังแสดงในภาพด้าน
• บน ; เช่น ความลึกของแผนผังในภาพด้านบนคือ 3
• ระดับของโหนด เช่น ระดับของโหนด E คือ 3 และระดับของโหนดคือ ระดับโหนดหลัก + 1 ระดับของโหนดรากคือ 1 ;
• path : ช่องสัญญาณจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง เช่น เส้นทางของ A→H คือ ADH ;
• ความยาวเส้นทาง : ระยะห่างจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง เช่น เส้นทางของ A→H นั่นคือ 3

โครงสร้างต้นไม้ใน JavaScript

อาจกล่าวได้ว่าเป็นโครงสร้างข้อมูลที่พบบ่อยที่สุดในส่วนหน้า เช่น แผนผัง DOM, การเลือกแบบเรียงซ้อน, ส่วนประกอบของต้นไม้ ฯลฯ

JavaScript ไม่มีโครงสร้างข้อมูลแบบต้นไม้ แต่เราสามารถใช้ได้ object และ Array เพื่อจำลอง tree

เช่นโค้ดต่อไปนี้:

const tree = {
  ค่า: 'A',
  เด็ก: [
    -
      ค่า: 'B',
      เด็ก: [
        { ค่า: 'E' ลูก: null }
        { ค่า: 'F' ลูก: null }
      -
    -
    -
      ค่า: 'C',
      เด็ก ๆ: [{ ค่า: 'G' เด็ก ๆ: null }],
    -
    -
      ค่า: 'D',
      เด็ก: [
        { ค่า: 'H' ลูก: null },
        { ค่า: 'ฉัน' ลูก: null }
      -
    -
  -
}

ข้อดีของอัลกอริธึมการแวะผ่านแนวกว้างก่อนและเชิงลึก อั

ลก

อริธึมการแวะผ่านความลึกก่อนที่เรียกว่าคือการค้นหากิ่งก้านของต้นไม้ให้ลึกที่สุด ลำดับการแวะผ่านมีดังนี้:

แนวคิดการใช้งานมีดังนี้

• เยี่ยมชมโหนดรูท
• ดำเนินการสำรวจเชิงลึกครั้งแรก (การเรียกซ้ำ) ของ children ของโหนดรูท

รหัสการใช้งานมีดังนี้:

function dfs(root) {
  console.log(root.value)
  root.children && root.children.forEach(dfs) // สอดคล้องกับสิ่งต่อไปนี้ // if (root.children) {
  // root.children.forEach(เด็ก => {
  //dfs(ลูก)
  -
  -
-
dfs(tree) //tree นี้เป็น tree ที่กำหนดไว้ก่อนหน้านี้/* ผลลัพธ์ A
บี
อี
เอฟ
ค
ช
ดี
ชม
ฉัน
*/

อย่างที่คุณเห็น ลำดับนั้นสอดคล้องกับรูปภาพ ซึ่งหมายความว่าไม่มีปัญหากับอัลกอริทึมของเรา

ลำดับความสำคัญแบบกว้าง

สิ่งที่เรียกว่าลำดับความสำคัญแบบกว้างคือการเยี่ยมชมโหนดที่อยู่ใกล้กับโหนดรูทมากที่สุดตามลำดับดังนี้:

แนวคิดการใช้งานมีดังนี้:

• สร้างคิว เพิ่มโหนดรูทลงในคิว
• ยกเลิกคิวส่วนหัวของคิวและเข้าถึง
• เพิ่ม children ของส่วนหัวของคิวลงในคิวตามลำดับ
• ทำซ้ำขั้นตอนที่ 2 และ 3 คิวว่างเปล่า

รหัสการใช้งานมีดังนี้:

function bfs(root) {
  // 1. สร้างคิวใหม่และเพิ่มโหนดในคิว const q = [root]
  // 4 ทำซ้ำในขณะที่ (q.length > 0) {
    const node = q.shift() // 2 คิวเฮดถูกแยกออกจากคิว console.log(node.value)
    // มีการเพิ่มลูก 3 คนซึ่งเป็นหัวหน้าทีมในโหนดทีม เด็ก &&
      node.children.forEach (เด็ก => {
        q.push(ลูก)
      -
  -
-
bfs(ต้นไม้)
/* ผลลัพธ์ ก
บี
ค
ดี
อี
เอฟ
ช
ชม
ฉัน
*/

อย่างที่คุณเห็น ลำดับนั้นสอดคล้องกับรูปภาพ ซึ่งหมายความว่าไม่มีปัญหากับอัลกอริทึมของเรา