Question

利用搜索二叉树（查找二叉树）的中序遍历排序的问题

小弟刚看到数据结构，看到二叉搜索树的中序遍历出来的数据是有序的；所以把无序的数据一个一个插入二叉树，然后利用中序遍历进行一个一个取出来，那么数据就是有序的了！我想问问这个排序方法的时间复杂度是多少？空间复杂度是多少？

Answer 1

构建二叉搜索树的时候，把n个数据插入并维护它二叉搜索的特性时间复杂度是 n*log(n),中序遍历n,所以最终时间复杂度是n*log(n)+n,即O(n*log(n))。因为要新开一个存储结构存二叉搜索树，所以空间复杂度是O(n).