إعادة بناء الأشجار من "بصمة"

Question

لقد قمت بإجراء SO و Google Research ، ولم أجد أي شخص تعامل مع هذا من قبل ، أو على الأقل ، أي شخص كتب عنه.

سؤالي هو ، بالنظر إلى شجرة "عالمية" من الارتفاع التعسفي ، مع كل عقدة قادرة على الحصول على عدد تعسفي من الفروع ، هل هناك وسيلة لتصبع "أصابع" فريدة (وكفاءة) الجذر ، بحيث بالنظر إلى الشجرة العالمية وبصمة الشجرة ، يمكنني إعادة بناء الشجرة الأصلية؟

على سبيل المثال ، لدي شجرة "عالمية" (سامح الرسوم التوضيحية الفقيرة) ، تمثل عالم الإمكانيات:

                Root
        /  /  /  |  \  \ ... \
       O  O  O   O   O  O     O  (Level 1)
      /|\/|\...................\ (Level 2)

إلخ.

لدي أيضًا شجرة أ ، شجرة فرعية متجذرة من كوني

        Root
      / /|\ \
     O O O O O
    /

إلخ.

هل هناك طريقة "لبصمة" الشجرة ، بحيث بالنظر إلى تلك البصمة ، والشجرة العالمية ، يمكنني إعادة بناء A؟

أفكر في شيء ما على غرار تجزئة ، أو ضغط ، أو ربما بناء وظيفي/تعريفي؟ تحليل Big-O (في الوقت أو الفضاء) هو زائد.

باعتبارها من أجل الاستقبال ، تعبير متداخل مثل: {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...} من المحتمل أن يكون تمثيل العقد الفعلية الموجودة في كل مستوى في الشجرة صالحًا ، ولكن هل يمكن أن يتم ذلك بشكل أكثر كفاءة؟

Answer 1

أود استخدام قائمة بالقوائم ، حيث ينص كل عنصر في القائمة على عدد الأطفال الذين لديك:

[[2][1,2][0,0,0]]

هي شجرة ذات عقدتين على المستوى الأول والطفل الأيسر لديه عقدة طفل واحد ، والعقدة الطفل اليمنى لديها 2 من تلقاء نفسها.

قم بتشغيل هذا الإخراج من خلال خوارزمية ضغط بدون فقدان من اختيارك.

يمكنك أيضًا استخدام اجتياز الشجرة ، أو أي نوع آخر من الأنواع الأخرى. كل ما هو أسهل بالنسبة لك لإعادة البناء من.