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