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

Question

لدي نظام ويب يحتوي على قائمة كلاسيكية بين الوالدين والأبناء محفوظة في قاعدة بيانات، مع معرف الحقول باعتباره PK، وparent_id للإشارة إلى القائمة الخاصة.(نعم، أعلم أن هذا لا يتسع نطاقه جيدًا، لكن هذا موضوع آخر).

لذلك بالنسبة لهذه السجلات (أزواج id-parent_id):

0-7 0-4 4-9 4-14 4-16 9-6

لدي هذه الشجرة:

0
├ 7
└ 4
  ├ 9
  | └ 6     
  ├ 14
  └ 16

أحتاج إلى إخفاء عقدة عليا، لذا يجب أن أقوم بإعداد قائمة بجميع العناصر الفرعية لتلك العقدة المعينة، أي.لـ 4، سيكونون (9، 6، 14، 16).النظام لا يهم.

أنا مرتبك...هل يتناسب هذا مع مشاكل الشجرة الكلاسيكية؟أم أنها رسم بياني واحد؟

كيف يمكنني إنشاء هذه البنية وحل هذه المشكلة باستخدام PHP؟

Answer 1

هذه هي الفرصة المثالية لاستخدام العودية!

كود مزيف:

nodeList = {}
enumerateNodes(rootNode, nodeList);

function enumerateNodes(node, nodeList) {
   nodeList += node;
   foreach ( childnode in node.children ) {
       enumerateNodes(childnode, nodeList);
   }
}

يحرر:لم ألاحظ أن شجرتك موجودة بتنسيق القائمة المجاورة.من المحتمل أن أقوم ببناء ذلك في بنية بيانات شجرة فعلية قبل أن أبدأ العمل معها.ما عليك سوى تكرار جميع الأزواج (إنشاء العقد في المرة الأولى التي تراها فيها) وربطها.أنا يفكر يفترض أن تكون سهلة...

Answer 2

من الصعب جدًا التعامل مع نماذج القائمة المجاورة.الشركة التي أعمل معها الآن تستخدمها في التسلسلات الهرمية، وهذا يسبب صداعًا كبيرًا.لقد استخدمت بنجاح نماذج مجموعة Celko المتداخلة لأصحاب العمل السابقين وهي تعمل بشكل رائع لإنشاء وصيانة واستخدام التسلسلات الهرمية (الأشجار).

وجدت هذا الرابط الذي يصفهم: http://www.intelligententerprise.com/001020/celko.jhtml

لكنني أوصي أيضًا بكتاب "SQL for Smarties:برمجة SQL المتقدمة" كتبها جو سيلكو ويغطي مجموعات متداخلة.

SQL لجو سيلكو لـ Smarties:برمجة SQL المتقدمة

أشجار جو سيلكو والتسلسلات الهرمية في SQL لـ Smarties

Answer 3

هذه مشكلة الرسم البياني.الدفع BFS (بحث أولي واسع النطاق) و DFS (بحث العمق الأول)..يمكنك البحث عن هذه المصطلحات على Google والعثور على مئات التطبيقات على الويب.

Answer 4

هذا أمر تافه مع تطبيق مجموعة متداخلة.انظر هنا لمزيد من التفاصيل:

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

وإلا فاكتب شيئا مثل هذا:

def get_subtree(node)
  if children.size > 0
    return children.collect { |n| get_subtree(n) }
  else
    return node
  end
end