أقصر الجذر إلى ورقة الطريق

Question

ما هي أسهل طريقة ، ويفضل استخدام العودية ، أن تجد أقصر الجذر إلى ورقة الطريق في BST (شجرة البحث الثنائية).جافا مفضلة, شبة الكود حسنا.

وذلك بفضل!

Answer 1

الوصف العام:

استخدام بحث اتساع الأول (BFS) بدلا من البحث المتعمق الأول (DFS).العثور على العقدة الأولى مع الأطفال.

استخدام DFS قد تحصل على الحظ على بعض المدخلات الأشجار (ولكن ليس هناك طريقة لمعرفة هل كنت محظوظا إذا كنت لا تزال بحاجة إلى البحث الشجرة كلها) ، ولكن باستخدام BFS طريقة أسرع بكثير و يمكنك أن تجد حلا دون لمس جميع العقد.

العثور على الجذر إلى ورقة الطريق, قد تتبع الأولى وجدت بتر عقدة كل في طريق العودة إلى الجذر باستخدام الوالد المرجعية.إذا كان لديك أي من الوالدين الإشارة المخزنة في كل عقدة, يمكنك تتبع الأم العقد كما كنت recurse أسفل.إذا كان لديك قائمة في ترتيب عكسي يمكنك أن تضغط على كومة ثم البوب قبالة.

الزائفة رمز:

المشكلة بسيط جدا ؛ هنا هو الزائفة رمز للعثور على أصغر طول:

1. وضع العقدة الجذر على قائمة الانتظار.

كرر أثناء طابور ليست فارغة ، وليس نتيجة وجد:

2. سحب عقدة من بداية طابور تحقق مما إذا كان لديها أطفال.إذا كان لديه أي الأطفال كنت تتم يمكنك العثور على أقصر طريق.
3. وإلا دفع جميع الأطفال (اليسار واليمين) على قائمة الانتظار.

إيجاد جميع أقصر مسارات:

للعثور على جميع المسارات الأقصر يمكنك تخزين عمق العقدة جنبا إلى جنب مع عقدة داخل الطابور.ثم سوف تستمر الخوارزمية على كافة العقد في طابور مع نفس العمق.

البديل:

إذا بدلا من ذلك كنت قد قررت استخدام DFS, سيكون لديك للبحث في الشجرة بأكملها إلى العثور على أقصر طريق.ولكن هذا يمكن أن يكون الأمثل من خلال الحفاظ على قيمة أقصر حتى الآن ، فقط التحقق من عمق المستقبل العقد حتى تجد الجديد أقصر ، أو حتى تصل إلى أقصر حتى الآن.BFS حل أفضل بكثير على الرغم من.

Answer 2

هذا هو في C++, ولكن هذا هو في غاية البساطة يمكنك التحويل بسهولة.مجرد تغيير الحد الأدنى إلى الحد الأقصى للحصول على أقصى عمق الشجرة.

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

فقط لشرح ما يفعله هذا ، فمن عد من ورقة عقدة (يعود 0 عندما يجد ورقة) و التهم تصل إلى الجذر.تفعل هذا من ناحية اليسار واليمين الجانبين من شجرة وأخذ الدنيا تعطيك أقصر الطرق.

Answer 3

اتساع البحث الأول هو بالضبط الأمثل من حيث عدد الرؤوس التي تمت زيارتها.لديك لزيارة كل واحدة من القمم كنت في زيارة في اتساع البحث الأول فقط من أجل إثبات أن لديك أقرب ورقة!

ومع ذلك, إذا كان لديك الولاية إلى استخدام العودية ، مايك طومسون نهج تقريبا الحق واحد و هو أبسط قليلا.

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf 

Answer 4

الباحث ثابت findCheapestPathSimple(TreeNode الجذر){

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}