Бинарное дерево - это структура данных, в которой каждый узел имеет не более двух дочерних узлов. Ниже приведен пример двоичного дерева. Самый верхний узел - это корневой узел.

Все узлы внизу, к которым не прикреплены дочерние узлы, называются листовыми узлами.

Если двоичное дерево имеет высоту h, то может быть максимум 2⁽ ʰ⁺ ¹⁾-1 узлов. Пусть n будет количеством узлов. Затем:
= ›n = 2⁽ ʰ⁺ ¹⁾-1
=› n + 1 = 2⁽ ʰ⁺ ¹⁾
= ›log₂ (n + 1) = log₂ (2⁽ ʰ⁺ ¹⁾)
=› log₂ (n + 1) = (h + 1) log₂2
= ›log₂ (n + 1) -1 = h или h = log₂ (n + 1) -1
Итак, учитывая n узлов, оптимальная высота h дерева составляет log₂ (n + 1) -1

Корневой узел находится на уровне 0. На каждом уровне может быть максимум 2ˡ узлов, где l - это уровень.

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

А в Go мы можем определить узел таким образом:

type Node struct{
 Data int
 Left *Node
 Right *Node
}

Как мы знаем, struct - это агрегированный тип данных, который содержит значения любого типа данных под одним зонтиком. Эти значения известны как поля.
В нашем примере есть три поля, которые принадлежат структуре Node, а именно Data для хранения целочисленных данных, Left для указания на левый дочерний элемент и Right для указания на правого дочернего элемента.

Моя структура бинарного дерева поиска выглядит более простой. Что-то вроде этого:

type BinSearchTree struct{
 root *Node
}

Узел root указывает на первый или корневой узел двоичного дерева поиска. Давайте посмотрим на логику вставки.

func (t *BinSearchTree) Insert(data int){
  newNode := Node{data, nil, nil}
  if t.root == nil {
    t.root = &newNode
    return
  }
  iter, prev := t.root, t.root
  for iter != nil {
    prev = iter
    if data < iter.Data {
      iter = iter.Left
    } else {
      iter = iter.Right
    }
  }
  if data < prev.Data {
    prev.Left = &newNode
  } else {
    prev.Right = &newNode
  }
}

Первая строка func (t *BinSearchTree) Insert(data int) сообщает нам, что функция Insert связана с struct BinSearchTree. В Go мы называем такие функции методами. (t *BinSearchTree) - это получатель, который сообщает нам, что Insert может вызываться только литералами типа BinSearchTree.

Как вы могли заметить, я не использовал рекурсию для вставки данных в подходящий узел, вместо этого использовал цикл for для поиска позиции, подходящей для вставки узла.

newNode := Node{data, nil, nil} создает новый узел, где newNode.Data - это data, newNode.Left - это nil, а newNode.Right - это nil.

Узел root в начале будет ноль. Таким образом, ссылка на первый узел присваивается root, как показано ниже:

if t.root == nil {
  t.root = &newNode
  return
}

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

iter, prev := t.root, t.root
for iter != nil {
    prev = iter
    if data < iter.Data {
      iter = iter.Left
    } else {
      iter = iter.Right
    }
}

Найдя подходящее место, мы вставляем элемент:

if data < prev.Data {
    prev.Left = &newNode
} else {
    prev.Right = &newNode
}

Какой смысл создавать дерево, если мы не можем его пройти? Дерево двоичного поиска можно перемещать по порядку, по предварительному заказу и по почте.

В обходе по порядку мы переходим к левому дочернему элементу, затем к родительскому и затем к правому дочернему.
В обходе pre-order мы переходим к родительскому узлу, затем к левому дочернему элементу а затем правого дочернего.
В обходе post-order мы переходим к левому дочернему элементу, затем к правому дочернему элементу, а затем к родительскому узлу.

Метод обхода по порядку выглядит примерно так:

func (t *BinSearchTree) InOrder(node *Node){
 if node == nil {
  return
 }
 t.InOrder(node.Left)
 fmt.Println(node.Data)
 t.InOrder(node.Right)
}

Как вы заметили, рекурсивные методы, используемые для обхода двоичного дерева поиска. Полный исходный код можно найти здесь https://gist.github.com/sandeep-sarkar/07e47cdae0c63f14b695370536b434ab

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