HYPERLINK"http://www.cnblogs.com/kekec/archive/2011/10/11/2207671.html"二叉树遍历算法1.前序/中序/后序遍历（递归实现）//前序遍历voidBT_PreOrder(BiTreePtrpNode){if(!pNode)return;visit(pNode);BT_PreOrder(pNode->left);BT_PreOrder(pNode->right);}//中序遍历voidBT_PreOrder(BiTreePtrpNode){if(!pNode)return;BT_PreOrder(pNode->left);visit(pNode);BT_PreOrder(pNode->right);}//后序遍历voidBT_PreOrder(BiTreePtrpNode){if(!pNode)return;BT_PreOrder(pNode->left);BT_PreOrder(pNode->right);visit(pNode);}2.前序遍历（非递归实现）//用栈实现voidBT_PreOrderNoRec1(BiTreePtrpNode){stack<BiTreePtr>s;while(!pNode||!s.empty()){if(!pNode){visit(pNode);s.push(pNode);pNode=pNode->left;}else{pNode=s.pop();pNode=pNode->right;}}}//用栈实现voidBT_PreOrderNoRec2(BiTreePtrpNode){if(!pNode){stack<BiTreePtr>s;s.push(pNode);while(!s.empty()){BiTreePtrpvNode=s.pop();visit(pvNode);s.push(pvNode->right);s.push(pvNode->left);}}}//不用栈实现每个节点含父节点指针和isVisited【默认为false】状态变量且该二叉树含一个头节点voidBT_PreOrderNoRec3(BiTreePtrpNode){while(!pNode)//回溯到指向根节点的头节点时退出{if(!pNode->bVisited)//判定是否已被访问{visit(pNode);pNode->isVisited=true;}if(pNode->left&&!pNode->left->isVisited)pNode=pNode->left;elseif(pNode->right&&!pNode->right->isVisited)pNode=pNode->right;else//回溯pNode=pNode->parent;}}3.中序遍历（非递归实现）//用栈实现voidBT_InOrderNoRec1(BiTreePtrpNode){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】的状态变量且该二叉树含一个头节点voidBT_InOrderNoRec2(BiTreePtrpNode){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;elsepNode=pNode->parent;}}4.后序遍历（非递归实现）voidBT_PostOrderNoRec(BiTreePtrpNode){if(!pNode)return;stack<BiTreePtr>s;s.push(pNode);while(!s.empty()){BiTreePtrpvNode=s.pop();if(pvNode->is