بناء شجرة ثنائية بحيث يجب أن تعطي اجتياز الترتيب بعد النتيجة الفرز

Question

أعلم أن اجتياز الدخول المباشر (زيارة اليسار، قم بزيارة الجذر، وزيارة اليمين) على شجرة البحث الثنائية تعطيني نتيجة مرتبة. لكنني بحاجة إلى إجراء اجتياز آخر ترتيب (زيارة اليسار، قم بزيارة الحق، وزيارة الجذر) على شجرة ثنائية والنتيجة يجب أن تعطيني القيم الفرز.

من أجل تحقيق ذلك، كيف يمكنني بناء شجرة ثنائية؟

Answer 1

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

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

Answer 2

تحتاج إلى ضمان ما يلي في كل عقدة من الشجرة:

• يجب أن تكون القيمة في العقدة أكبر من جميع القيم الموجودة في الجزء السفلي الأيسر والإيمان الفرعي الصحيح.
• يجب أن تكون القيم في الشجرة الفرعية اليسرى أقل من القيم في الشجرة الفرعية الصحيحة.

Answer 3

هذا الروتين الفرعي هو الإدراج في الشجرة حيث هيكل الأشجار

struct tree

{

int data;
tree * left;
tree *right;

tree(int n)  // constructor 

{
       data = n;
       left = right = NULL;
    }
};

الخوارزمية هي:
1. إذا كانت الشجرة فارغة إدراج عقدة جديدة.
2. إذا كانت بيانات العقدة الجديدة أكبر من بيانات العقدة الجذر تجعل العقدة الجديدة
جذر الشجرة.
3. إدراج عقدة جديدة في الجزء السفلي الأيسر من الشجرة.

tree * insert(tree *root,int n)

{

if(root == NULL)
{

    root = new tree(n);

    return root;
}
else
{

    if(n > root -> data)
    {
        tree * t = new tree(n);

        t -> left = root;

        return t;
    }

    else


    {

        root -> left = insert(root -> left,n);

        return root;
    }
    }
}

Answer 4

ال إجابة مقبولة حاليا يعطي خوارزمية جيدة على الانترنت. حل أبسط إلى حد ما --- وهو ليس عبر الإنترنت وهناك الغش ربما هو تخزين قائمة مرتبطة مرتبة في المؤشرات الأصل.

بمعنى آخر: فرز البيانات؛ ضع أكبر عنصر في الجذر، وجعل واحدة من السكتات الحرارية فارغة وإعادة تشديد شجرة مصنوعة من العناصر التي تم فرزها من أجل المتبقية من العناصر N-1 المتبقية في الشجرة الأخرى.

ستتمتع الشجرة الارتفاع N، ورقة واحدة هي رأس القائمة والجذر هو عنصر الذيل الأكثر. إذا تمشي عبر الشجرة من ورقة إلى الجذر، فسوف تشكل العناصر تسلسل متزايد، وسيتوصل هذا المسار إلى اجتياز postorder.

Answer 5

حذف

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

علي سبيل المثال:

    7                                                            6
   / \                                                          / \
  3   6             =========DELETING 7 ============>          4   5
 / \ / \                                                      /    
1  2 4  5                                                    3
                                                            / \
                                                           1   2

Answer 6

بادئ ذي بدء، لاحظ أن أفضل تعقيد لحل هذه المشكلة هو O (NLGON) على خلاف ذلك، وإلا سيكون من الممكن فرز الصفيف في أقل من O (NLGON) عن طريق إنشاء هذه الشجرة والقيام بالمرور (وهو أمر مستحيل). أيضا، من المفيد خلق شجرة متوازنة بحيث تكون العمليات التي قد تفعلها على الشجرة في وقت لاحق ستكون سريعة. على الرغم من أن الإجابة المقبولة تعمل لها (n ^ 2)، فإن الشجرة غير متوازنة.

خوارزمية:

1) فرز الصفيف.

2) إنشاء شجرة متوازنة فارغة من حجم n.

3) املأ هذه الشجرة بقيم من الصفيف الفرز باستخدام postorder.

التعقيد: O (nlogn)