数据结构中二叉树各种题型详解及程序.docx

《数据结构中二叉树各种题型详解及程序.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、轻松搞定面试中的二叉树题目树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结，希望对找工作的同学有所帮助。二叉树节点定义如下：structBinaryTreeNode{  intm_nValue;  BinaryTreeN

2、ode*m_pLeft;  BinaryTreeNode*m_pRight;};相关链接：轻松搞定面试中的链表题目题目列表：1.求二叉树中的节点个数2.求二叉树的深度3.前序遍历，中序遍历，后序遍历4.分层遍历二叉树（按层次从上往下，从左往右）5.将二叉查找树变为有序的双向链表6.求二叉树第K层的节点个数7.求二叉树中叶子节点的个数8.判断两棵二叉树是否结构相同9.判断二叉树是不是平衡二叉树10.求二叉树的镜像11.求二叉树中两个节点的最低公共祖先节点12.求二叉树中节点的最大距离13.由前序遍历序列和中序遍历序列重建二叉树14.判

3、断二叉树是不是完全二叉树详细解答1.求二叉树中的节点个数递归解法：（1）如果二叉树为空，节点个数为0（2）如果二叉树不为空，二叉树节点个数=左子树节点个数+右子树节点个数+1参考代码如下：1.int GetNodeNum(BinaryTreeNode * pRoot)  2.{  3.    if(pRoot == NULL) // 递归出口  4.        return 0;  5.    return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;

4、  6.}  2.求二叉树的深度递归解法：（1）如果二叉树为空，二叉树的深度为0（2）如果二叉树不为空，二叉树的深度=max(左子树深度，右子树深度)+1参考代码如下：1.int GetDepth(BinaryTreeNode * pRoot)  2.{  3.    if(pRoot == NULL) // 递归出口  4.        return 0;  5.    int depthLeft = GetDepth(pRoot->m_pLeft);  6.    int depthRight = GetDepth(pRoot

5、->m_pRight);  7.    return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);   8.}  3.前序遍历，中序遍历，后序遍历前序遍历递归解法：（1）如果二叉树为空，空操作（2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树参考代码如下：1.void PreOrderTraverse(BinaryTreeNode * pRoot)  2.{  3.    if(pRoot == NULL)  4.        return

6、;  5.    Visit(pRoot); // 访问根节点  6.    PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树  7.    PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树  8.}  中序遍历递归解法（1）如果二叉树为空，空操作。（2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树参考代码如下：1.void InOrderTraverse(BinaryTreeNode * pRoot)  2.{  3.    if(p

7、Root == NULL)  4.        return;  5.    InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树  6.    Visit(pRoot); // 访问根节点  7.    InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树  8.}  后序遍历递归解法（1）如果二叉树为空，空操作（2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点参考代码如下：1.void PostOrderTraverse(BinaryTree

8、Node * pRoot)  2.{  3.    if(pRoot == NULL)  4.        return;  5.    PostOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树