1. 前序/中序/后序遍历（递归实现）

复制代码 代码如下:

// 前序遍历

void BT_PreOrder(BiTreePtr pNode){

if (!pNode) return;

visit(pNode);

BT_PreOrder(pNode->left);

BT_PreOrder(pNode->right); }

// 中序遍历

void BT_PreOrder(BiTreePtr pNode){

if (!pNode) return;

BT_PreOrder(pNode->left);

visit(pNode);

BT_PreOrder(pNode->right);}

// 后序遍历void BT_PreOrder(BiTreePtr pNode){

if (!pNode) return;

BT_PreOrder(pNode->left);

BT_PreOrder(pNode->right);

visit(pNode);}

2. 前序遍历（非递归实现）

复制代码 代码如下:

// 用栈实现

void BT_PreOrderNoRec1(BiTreePtr pNode){

stack<BiTreePtr> s;

while (!pNode || !s.empty())

{

if (!pNode)

{

visit(pNode);

s.push(pNode);

pNode = pNode->left;

}

else

{

pNode = s.pop();

pNode = pNode->right;

}

}

}

// 用栈实现

void BT_PreOrderNoRec2(BiTreePtr pNode){

if (!pNode)

{

stack<BiTreePtr> s;

s.push(pNode);

while (!s.empty())

{

BiTreePtr pvNode = s.pop();

visit(pvNode);

s.push(pvNode->right);

s.push(pvNode->left);

}

}}

//

不用栈实现 每个节点含父节点指针和isVisited【默认为false】状态变量 且该二叉树含一个头节点

void BT_PreOrderNoRec3(BiTreePtr pNode){

while (!pNode)

// 回溯到指向根节点的头节点时退出

{

if( !pNode->bVisited )

// 判定是否已被访问

{

visit(pNode);

pNode->isVisited = true;

}

if ( pNode->left && !pNode->left->isVisited )

pNode = pNode->left;

else if( pNode->right && !pNode->right->isVisited )

pNode = pNode->right;

else

//回溯

pNode = pNode->parent;

}}

3. 中序遍历（非递归实现）

复制代码 代码如下:

// 用栈实现

void BT_InOrderNoRec1(BiTreePtr pNode){

stack<BiTreePtr> s;

while (!pNode || !s.empty())

{

if (!pNode)

{

s.push(pNode);

pNode = pNode->left;

}

else

{

pNode = s.pop();

visit(pNode);

pNode = pNode->right;

}

}}

// 不用栈实现 每个节点含父节点指针和isVisited【默认为false】的状态变量 且该二叉树含一个头节点

void BT_InOrderNoRec2(BiTreePtr pNode){

while (!pNode)

// 回溯到指向根节点的头节点时退出

{

while (pNode->left && !pNode->left->isVisited)

pNode = pNode->left;

if (!pNode->isVisited)

{

visit(pNode);

pNode->isVisited=true;

}

if (pNode->right && !pNode->right->isVisited)

pNode = pNode->right;

else

pNode = pNode->parent;

}}

4. 后序遍历（非递归实现）

复制代码 代码如下:

void BT_PostOrderNoRec(BiTreePtr pNode){

if(!pNode) return;

stack<BiTreePtr> s;

s.push(pNode);

while (!s.empty())

{

BiTreePtr pvNode = s.pop();

if (pvNode->isPushed)

// 表示其左右子树都已入栈，访问该节点

visit(pvNode);

else

{

if (pvNode->right)

{

pvNode->right->isPushed = false;

S.push(pvNode->right);

}

if (pvNode->left)

{

pvNode->left->isPushed = false;

s.push(pvNode->left);

}

pvNode->isPushed = true;

s.push(pvNode);

}

}}

5. 层序遍历（使用队列）

复制代码 代码如下:

void BT_LevelOrder(BiTreePtr pNode){

if (!pNode) return;

queue<BiTreePtr> q;

q.push(pNode);

BiTreePtr pvNode;

while (!q.empty())

{

pvNode = q.pop();

visit(pvNode);

if (pvNode->left)

q.push(pvNode->left);

if (pvNode->right)

q.push(pvNode->right);

}}