Что такое двоичное дерево поиска?

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

Хватит говорить, приступим к кодированию 😁

Теперь давайте добавим метод push к прототипу BinarySearchTree, чтобы добавить к нему узлы.

Самая распространенная операция, выполняемая над двоичным деревом поиска, - это поиск и проверка того, существует ли данный узел или нет.

Теперь рассмотрим различные способы обхода двоичного дерева поиска.

inorder (узел)

  1. Пройдите по левому поддереву, т.е. выполните упорядочение по левому поддереву
  2. Посетите корень
  3. Пройдите по правому поддереву, т.е. выполните упорядочение по правому поддереву

предварительный заказ (узел)

  1. Посетите корень
  2. Пройдите по левому поддереву, то есть выполните предварительный заказ на левом поддереве
  3. Пройдите по правому поддереву, то есть выполните предварительный заказ на правом поддереве

postorder (узел)

  1. Пройдите по левому поддереву, т.е. выполните поступорядочение на левом поддереве
  2. Пройдите по правому поддереву, т.е. выполните поступорядочение по правому поддереву
  3. Посетите корень

Обход дерева порядка без рекурсии.

Примечание. Обход дерева порядка следования в двоичном дереве поиска гарантирует отсортированный вывод.

Что такое n-ary Tree?

n-арное дерево - это корневое дерево, в котором каждый узел имеет не более n дочерних элементов. Бинарное дерево - это частный случай, когда n = 2, а троичное дерево - это еще один случай, когда n = 3, что ограничивает количество его дочерних элементов тремя.

Теперь давайте посмотрим на обход этого дерева до и после завершения.

До сих пор мы видели обходы дерева при поиске в глубину (dfs), теперь мы увидим, как выполнить обход дерева при поиске в ширину (bfs).



Разница между BFS и DFS - GeeksforGeeks
означает поиск в ширину - это метод на основе вершин для поиска кратчайшего пути на графике. Он использует данные очереди… www.geeksforgeeks.org



По умолчанию javascript не предоставляет никакой структуры данных очереди, вот как мы можем реализовать это в javascript.

Надеюсь, вам понравилась эта статья. Пожалуйста, хлопните в ладоши или шесть, если вам это понравилось.

Удачного обучения !! Приятного чтения !! 😃 😄 😀