إعادة بناء الأشجار من "بصمة"
-
26-09-2019 - |
سؤال
لقد قمت بإجراء 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)}...}
من المحتمل أن يكون تمثيل العقد الفعلية الموجودة في كل مستوى في الشجرة صالحًا ، ولكن هل يمكن أن يتم ذلك بشكل أكثر كفاءة؟
المحلول
أود استخدام قائمة بالقوائم ، حيث ينص كل عنصر في القائمة على عدد الأطفال الذين لديك:
[[2][1,2][0,0,0]]
هي شجرة ذات عقدتين على المستوى الأول والطفل الأيسر لديه عقدة طفل واحد ، والعقدة الطفل اليمنى لديها 2 من تلقاء نفسها.
قم بتشغيل هذا الإخراج من خلال خوارزمية ضغط بدون فقدان من اختيارك.
يمكنك أيضًا استخدام اجتياز الشجرة ، أو أي نوع آخر من الأنواع الأخرى. كل ما هو أسهل بالنسبة لك لإعادة البناء من.