Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность

Применение бинарного дерева

[Концепция] Двоичное дерево сортировки

Также известное как двоичное дерево поиска (BST, Binary Search Tree). Двоичное дерево — это либо пустое двоичное дерево, либо двоичное дерево со следующими свойствами: Ключевые слова всех узлов в левом поддереве меньше, чем ключевые слова корневого узла. ; Ключи всех узлов в правом поддереве больше, чем ключи корневого узла. Левое поддерево и правое поддерево представляют собой бинарное отсортированное дерево.

[Концепция] Поиск по двоичному сортировочному дереву

Значение узла левого поддерева

[Концепция] Вставка двоичного дерева сортировки

Если исходное двоичное дерево сортировки пусто, вставьте узел напрямую; В противном случае, если ключевое слово k меньше значения корневого узла, оно вставляется в левое поддерево, а если ключевое слово k больше значения корневого узла, оно вставляется в правое поддерево.

[Концепция] Построение бинарного дерева сортировки

Построить BST в соответствии с последовательностью str={45, 24, 53,12}

Построить BST в соответствии с последовательностью str={24, 45, 12,53}

Последовательность другая, построение бинарного дерева другое

[Концепция] Удаление дерева двоичной сортировки

Дело 1

Первый поиск, чтобы найти целевой узел: ① Если удаленный узел z является конечным узлом, удалите его напрямую, не разрушая свойства бинарного дерева сортировки.

Случай 2

Первый поиск, чтобы найти целевой узел:

① Если удаленный узел z является конечным узлом, удалите его напрямую, не разрушая свойства бинарного дерева сортировки. ② Если узел z имеет только одно левое или правое поддерево, пусть поддерево узла z станет поддеревом родительского узла узла z, заменив положение узла z.

Случай 3

Первый поиск, чтобы найти целевой узел: ① Если удаленный узел z является конечным узлом, удалите его напрямую, не разрушая свойства бинарного дерева сортировки. ② Если узел z имеет только одно левое или правое поддерево, пусть поддерево узла z станет поддеревом родительского узла узла z, заменив положение узла z. ③ Если узел z имеет левое и правое поддеревья, пусть прямой преемник (или прямой предшественник) z заменит z, а затем удалите этого прямого преемника (или прямого предшественника) из бинарного дерева сортировки, чтобы он был преобразован в первое или второе кейс.