数据结构面试之五—二叉树的常见操作（递归实现部分）

题注

《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。

二叉树是笔试、面试的重点，包括选择题的题型之——求解前、中、后序的遍历结果等。去年（2011秋季）的百度笔试试题就考察了二叉树的后序遍历的非递归实现。

笔者先就下面常考几个题目就递归算法的实现分析如下：

递归的核心就是遍历完根节点后，再依次同样的方法递归左孩子、右孩子节点，直到为空为止！

1.中根遍历

//中序:左->根->右[递归实现]

  template<typename elemType>       voidbinaryTreeType<elemType>::inorder(nodeType<elemType> *p)       {              if(