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

Question

У меня есть вопрос о двоичных деревьях:

Существует двоичное дерево T1 с n элементами. Когда мы запускаем обход ордера на T1, мы получаем серию от 1 до n (1,2,3, ... n). Теперь T1 a BST (Двоичное дерево поиска)?

Я знаю, что если T1 является BST, то обход по порядку приведет к сортировке ряда, но будет ли oposite направление работать?

Answer 1

Короче да ..

Двоичное свойство каждый узел на левом дереве является меньшим, и каждый узел справа больше.

Учитывая, что в любой суб дерева в вашем случае, поскольку мы обходе в заказ и увидел каждый элемент перед ними меньше, и мы поднимаемся при движении справа мы имеем BST ...

Answer 2

Это звучит слишком натощак, поэтому прямого ответа нет. Но:

Предположим, что корень имеет значение k.

Теперь попробуйте следующее: что означает средство для того, чтобы узел отображался слева от k в обход? Справа?

Кроме того, цифры, указанные до k, все меньше, чем k. Что здесь помогает в этом вопросе?