Binary tree

Информация

Бинарное дерево (Binary Tree) - это дерево, в котором у каждого узла не более двух дочерних элементов, обычно называемых левым и правым дочерним элементами. В бинарном дереве каждый узел может иметь от 0 до 2 дочерних узлов.

Бинарное дерево поиска (Binary Search Tree) - это бинарное дерево, в котором для всех узлов, лежащих в левом поддереве, значения этих узлов меньше, чем значение корня, а для всех узлов, лежащих в правом поддереве, значения этих узлов больше, чем значение корня.

Отличие от BST

Отличия:

1. В бинарном дереве поиска значения узлов упорядочены, тогда как в обычном бинарном дереве этого не происходит.
2. В бинарном дереве поиска операции поиска, вставки и удаления имеют логарифмическую сложность, тогда как в обычном бинарном дереве эти операции могут иметь линейную сложность.
3. Бинарное дерево поиска может быть несбалансированным, тогда как бинарное дерево обычно является сбалансированным.

Порядок обхода

В бинарном дереве существует три основных метода обхода:

1. Inorder (синтаксический, инфиксный): Вы посещаете левое поддерево, потом корень, и затем правое поддерево.
2. Preorder (префиксный): Вы посещаете корень, затем левое поддерево, и затем правое поддерево.
3. Postorder (постфиксный): Вы посещаете левое поддерево, затем правое поддерево, и затем корень.

Если мы используем алгоритм DFS(Depth-First Search) для обхода дерева, то может быть три варианта DFS:

1. Preorder DFS (Root, Left, Right)
2. Inorder DFS (Left, Root, Right)
3. Postorder DFS (Left, Right, Root)