как реализовать прохождение BST inorder?

Question

На самом деле я хочу знать не о том, как реализовать алгоритм обхода по порядку для BST, а реализовать его только с использованием алгоритмов вставки, удаления и предварительного порядка для BST.
Можно предположить, что выприведены реализации для стандартных алгоритмов BST для вставки, удаления и обхода предварительного заказа.

Answer 1

Я думаю, что нашел решение.:)

у нас есть методы обхода, вставки и удаления предварительного заказа.

Предположим, что нам дан BST.

что мы делаем, мы предоставляемметод обхода заказа с заданным BST.Так как обход по предварительному заказу всегда сначала идет к родительскому узлу, мы рекурсивно удаляем и вставляем каждый корневой узел (поскольку корень - первый родительский элемент, с которым мы встречаемся), пока левое поддерево корня не станет нулевым.

сейчасВы начинаете удалять корень, пока не останется ни одного узла. Поместите эти удаленные узлы в массив или куда угодно.Вы получите отсортированный набор узлов.(то есть узлы будут удалены в отсортированном порядке. сначала самые маленькие и так далее ...)

Answer 2

Хммм ... Допустим, у нас есть + в корне и 1 в левом узле и 2 в правом узле.Предварительный порядок будет + 1 2, а порядок будет 1 + 2 .. Разница в том, что 1-й и 2-й были поменяны местами, поэтому, если у вас есть вставка и удаление, вы можете рекурсивно поменять местами каждое значение корневого узла с его значением левого узлаи затем использование обхода предзаказа по дереву, которое вернется, вызовет обход по порядку.

Я не уверен, что это путь, но я надеюсь, что это поможет.