Сделать двоичное дерево наклоненным влево

Итак, у меня есть реализация двоичного дерева, которая выглядит так

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

Я понимаю концепцию вращения дерева, но я действительно не знаю, как использовать их (или любой другой алгоритм в этом отношении), чтобы сделать дерево полностью наклоненным влево, как на диаграмме выше.

Если бы кто-нибудь мог указать мне на алгоритм или другой ресурс для этого, я был бы очень признателен

0 ответов

Другие вопросы по тегам