树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解决法也该掌握，如非递归遍历节点等等。
二叉树结点定义：
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode *m_pLeft;
BinaryTreeNode *m_pRight;
}
1.求二叉树中的节点个数
递归方法：
（1）如果二叉树为空，节点个数为0；
（2）如果二叉树不为空，二叉树结点个数 = 左子树节点个数 + 右子树节点个数 + 1.
参考代码：
int GetNodeNum(BinaryTreeNode *pRoot)
{
if(pRoot == NULL)//递归出口
return 0;
return GetNodeNum(pPoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;
}
2.求二叉树的深度
递归解法：
（1）如果二叉树为空，二叉树的深度为0；
（2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1.
参考代码：
int GetDepth(BinaryTreeNode *pRoot)
{
if(pRoot == NULL)//递归出口
return 0;
int depthLeft = GetDepth(pRoot->m_pLeft);
int depthRight = GetDepth(pRoot->m_pRight);
return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
}
3.前序遍历，中序遍历，后序遍历
前序遍历递归解法：
（1）如果二叉树为空，空操作；
（2）如果二叉树不为空，方位根节点，前序遍历左子树，前序遍历右子树。
参考代码：
void PreOrderTraverse(BinaryTreeNode *pRoot)
{
if(pRoot == NULL)
return;
visit(pRoot);//访问根节点
PreOrderTraverse(pRoot->m_pLeft);//前序遍历左子树
PreOrderTraverse(pRoot->m_pRight);//前序遍历右子树
}
中序遍历递归解法：
(1)如果二叉树为空，空操作；
(2)如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树。
参考代码：
void InOrderTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
InOrderTraverse(pRoot->m_pLeft);//中序遍历左子树
Vist(pRoot);//访问根节点
InOrderTraverse(pRoot->m_pRight);//中序遍历右子树
}
后序遍历递归解法：
（1）如果二叉树为空，空操作；
（2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点。
参考代码：
void PostOrderTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
PostOrderTraverse(pRoot->m_pLeft);//后序遍历左子树
PostOrderTraverse(pRoot->m_pRight);//后序遍历右子树
Vist(pRoot);//访问根节点
}
4.分层遍历二叉树（按层次从上到下，从左到右）
相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。
void LevelTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
queue<BinaryTreeNode *> q;
q.push(pRoot);
while(!q.empty())
{
BinaryTreeNode *pNode = q.front();
q.pop();
Visit(pNode);
if(pNode->m_pLeft != NULL)
q.push(pNode->m_pLeft);
if(pNode->m_pRight != NULL)
q.push(pNode->m_pRight);
}
return;
}
FORM: