Consulta básica da árvore de pesquisa binária

Question

interroder travessia da BST é sempre classificado. Mas podemos dizer que a árvore binária é BST se e somente se a inorder for classificada? Quero dizer, se a inorder for classificada, podemos concluir que é sempre BST?

Answer 1

Se a altura é $ 0 $ é verdade.

Suponha que todas as árvores binárias para as quais a não seja classificada e a altura menor do que $ h $ são BST.

Considere uma árvore com raiz $ x $ , altura $ h $ e sua inorder é classificada. Em particular, sua subárvore esquerda e direita são classificadas e têm altura menor que $ H $ . Então, pela suposição, eles são BST. Agora, no inorder da árvore dada, o nó $ x $ é listado depois de todos os nós da subárvore esquerda. Desde que sua inorla é classificada, então $ x $ não é menor que qualquer nó da subárvore esquerda. Da mesma forma, $ x $ não é maior que qualquer nó da subárvore direita. Portanto, a árvore é uma BST.

Assim, por indução na altura da árvore binária, todas as árvores binárias para as quais a inorder é classificada são BST.