面试过程中。问的最多的题目大致是能够分为两类的。一类是链表。还有一类就是二叉树了，树（普通数）和B（+-）树因为稍难些，问的不是非常多。
往往在问到二叉树的时候。一般都是用递归的解法。然后现场写代码。
这里，还是像上一篇文章一样，我对很多二叉树的算法进行了总结。须要下载的朋友能够去这里免积分下载：
http://download.csdn.net/detail/dlutbrucezhang/8066557
也是像上一篇文章一样，这里我贴出二叉树代码类：
template <typename T>
class dutBinNode
{
public :
T data;
dutBinNode<T>* lChild;
dutBinNode<T>* rChild;
};
template <typename T>
class dutBinTree
{
private :
dutBinNode<T>* pRoot;
protected : /*包裹函数*/
void dutDeleteBinTree(dutBinNode<T>*); /*销毁二叉树*/
void dutCreateBinTree(dutBinNode<T>**); /*创建二叉树*/
void dutRecursionPreOrder(dutBinNode<T>*); /*递归前序遍历*/
void dutRecursionInOrder(dutBinNode<T>*); /*递归中序遍历*/
void dutRecursionPostOrder(dutBinNode<T>*); /*递归后序遍历*/
void dutNotRecursionPreOrder(dutBinNode<T>*); /*非递归前序遍历*/
void dutNotRecursionInOrder(dutBinNode<T>*); /*非递归中序遍历*/
void dutNotRecursionPostOrder(dutBinNode<T>*); /*非递归后序遍历*/
void dutLevelTraverseNoBranch(dutBinNode<T>*); /*不分行层次遍历*/
void dutLevelTraverseHasBranch(dutBinNode<T>*); /*分行层次遍历*/
void dutDepthFirstSearch(dutBinNode<T>*); /*深度优先遍历*/
void dutBreadthFirstSearch(dutBinNode<T>*); /*广度优先遍历*/
int dutDepthOfTree(dutBinNode<T>*); /*树的高度*/
int dutNodeCountOfTree(dutBinNode<T>*); /*树中节点个数*/
int dutLeafNodeCountOfTree(dutBinNode<T>*); /*树中叶子节点个数*/
int dutNodeCountInLevelK(dutBinNode<T>*, int); /*第k层节点个数*/
int dutPrintNodeInLevelK(dutBinNode<T>*, int); /*打印第K层节点*/
bool dutIsBalanceBinTree(dutBinNode<T>*, int&); /*是否是平衡二叉树*/
bool dutIsCompleteBinTree(dutBinNode<T>*); /*是否是全然二叉树*/
/*推断是否是子树*/
bool dutDoesTree1HaveTree2(dutBinNode<T>*, dutBinNode<T>*);
bool dutIsTreeHasSubTree(dutBinNode<T>*, dutBinNode<T>*);
void dutNotRecursionTreeMirroring(dutBinNode<T>*); /*非递归树的镜像*/
void dutRecursionTreeMirroring(dutBinNode<T>*); /*递归树的镜像*/
/*寻找和为某一值的路径*/
void dutFindPathEqualSum(dutBinNode<T>*, int, std :: vector<int>&, int);
/*二叉搜索树转换为双向链表*/
dutBinNode<T>* dutCluesBinTreeConvertToDoubleList(dutBinNode<T>*, dutBinNode<T>* &);
/*递归树中两个节点的最低公共祖先*/
dutBinNode<T>* dutRecursionGetLastCommonParent(dutBinNode<T>* ,dutBinNode<T>*, dutBinNode<T>*);
/*非递归树中两个节点的最低公共祖先*/
//bool dutNotRecursionGetLastCommonParent(dutBinNode<T>* ,dutBinNode<T>*, std :: vector<dutBinNode<T>*>&);
bool dutCmpStructOfTree(dutBinNode<T>*, dutBinNode<T>*); /*推断两棵树的结构是否同样，不考虑元素*/
bool dutCmpTreeIsEqual(dutBinNode<T>*, dutBinNode<T>*); /*推断两棵树是否同样，考虑元素*/
int dutMaxDistBetweenNodes(dutBinNode<T>*, int&); /*二叉树中节点间的最大距离*/
dutBinNode<T>* dutMinNodeInCluseBinTree(dutBinNode<T>*); /*二叉排序树中寻找最小值节点*/
dutBinNode<T>* dutMaxNodeInCluseBinTree(dutBinNode<T>*); /*二叉排序树中寻找最大值节点*/
dutBinNode<T>* dutFindNearestBigNode(dutBinNode<T>*, T _data); /*距离data近期且大于data的节点*/
dutBinNode<T>* dutFindNearestSmallNode(dutBinNode<T>*, T _data); /*距离data近期且小于data的节点*/
public :
dutBinTree<T>() : pRoot(NULL) {}
~dutBinTree<T>();
void dutCreateBinTree(); /*创建二叉树*/
void dutRecursionPreOrder(); /*递归前序遍历*/
void dutRecursionInOrder(); /*递归中序遍历*/
void dutRecursionPostOrder(); /*递归后序遍历*/
void dutNotRecursionPreOrder(); /*非递归前序遍历*/
void dutNotRecursionInOrder(); /*非递归中序遍历*/
void dutNotRecursionPostOrder(); /*非递归后序遍历*/
void dutLevelTraverseNoBranch(); /*不分行层次遍历*/
void dutLevelTraverseHasBranch(); /*分行层次遍历*/
void dutDepthFirstSearch(); /*深度优先遍历*/
void dutBreadthFirstSearch(); /*广度优先遍历*/
/*algorithm*/
int dutDepthOfTree(); /*树的高度*/
int dutNodeCountOfTree(); /*树中节点个数*/
int dutLeafNodeCountOfTree(); /*树中叶子节点个数*/
int dutNodeCountInLevelK(int); /*第k层节点个数*/
int dutPrintNodeInLevelK(int); /*打印第K层节点*/
bool dutIsBalanceBinTree(); /*是否是平衡二叉树*/
bool dutIsCompleteBinTree(); /*是否是全然二叉树*/
bool dutIsTreeHasSubTree(dutBinTree<T>); /*推断是否是子树*/
void dutNotRecursionTreeMirroring(); /*非递归树的镜像*/
void dutRecursionTreeMirroring(); /*递归树的镜像*/
void dutFindPathEqualSum(int, std :: vector<int>&); /*寻找和为某一值的路径*/
dutBinNode<T>* dutCluesBinTreeConvertToDoubleList(); /*二叉搜索树转换为双向链表(破坏了封装)*/
dutBinNode<T>* dutBinFindInBinSearchTree(int); /*二分查找树中寻找一个数(破坏了封装)*/
/*递归树中两个节点的最低公共祖先(破坏了封装)*/
dutBinNode<T>* dutRecursionGetLastCommonParent(dutBinNode<T>*, dutBinNode<T>*);
/*非递归树中两个节点的最低公共祖先(破坏了封装)*/
//dutBinNode<T>* dutNotRecursionGetLastCommonParent(dutBinNode<T>*, dutBinNode<T>*);
bool dutCmpStructOfTree(dutBinTree<T>); /*推断两棵树的结构是否同样。不考虑元素*/
bool dutCmpTreeIsEqual(dutBinTree<T>); /*推断两棵树是否同样，考虑元素*/
int dutMaxDistBetweenNodes(); /*二叉树中节点间的最大距离*/
/*破坏了封装*/
dutBinNode<T>* dutMinNodeInCluseBinTree(); /*二叉排序树中寻找最小值节点*/
dutBinNode<T>* dutMaxNodeInCluseBinTree(); /*二叉排序树中寻找最大值节点*/
dutBinNode<T>* dutFindNearestBigNode(T _data); /*距离data近期且大于data的节点*/
dutBinNode<T>* dutFindNearestSmallNode(T _data); /*距离data近期且小于data的节点*/
dutBinNode<T>* dutFindNextNodeInClueBinTree(dutBinNode<T>*); /*二叉搜索树的下一个节点*/
};