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

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

1 отговор

+1 глас
отговорени 2018 май 6 от Павката (3,450 точки)
редактиран 2018 май 6 от Павката
Здравей,

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

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

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

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

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

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

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