树结构问题因为容易写出解法，因此经常出现在面试题中
1. 树的种类
1) Tree
2) Binary Trees
3) Binary Search Trees(BST) : used to sorted or ordered data. //解决方案：recursion
查找操作(fast and simple)：O(logn)
插入和删除：O(logn)
打印：O(n)
4) Heap: find the maximum value / minimum value(min-heap) in constant time.
插入和删除：O(logn)
查找：O(n) ，因为除了顶点，左右子书是无序的
2. 通常的查询方法
注意：如果查找的树结构是无序的，时间复杂度是O(n)，所以复杂的树要避免使用普通的树结构
1）BFS ：空间开销大
2) DFS
3. Traversals
当需要遍历树中的每个点时使用的方法，遍历方法有很多。 // recursive
最寻常的Depth-first-traversals for binary tree的种类
1) Pre-order : a node is always visited before any its children, then left first
2) In-order : The left subtree is visited first, then the node itself, and then the nodes‘s right subtree.
3) Post-order: left, right, node. A node is always visited after all its children.
原文：https://www.cnblogs.com/GW977/p/10049995.html