Сначала давайте вспомним, что такое деревья.
Деревья – это структура данных, имеющая множество дочерних элементов. Корневой узел является самым верхним узлом в дереве, а дочерний узел возникает из корневого узла.
Теперь, что такое бинарные деревья?
Двоичные деревья — это древовидная структура данных, имеющая только два дочерних элемента (левый и правый), поэтому имя и узлы, не имеющие дочерних элементов, являются листовыми узлами. Левый и правый дочерние узлы или узлы являются поддеревьями вне двоичного файла. дерево.
Двоичные деревья поиска являются бинарными деревьями, но левая половина/поддерево бинарного дерева поиска всегда меньше корневого узла, а правая половина/поддерево бинарного дерева поиска всегда больше корневого узла. левое поддерево и правое поддерево также должны быть бинарным деревом поиска, и в большинстве случаев не должно быть повторяющихся узлов.
Нахождение максимального элемента в двоичном дереве:
- Сначала мы объявляем переменную maxElement и присваиваем ей корневой узел (не данные/значение корневого узла, а корневой узел), поскольку мы должны вернуть максимальный элемент а не данные/значение максимального элемента.
- Затем мы должны увидеть значение корневого узла, и если корневой узел равен нулю, это означает, что он не существует, мы возвращаем корневой узел, так как ясно, что двоичное дерево поиска пусто, потому что оно существует. не содержит корневого узла.
- Однако, если есть корневой узел, мы проверяем справа, поскольку значения, превышающие корневые узлы, могут существовать только справа. Однако если бы это было бинарное дерево, но не бинарное дерево поиска, нам пришлось бы проверять как левую, так и правую стороны дерева.
- Затем мы идем вправо, и если значение справа от корневого узла равно null, это означает, что в дереве нет правильного элемента или узла, мы возвращаем корневой узел, так как это максимальный элемент в дереве.
- Однако, если у дерева есть правая сторона, мы проверяем данные внутри maxElement и, если они меньше, чем данные внутри правой части корневого узла, тогда мы назначаем право корневого узла. к maxElement и, используя рекурсию, мы обходим правую половину дерева, передавая правую часть узла, в котором мы находимся, внутри рекурсивной функции, пока правая сторона не достигнет нуля, а затем мы нажмите базовый случай и верните элемент.
Для нахождения минимального элемента в бинарном дереве поиска мы выполняем те же шаги, за исключением того, что при переходе вправо мы идем влево, поскольку элементы или узлы слева от дерева меньше, чем корневой узел.
Поиск минимального элемента в двоичном дереве поиска:
- Сначала мы объявляем переменную minElement и присваиваем ей корневой узел (не данные/значение корневого узла, а корневой узел), поскольку мы должны вернуть минимальный элемент, а не данные/значение минимального элемента.
- мы должны проверить значение корневого узла, и если корневой узел равен нулю, то дерево пусто, и мы возвращаем корневой узел.
- Однако, если есть корневой узел, мы проверяем левый от корневого узла, и если левый от корневого узла равен нулю, то это означает, что дерево не имеет левых узлов и минимальный элемент или узел является корневым узлом, и мы возвращаем его.
- Если дерево имеет левый узел, мы проверяем, меньше ли данных внутри minElement данных внутри левого узла, и если да, то заменяем предыдущее значение minElement. strong> с новым значением или новым элементом, и мы продолжаем обход дерева, используя рекурсию, передавая левую часть текущего узла внутри функции и продолжая заменять элемент в minElement пока мы не достигнем самого левого узла дерева и не нажмем null , этот узел не имеет дочерних элементов, то есть листового узла, и не попадет в базовый случай и не вернет минимальный элемент.
Ресурсы:
https://www.geeksforgeeks.org/difference-between-binary-tree-and-binary-search-tree/
