أتقن خوارزمية العمق الأول لبنية شجرة جافا سكريبت في مقال واحد

ما هي الشجرة؟

في الحياة الواقعية، أعتقد أن الجميع على دراية بالأشجار، سواء كانت أشجار الصفصاف أو الحور أو الخوخ، ويمكن القول أنه يمكن رؤية الأشجار في كل مكان في حياتنا، فالأشجار مجرد فكرة نموذج الهيكل الهرمي

كما هو موضح أدناه:

هناك العديد من التطبيقات للهيكل الشجري، على سبيل المثال، يمكن تمثيل الهيكل التنظيمي للشركة بواسطة شجرة، كما هو موضح أدناه:

بالإضافة إلى الهياكل التنظيمية، يمكن تمثيل أشياء مثل أشجار العائلة والمقاطعات والمدن وما إلى ذلك باستخدام الهياكل الشجرية.

مصطلحات الشجرة

هناك مصطلحات عديدة للأشجار، كما هو موضح أدناه:

• الشجرة : مجموعة محدودة من العقد n (n≥0)، عندما تكون n=0 ، تسمى شجرة فارغة؛
• عدد الأشجار الفرعية للعقدة ، على سبيل المثال، درجة العقدة B هي 2 درجة العقدة A هي 3؛
درجة الشجرة
• : الدرجة
• القصوى بين جميع عقد الشجرة، على سبيل المثال، في الشكل أعلاه، درجة الشجرة هي 3؛
• ، وتسمى أيضًا العقدة الورقية ؛
• العقدة الفرعية : كما هو موضح في الشكل أعلاه؛
• العقدة الشقيقة : كما هو موضح في الصورة أعلاه؛
• العقدة الجذرية : كما هو موضح في الصورة أعلاه
• : أقصى مستوى بين جميع العقد في الشجرة ، على سبيل المثال، عمق الشجرة في الصورة أعلاه هو 3؛
• مستوى العقدة : على سبيل المثال، مستوى العقدة E هو 3، ومستوى العقدة هو مستوى العقدة الأصلية + 1، ومستوى العقدة الجذرية هو 1. المسار
• : القناة من عقدة إلى عقدة أخرى ، على سبيل المثال، مسار A→H هو ADH ؛
• طول المسار : المسافة من عقدة إلى عقدة أخرى ، مثل مسار A→H وهذا هو 3.

بنية الشجرة في JavaScript

هي إحدى هياكل البيانات الأكثر شيوعًا في الواجهة الأمامية، مثل شجرة DOM والاختيار المتتالي ومكونات الشجرة وما إلى ذلك؛

لا توفر JavaScript بنية بيانات الشجرة، ولكن يمكننا استخدامها كائنات ومصفوفة لمحاكاة شجرة،

مثل الكود التالي:

const Tree = {
  القيمة: "أ"،
  أطفال: [
    {
      القيمة: "ب"،
      أطفال: [
        {القيمة: 'E'، الأطفال: فارغة }،
        {القيمة: 'F'، الأطفال: فارغة }،
      ]،
    },
    {
      القيمة: "ج"،
      الأطفال: [{ القيمة: 'G'، الأطفال: فارغة }]،
    },
    {
      القيمة: "د"،
      أطفال: [
        {القيمة: 'H'، الأطفال: فارغة }،
        {القيمة: 'أنا'، الأطفال: فارغة }،
      ]،
    },
  ]،
}

مزايا خوارزميات اجتياز العمق أولاً والعمق

أولاً

ما يسمى بخوارزمية اجتياز العمق أولاً هو البحث في فروع الشجرة بعمق قدر الإمكان. ترتيب اجتيازها هو كما يلي:

فكرة التنفيذ هي كما يلي:

• قم بزيارة العقدة الجذرية،
• واستمر في اجتياز العمق الأول (العودة) children العقدة الجذرية،

ويكون رمز التنفيذ كما يلي:

function dfs(root) {
  console.log(root.value)
  root.children && root.children.forEach(dfs) // متوافق مع ما يلي // if (root.children) {
  // root.children.forEach(child => {
  //دفس (طفل)
  // })
  // }
}
dfs(tree) // هذه الشجرة هي الشجرة المحددة مسبقًا/* النتيجة أ
ب
ه
ف
ج
ز
د
ح
أنا
*/

كما ترون، الترتيب متوافق مع الصورة، مما يعني عدم وجود مشكلة في الخوارزمية لدينا.

أولوية العرض

ما يسمى بأولوية العرض هي زيارة العقد الأقرب إلى العقدة الجذرية بالترتيب كما يلي:

فكرة التنفيذ هي كما يلي:

• إنشاء قائمة انتظار، وإضافة العقدة الجذرية إلى قائمة الانتظار؛
• وحذف
• رأس قائمة الانتظار والوصول إليها؛
• وإضافة children لرأس قائمة الانتظار إلى قائمة الانتظار بالتسلسل؛
• قائمة الانتظار فارغة.

رمز التنفيذ كما يلي:

function bfs(root) {
  // 1. أنشئ قائمة انتظار جديدة وأضف العقد إلى قائمة الانتظار const q = [root]
  // 4 كرر بينما (q.length > 0) {
    عقدة const = q.shift() // تم وضع رأس قائمة الانتظار في قائمة الانتظار console.log(node.value)
    // تمت إضافة 3 أطفال، رئيس الفريق، إلى الفريق العقدة. الأطفال &&
      العقدة. الأطفال.forEach (الطفل => {
        ف.ادفع (الطفل)
      })
  }
}
صديقك المفضل (شجرة)
/* النتيجة أ
ب
ج
د
ه
ف
ز
ح
أنا
*/

كما ترون، الترتيب متوافق مع الصورة، مما يعني عدم وجود مشكلة في الخوارزمية لدينا.