Сегодня я узнал о рекурсивных структурах данных, двоичных деревьях, о том, почему они полезны, как мы можем их построить и как обходить их в глубину и в ширину как рекурсивным, так и нерекурсивным образом.

Что и почему в деревьях

Прочтите статью ниже, в которой объясняются важные аспекты двоичного дерева. Моя обложка вдохновлена ​​этим постом :)



Как не попасть в тупик деревьями
Как только в вашей голове гаснет лампочка со структурой данных, становится действительно трудно не видеть структуры данных каждый раз… medium.com



Важные понятия, которые вы должны знать:

  • Если в дереве есть N узлов, у него будет ровно N-1 ребер.
  • Высота узла - это количество ребер между узлом и самым дальним листом, достижимым от узла. Высота листового узла равна 0.
  • Высота дерева равна высоте корня.
  • Глубина узла - это количество ребер на пути от корня до узла. Глубина корневого узла равна 0.

Как реализовать двоичные деревья:

  • Сохраните их в широком порядке в массиве, где -1 будет представлять нулевой узел. Но у этого представления есть недостаток, оно тратит много памяти в случае несбалансированного дерева.
  • В большинстве случаев деревья реализованы как узлы, связывающиеся друг с другом, как в связанном списке.

ПУТЕШЕСТВИЯ ПО ДЕРЕВАМ

Обход в глубину

ПРЕДВАРИТЕЛЬНЫЙ ПУТЕШЕСТВИЕ: УЗЛ → ВЛЕВО → ВПРАВО.

  • Рекурсивный
Algorithm:
  1. Check if root is null and end.
  2.Visit Node
  3.Visit left-subtree.
  4.Visit right sub-tree.
Run-time: O(n)
Space (stack of function calls considered): O(n)
  • Итеративный
Algorithm:
  1. Check if root is null and end.
  2.Initialize a Stack of nodes.
  3.Loop until stack is not empty
  4.Pop element from top of stack and visit it.
  5.Push right and then left child of node if they are not empty.
Run-time: O(n)
Space: O(n)

ПОСЛЕ ЗАКАЗА: ВЛЕВО → ВПРАВО → УЗЕЛ

  • Рекурсивный
Algorithm:
  1. Check if root is null and end.
  2.Visit left-subtree.
  3.Visit right sub-tree.
  4.Visit Node.
Run-time: O(n)
Space (stack of function calls considered): O(n)
  • Итеративный
I will update it Later i could not implement it for now.

В ПОРЯДКЕ ПУТЕШЕСТВИЯ: ВЛЕВО → УЗЕЛ → ВПРАВО

  • Рекурсивный
Algorithm:
  1. Check if root is null and end.
  2.Visit left-subtree.
  3.Visit Node.
  4.Visit right sub-tree.
Run-time: O(n)
Space (stack of function calls considered): O(n)
  • Итеративный
Algorithm:
  1. Check if root is null and end.
  2. Initialize a Stack of nodes.
  3. Initialze a temp variable to keep reference of current node.
  4. Loop.
  5. If temp is not null ,push temp to stack and make temp point to   its left child.
  6.Else, if stack is not empty pop the element, visit it and make temp point to right child of popped element. Else if stack is empty break.
Run-time: O(n)
Space: O(n)

Обход в ширину

Algorithm:
  1. Check if root is null and end.
  2.Initialize a Queue of nodes.
  3.Loop until queue is empty
  4.Dequeue element from head of queue and visit it.
  5.Enqueue left and right child of node if they are not empty 
Run-time: O(n)
Space: O(n)

Источники



Обходы по дереву (Inorder, Preorder и Postorder) - GeeksforGeeks
В отличие от линейных структур данных (массив, связанный список, очереди, стеки и т. Д.), Которые имеют только один логический способ обхода … www.geeksforgeeks.org





CS 61B: структуры данных - Шевчук - Калифорнийский университет в Беркли
Проф. Джонатан Шевчук [email protected] (Но задавайте большинство вопросов в дискуссионной группе CS 61B Piazza и отправляйте больше всего… people.eecs.berkeley.edu



Заключительные слова

Я реализую полный код для дерева двоичного поиска в День 6, если вы сделаете какое-либо предложение, исправление или запрос, вы можете прокомментировать.

Github: https://github.com/rajat13

LinkedIn: https://www.linkedin.com/in/rajat-goyal-7b55ab104/