二叉树遍历（前中后层序／非递归） (一)

一：前中后序递归实现
[cpp]
/*
前中后序的递归实现理解起来最为简单，要点在于visit(node)的位置。
*/
/*
前中后序递归实现
*/
//前序遍历
void BT_PreOrder(BitTree node)
{
if(!node) return;

visit(node);
BT_PreOrder(node->left);
BT_PreOrder(node->right);
}

//中序遍历
void BT_InOrder(BitTree node)
{
if(!node) return;

BT_PreOrder(node->left);
visit(node);
BT_PreOrder(node->right);
}

//中序遍历
void BT_PostOrder(BitTree node)
{
if(!node) return;

BT_PreOrder(node->left);
BT_PreOrder(node->right);
visit(node);
}

/*
前中后序的递归实现理解起来最为简单，要点在于visit(node)的位置。
*/
/*
前中后序递归实现
*/
//前序遍历
void BT_PreOrder(BitTree node)
{
if(!node) return;

visit(node);
BT_PreOrder(node->left);
BT_PreOrder(node->right);
}

//中序遍历
void BT_InOrder(BitTree node)
{
if(!node) return;

BT_PreOrder(node->left);
visit(node);
BT_PreOrder(node->right);
}

//中序遍历
void BT_PostOrder(BitTree node)
{
if(!node) return;

BT_PreOrder(node->left);
BT_PreOrder(node->right);
visit(node);
}

二：层序递归实现
[cpp]
*
层序遍历
这种方式用队列来实现，也是最容易理解的方式，思路如下：
按照层序遍历的定义，访问完当前节点之后，则当前节点的左子节点具备了倒数第二优先级，当前节点的右子节点具备了倒数第一优先级，利用队列先进先出的特性（可以确定最低的优先级），可以实现。
*/
void BT_LevelOrder(BitTree node)
{
if(!node) return;

queue q;
q.push(node);

BitTree pvNode;
while(!q.empty())
{
pvNode = q.pop();
visit(pvNode);

if(!pvNode->left) q.push(pvNode->left);
if(!pvNode->right) q.push(pvNode->right);
}
}

/*
层序遍历
这种方式用队列来实现，也是最容易理解的方式，思路如下：
按照层序遍历的定义，访问完当前节点之后，则当前节点的左子节点具备了倒数第二优先级，当前节点的右子节点具备了倒数第一优先级，利用队列先进先出的特性（可以确定最低的优先级），可以实现。
*/
void BT_LevelOrder(BitTree node)
{
if(!node) return;

queue q;
q.push(node);

BitTree pvNode;
while(!q.empty())
{
pvNode = q.pop();
visit(pvNode);

if(!pvNode->left) q.push(pvNode->left);
if(!pvNode->right) q.push(pvNode->right);
}
}

三：前序非递归实现
[cpp]
/*
前序遍历非递归实现1
这种方式用栈来实现，也是最容易理解的方式，思路如下：
按照前序遍历的定义，访问完当前节点之后，则当前节点的左子节点具备了第一优先级，当前节点的右子节点具备了第二优先级，
利用栈后进先出的特性（可以确定最高的优先级），可以实现。
*/
void BT_PreOrderNoRec(BitTree node)
{
if(!node) return;

stack s;
BitTree pvNode;
s.push(node);
while(!s.empty())
{
pvNode = s.pop();
visit(pvNode);

if(!pvNode->right) s.push(pvNode->right);
if(!pvNode->left) s.push(pvNode->left);
}
}

/*
前序遍历非递归实现2
在网上看到的一种写法，个人觉得不如第一种实现起来更易懂
*/
void BT_PreOrderNoRec2(BitTree node)
{
if(!node) return;

stack s;
while(!node && !s.empty())
{
/*如果当前节点不为空，则直接访问，然后将节点存储到栈中（仅仅用来将来寻找右子节点），然后当前节点变为左字节点*/
if(node)
{
visit(node);
s.push(node);
node = node->left;
}
/*如果当前节点为空，则到栈中取出上一个节点，并找出右子节点进行访问*/
else
{
node = s.pop();
node = s.right;
}
}
}

/*
前序遍历非递归实现1
这种方式用栈来实现，也是最容易理解的方式，思路如下：
按照前序遍历的定义，访问完当前节点之后，则当前节点的左子节点具备了第一优先级，当前节点的右子节点具备了第二优先级，
利用栈后进先出的特性（可以确定最高的优先级），可以实现。
*/
void BT_PreOrderNoRec(BitTree node)
{
if(!node) return;

stack s;
BitTree pvNode;
s.push(node);
while(!s.empty())
{
pvNode = s.pop();
visit(pvNode);

if(!pvNode->right) s.push(pvNode->right);
if(!pvNode->left) s.push(pvNode->left);
}
}

/*
前序遍历非递归实现2
在网上看到的一种写法，