Сделать двоичное дерево наклоненным влево
Итак, у меня есть реализация двоичного дерева, которая выглядит так
struct node {
struct node *left;
struct node *right;
};
(фактическая реализация немного сложнее, поскольку там хранятся дополнительные данные, поскольку это для упрощения логической алгебры, но с целью донести свою точку зрения я буду упрощать)
в основном я получаю дерево, и мне нужно преобразовать его так, чтобы оно полностью оставалось наклонным
например
a
/ \
/ \
/ \
/ \
/ \
b \
/ \ \
/ \ \
/ \ \
c \ d
/ \ \ / \
e \ f g \
/ \ \ / \ / \ \
h i j k l m n o
должен стать
g
/ \
d \
/ \ \
a \ \
/ \ \ \
f \ \ \
/ \ \ \ \
b \ \ \ \
/ \ \ \ \ \
c \ \ \ \ \
/ \ \ \ \ \ \
e \ \ \ \ \ \
/ \ \ \ \ \ \ \
h i j k l m n o
Я понимаю концепцию вращения дерева, но я действительно не знаю, как использовать их (или любой другой алгоритм в этом отношении), чтобы сделать дерево полностью наклоненным влево, как на диаграмме выше.
Если бы кто-нибудь мог указать мне на алгоритм или другой ресурс для этого, я был бы очень признателен