二叉树面试题之二叉树的遍历方式

一、基本概念
1、二叉树的概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成（即一个根节点最多只有两个孩子结点）。
2、二叉树的特点
（1）每个结点最多有两棵子树，即二叉树不存在度大于2的结点(分支数最大不超过2)
（2）二叉树的子树有左右之分，其子树的次序不能颠倒
3、完全二叉树与满二叉树
（1）满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子节点都在同一层上。
（2）完全二叉树：如果一棵具有N个结点的二叉树的结构与满二叉树的前N个结点的结构相同，称为完全二叉树。

4、二叉树的性质
（1）若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2 i-1 (i>=1)个结点
（2）若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2 k -1(k>=0)
（3）对任何一棵二叉树, 如果其叶结点个数为 n0 , 度为2的非叶结点个数为 n2 ,则有n0 ＝n 2 ＋1
（4）具有n个结点的完全二叉树的深度k为log2(n+1)上取整。
（5）对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

二、二叉树的基本操作
1、二叉树的创建
利用前序的规则，即先创建根节点，然后在创建右节点，最后创建左结点
2、在二叉树中，赋值运算符的重载
（1）先销毁原来的树
（2）拷贝现在的树
3、二叉树的销毁
利用后序的规则，防止将根节点销毁之后，其的左孩子或者右孩子找不到
上面几个基本操作的代码如下所示：

//二叉树结点的定义
template<class T> struct BinTreeNode {
//构造函数
BinTreeNode(const T&data)
:_data(data)
, _pLeft(NULL)
, _pRight(NULL)
{}
BinTreeNode *_pLeft;
BinTreeNode *_pRight;
T _data;
};

//二叉树的定义
template<class T>
class BinTree
{
typedef BinTreeNode Node;
typedef BinTreeNode* pNode ;
public:
//构造函数
BinTree()
:_pRoot(NULL)
{}
BinTree(const T* array, size_t size, const T& invalid)
{
size_t index = 0;//防止常引用
_CreateBinTree(_pRoot, array, size, index, invalid);//构造树
}
//拷贝构造函数
BinTree(const BinTree& bt)
{
_pRoot = _CopyBinTree(bt._pRoot);
}
//赋值运算符重载
BinTree& operator=(const BinTree& bt)
{
if (this != &bt)
{
//先销毁原来的树
_DestroyBinTree(_pRoot);
//拷贝现在的树
_pRoot = _CopyBinTree(bt._pRoot);
}
return *this;
}
private:
//利用后序遍历
void _DestroyBinTree(PNode pRoot)
{
if (pRoot)
{
//销毁左子树
_DestroyBinTree(pRoot->_pLeft);
//销毁右子树
_DestroyBinTree(pRoot->_pRight);
//销毁根节点
delete pRoot;
pRoot = NULL;
}
}
PNode _CopyBinTree(PNode pRoot)
{
PNode pNewNode = NULL;
if (pRoot)
{
//拷贝根节点
pNewNode = new Node(pRoot->_data);
//拷贝根节点的左孩子
if (pRoot->_pLeft)
pNewNode->_pLeft = _CopyBinTree(pRoot->_pLeft);
//拷贝根节点的右孩子
if (pRoot->_pRight)
pNewNode->_pRight = _CopyBinTree(pRoot->_pRight);
}
return pNewNode;
}
void _CreateBinTree(PNode& pRoot, const T* array, size_t size, size_t& index, const T& invalid)
{
if (index array[index])//防止无效值的插入
{
//创建根节点
pRoot = new Node(array[index]);
//创建左子树-
_CreateBinTree(pRoot->_pLeft, array, size, ++index, invalid);
//创建右子树
_CreateBinTree(pRoot->_pRight, array, size, ++index, invalid);
}
}
private:
PNode _pRoot;
};

树的形式：

三、二叉树的遍历方式
（一）层序遍历
结果：abcdef
思路：层序遍历：即一层访问完成之后，才去进行下一层，在遍历当前层的时候，需要将当前层的当前结点的左右孩子保存在队列中，再将其当前结点弹出，直至队列中为空，利用队列+循环
代码实现如下所示；

void _LevelOrder(pNode pRoot)
{
if (_pRoot == NULL)
return;
queue q;
q.push(pRoot);
pNode pCur = NULL;
while (!q.empty())
{
pCur = q.front();
cout <_data <<" ";
if (pCur->_pLeft)
q.push(pCur->_pLeft);
if (pCur->_pRight)
q.push(pCur->_pRight);
q.pop();
}
cout < }

验证结果如下所示：

（二）前序遍历
结果：abdcef
思路：在前序遍历中，先访问一棵树的根节点，其次访问一棵树的左子树，最后访问右子树，根据思路，实现递归与非递归。
1、递归：同思路
代码实现如下：

void _FrontOrder(pNode pRoot)
{
if (pRoot)
{
cout << pRoot->_data << " ";
_FrontOrder(pRoot->_pLeft);
_FrontOrder(pRoot->_pRight);
}
}

2、非递归：利用栈，首先将二叉树的根节点压入到栈中，利用循环，循环的终止条件是，栈中不为空，取栈顶元素，访问并弹出，如果栈中的右孩子存在，且将栈顶元素的右孩子压入到栈中，如果栈中的左孩子存在，且将栈顶元素的左孩子压入到栈中，重复以上过程，直到栈为空。
代码实现如下：

void _FrontOrder_Nor1(pNode pRoot)
{
if (NULL == pRoot)
return;
stack s;
s.push(pRoot);
while (!s.empty())
{
pNode pCur = s.top();
cout <_data <<" ";
s.pop();
if (pCur->_pRight)
s.push(pCur->_pRight);
if (pCur->_pLeft)
s.push(pCur->_pLeft);
}
}

3、非递归：由于在前序遍历中，一直先访问二叉树中的根节点与左孩子，因此，为了优化程序，因此如果当前结点的右孩子存在，将当前结点的右孩子压入到栈中，在此时，取二叉树的左孩子并且访问，直到当前结点没有右孩子，且栈中元素已经访问完成即可（即栈为空）。
代码实现如下所示：

void _FrontOrder_Nor2(pNode pRoot)
{
if (NULL == pRoot)
return;
stack s;
s.push(pRoot);
while (!s.empty())
{
pNode pCur = s.top();
s.pop();
while (pCur)
{
cout <_data <<" ";
if (pCur->_pRight)
s.push(pCur->_pRight);
pCur = pCur->_pLeft;
}
}
}

整体验证结果如下所示：

（三）中序遍历
结果：dbaecf
思路：在中序遍历中，先访问一棵树的左子树，其次访问一棵树的根节点，最后访问右子树，根据思路，实现递归与非递归。
1、递归：同思路
代码实现如下所示：

void _InOrder(pNode pRoot)
{
if (pRoot)
{
_InOrder(pRoot->_pLeft);
cout << pRoot->_data << " ";
_InOrder(pRoot->_pRight);
}
}

2、非递归
利用栈，定义临时变量，让其指向根节点，其次利用循环，循环条件while (pCur || !s.empty())，（出口的条件），在循环内部，让其的当前结点入栈，然后让其取当前结点的左孩子，一直入栈，直到当前结点为空为止，然后取其栈顶元素并且访问，让其临时变量指向栈顶元素，在取栈顶的右孩子，如果存在，压入到栈中，不存在，继续取栈顶元素即可，直到栈中为空且临时变量取到空为止。
代码实现如下所示：

void _InOrder_Nor(pNode pRoot)
{
if (NULL == pRoot)
return;
stack s;
pNode pCur = pRoot;
while (pCur || !s.empty())
{
while (pCur)
{
s.push(pCur);
pCur = pCur->_pLeft;
}
pCur = s.top();
cout <_data <<" ";
s.pop();
pCur = pCur->_pRight;
}
}


验证结果如下所示：

（四）后序遍历
结果：dbefca
思路：在后序遍历中，先访问一棵树的左子树，其次访问一棵树的右子树，最后访问根节点，根据思路，实现递归与非递归。
1、递归：同思路
代码实现如下所示：

void _PostOrder(pNode pRoot)
{
if (pRoot)
{
_PostOrder(pRoot->_pLeft);
_PostOrder(pRoot->_pRight);
cout << pRoot->_data << " ";
}
}

2、非递归
后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。
代码实现如下所示：

void _PostOrder_No1(pNode pRoot)
{
if (NULL == pRoot)
return;
pNode pCur = pRoot;
pNode pTop = NULL;
pNode Prev = NULL;
stack s;
while (pCur||!s.empty())
{
//左子树入栈
while (pCur)
{
s.push(pCur);
pCur = pCur->_pLeft;
}
//左子树入栈之后，取栈顶元素
pTop = s.top();
//判断栈顶元素是否有右子树
//右子树不存在，且右子树没有被访问
if (NULL == pTop->_pRight || Prev == pTop->_pRight)
{
//访问并弹出
cout <_data <<" ";
Prev = pTop;
s.pop();
}
else
pCur = pTop->_pRight;
}
}
void _PostOrder_No2(pNode pRoot)
{
if (NULL == pRoot)
return;
pNode pCur = pRoot;
pNode Prev = NULL;
stack s;
while (pCur || !s.empty())
{
//左子树入栈
//这块pCur != Prev改变了pCur的指向，因此是为了防止循环入栈
while (pCur&&pCur != Prev)
{
s.push(pCur);
pCur = pCur->_pLeft;
}
//这样防止形成死循环
if (s.empty())
return;
//左子树入栈之后，取栈顶元素
pCur = s.top();
//判断栈顶元素是否有右子树
//右子树不存在，且右子树没有被访问
if (NULL == pCur->_pRight || Prev == pCur->_pRight)
{
//访问并弹出
cout <_data <<" ";
Prev = pCur;
s.pop();
}
else
pCur = pCur->_pRight;
}
}

验证结果如下所示：

整体结果如下所示：

对于二叉树的遍历方式，就分为以上四种，如果大家还有更好的建议，还请大家指正！！

只有不停的奔跑，才能不停留在原地！！！