Как преобразовать отсортированный список в двоичное дерево

отсортированный связанный список используется для построения двоичного дерева от листьев до корня. Идея состоит в том, чтобы вставить узлы в двоичное дерево в том же порядке, в каком они появляются в связанном списке, чтобы дерево можно было построить с временной сложностью O ( n ) O (n ) O (n).

Method

Количество узлов в связанном списке подсчитывается и устанавливается равным к п. Сначала средний узел устанавливается как корневой (всегда). Затем левое поддерево строится рекурсивно с использованием левых n/2 узлов и соединяется с корнем в конце. Правое поддерево строится аналогичным образом и соединяется с корнем.

При построении BST мы продолжаем перемещать указатель заголовка списка на следующий узел, чтобы у нас был соответствующий указатель при каждом рекурсивном вызове.

Пример

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

Связанный список:

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 1 node_15647449794512 node_1564744979451 -> node_1-> node_1564744979451 node_1564744912919 3 node_1564744912919 -> node_1564744979451-> node_1564744912919 node_1564744945966 4 node_1564744945966 -> node_1564744912919-> node_1564744945966 node_1564744901302 5 node_1564744901302 -> node_1564744945966-> node_1564744901302 node_1564745552214 6 node_1564745552214 -> node_1564744901302-> node_1564745552214 node_1564745474095 7 node_1564745474095 -> node_1564745552214-> node_1564745474095

Преобразованный двоичный дерево:

xml version = «1.0» encoding = «UTF-8» standalone = «no»?> % 0 node_1 4 node_15647454547962 node_1564745454796 -> node_1-> node_1564745454796 node_1564745453945 6 node_1564745453945 -> node_1-> node_1564745453945 node_1564745513249 1 node_1564745513249 -> node_1564745454796-> node_1564745513249 node_1564745544123 3 node_15647455441 23 -> node_1564745454796-> node_1564745544123 node_1564745511471 5 node_1564745511471 -> node_1564745453945-> node_1564745511471 node_1564745469108 7 node_1564745469108 -> node_1564745453945-> node_1564745469108

Реализация

Код ниже реализует метод выше.

  • C++
  • C++
  • C++
  • Java
  • Java
 #include  с использованием пространства имен std; /* Узел списка ссылок */class listNode {public: int data;  listNode * следующий;  }; /* Узел двоичного дерева */class treeNode {public: int data;  treeNode * left;  treeNode * right;  };  treeNode * newNode (данные типа int);  int countNodesOfList (listNode * голова);  treeNode * sortedListToBTrecur (listNode ** head_ref, int n); /* Эта функция подсчитывает количество узлов в Связанном списке, а затем вызывает */treeNode * sortedListToBST (listNode * head) {/* Подсчитывает количество узлов в Связанном списке */int n = countNodesOfList (head);  вернуть sortedListToBTrecur (& head, n);  }/* Основная функция, которая строит сбалансированный BT и возвращает его корень.  head_ref -> Указатель на указатель на головной узел связанного списка n -> Нет. узлов в связанном списке */treeNode * sortedListToBTrecur (listNode ** head_ref, int n) {/* Базовый случай */if (n  data);  корень-> слева = слева; /* Изменить указатель заголовка связанного списка для родительских рекурсивных вызовов */* head_ref = (* head_ref) -> next; /* Рекурсивно конструируем правое поддерево и связываем его с корнем Количество узлов в правом поддереве - это общее количество узлов - узлов в левом поддереве - 1 (для корня), что равно nn/2-1 */root-> right = sortedListToBTrecur (head_ref  , n - n/2 - 1);  вернуть корень;  }/* Служебная функция, которая возвращает количество узлов в данном связанном списке */int countNodesOfList (listNode * head) {int count = 0;  listNode * temp = head;  в то время как (темп) {темп = темп-> далее;  count ++;  } счетчик возврата;  }/* Функция для вставки узла в начало связанного списка */void push (listNode ** head_ref, int new_data) {/* выделить узел */listNode * new_node = new listNode (); /* вставляем данные */new_node-> data = new_data; /* свяжем старый список с новым узлом */new_node-> next = (* head_ref); /* перемещаем голову, чтобы указать на новый узел */(* head_ref) = new_node;  }/* Функция для печати узлов в данном связанном списке */void printList (listNode * node) {while (node! = NULL) {cout  data  следующий;  }}/* Вспомогательная функция, которая выделяет новый узел с заданными данными и NULL левым и правым указателями.  */treeNode * newNode (int data) {treeNode * node = new treeNode ();  узел-> данные = данные;  узел-> слева = NULL;  узел-> право = NULL;  возвратный узел;  }/* Служебная функция для печати обхода перед предварительным заказом BT */void preOrder (treeNode * node) {if (node ​​== NULL) return;  cout  данные  слева);  preOrder (узел-> справа);  }/* Код драйвера */int main () {/* Начать с пустого списка */listNode * head = NULL; /* Давайте создадим отсортированный связанный список для проверки функций Созданный связанный список будет 1-> 2-> 3-> 4-> 5-> 6-> 7 */push (& head, 7);  push (& head, 6);  push (& head, 5);  push (& head, 4);  push (& head, 3);  push (& head, 2);  push (& head, 1);  cout 

Оцените статью
nanomode.ru
Добавить комментарий