Помощ курсова задачка C++

0 гласа
24 прегледа
попитан 3 май в PHP от pepi9846 (140 точки)
Да се състави функция за преобразуване на даден едносвързан списък в балансирано двоично дърво.Благодаря предварително

1 отговор

0 гласа
отговорени 6 май от Павката (2,500 точки)
редактиран 6 май от Павката
Здравей,

  Първо ако искаш да доуточним условието:

1. Списъка от какъв тип елементи е съставен? (търси ли се решение с темплейти, които имплементират операция за сравнение или може да приемем, че е достатъчно да се напише за целочислени)

2. Има ли ограничение за броя на елементите? (по един начин можем да подходим за 5-10 елемента, по друг за 5-10 милиона или повече)

3. Има ли ограничение за комплекността на алгоритъма О(n) достатъчно ли е?

  Ако нямаш много време за тези детаили или не са ти от голямо значение ти предлагам следния подход :

1. Сортираш списъка

2. Прегледай едно решение тук за балансирано дърво от сортиран списък:
https://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/
...