188
правок
Изменения
м
Корректность При выполнении данного алгоритма следует из свойств бинарного дерева поискаобхода вершины будут выведены в следующем порядке: ''1 3 4 6 7 8 10 13 14''.
→Обход дерева поиска
=== Обход дерева поиска ===
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
* <tex>\mathrm{inorderTraversal}</tex> {{---}} обход узлов в отсортированном порядке,* <tex>\mathrm{preorderTraversal}</tex> {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево,* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина.
inorderTraversal('''Node''' x)
'''if''' x != ''null''
'''print''' x.key
inorderTraversal(x.right)
preorderTraversal('''Node''' x)
'''if''' x != ''null''
preorderTraversal(x.left)
preorderTraversal(x.right)
При выполнении данного обхода вершины будут выведены в следующем порядке: ''8 3 1 6 4 7 10 14 13''.
postorderTraversal('''Node''' x)
postorderTraversal(x.right)
'''print''' x.key
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 4 7 6 3 13 14 10 8 '' Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.
=== Поиск элемента ===
[[Файл:Bst search.png|thumb|right|318px|Поиск элемента 4]]
