На самом деле я хочу знать не то, как реализовать алгоритм обхода по порядку для BST, а реализовать его только с использованием алгоритмов вставки, удаления и обхода в предварительном порядке для BST.
Вы можете предположить, что вам дана реализации стандартных алгоритмов BST для вставки, удаления и обхода предварительного порядка.
как реализовать обход BST по порядку?
comment
Вы искали немного вокруг ?? Посмотрите на эту ссылку.
- person devsaw schedule 03.08.2013
Ответы (2)
Хммм... Допустим, у нас есть + в корне, 1 в левом узле и 2 в правом узле. Предварительный порядок будет + 1 2, а порядок будет 1 + 2.. разница в том, что 1-й и 2-й поменялись местами, поэтому, если у вас есть вставка и удаление, вы можете рекурсивно поменять местами каждое значение корневого узла с его значением левого узла, а затем с помощью pre -order обход дерева, который вернется, вызовет неупорядоченный обход.
Я не уверен, что это правильный путь, но я надеюсь, что это поможет.
person
Ankur
schedule
18.10.2011
Анкур, кажется, у тебя где-то что-то не так. Мы можем удалить и вставить элемент, но два элемента не меняются местами, поскольку все операции вставки и удаления будут выполняться так, чтобы они защищали свойство двоичного поиска.
- person Tharindu Rusira; 21.10.2011
Я думаю, что нашел решение. :)
у нас есть методы обхода предварительного заказа, вставки и удаления.
Предположим, что нам дан BST.
что мы делаем, так это предоставляем метод обхода предварительного заказа с заданным BST. поскольку обход в предварительном порядке всегда сначала идет к родительскому узлу, мы рекурсивно удаляем и вставляем каждый корневой (поскольку корень — это первый родитель, которого мы встречаем) узел, пока левое поддерево корня не станет нулевым.
теперь вы начинаете удалять корень до тех пор, пока не останется узлов. Поместите эти удаленные узлы в массив или куда хотите. Вы получите отсортированный набор узлов. (т.е. узлы будут удалены в отсортированном порядке. Сначала самые маленькие и так далее...)
person
Tharindu Rusira
schedule
21.10.2011
