Юра
c++. Как восстановить бинарное дерево, зная инордер и постордер (инфикс и постфикс)?
Замучился уже . Вся работа готова, а эта функция ну никак не идет. Подскажите пожалуйста
Замучился уже . Вся работа готова, а эта функция ну никак не идет. Подскажите пожалуйста
Элементы уникальные? Если нет - то никак (например, постордер и инордер 1,1,1 может означать как корень с двумя ветвями, так и цепочку, где из корня выходит одна ветвь) . Если да - то:
- берем у постордера последний элемент (корень)
- находим его в инордере;
- делим инордер на левую и правую части относительно корня;
- делим постордер пополам (по принадлежности к половинкам инордере) ;
- вызываем построение рекурсивно для левой и правой ветвей.