2.3.4 树

树是一种在实际编程过程中经常会遇到的数据结构。它的逻辑很简答；除根节点之外每个节点都只有一个父节点，根节点没有父节点。
除叶节点之外所有的节点都有一个或多个子节点，叶子节点没有子节点。父节点和子节点之间用指针链接。由于树的操作会涉及大量指针
因此与树有关的面试题都不太容易。当面试官想考查应聘者在有复杂指针操作的情况下写代码的能力时，他往往会想到用与树有关的面试题。
面试的时候提到的树，大部分是二叉树。所谓二叉树是一种树的特殊结构，在二叉树中每个节点最多只能有两个子节点。
在树种最重要的操作莫过于遍历，即按照某一顺讯访问树中的节点。通常树有如下几种遍历方式：

• 前序遍历
• 中序遍历
• 后续遍历

很多面试官喜欢直接或间接考查遍历

• 面试题26“树的子结构”
• 面试题34“二叉树中和为某一值的路径”

• 面试题55“二叉树的深度”
  

• 面试题7“重建二叉树”
• 面试题33“二叉搜索树的后续遍历序列”
  也是考查对遍历特点的理解，因此应聘者应该对这3种遍历的6种方法都了如执掌。