二叉树的基本的遍历规则有三种：前序遍历，中序遍历和后序遍历。对于每一种遍历，树中每个结点都要经过3次。前序遍历在第一次遇到结点时立即访问，中序遍历第二次遇到结点时访问，后序遍历则到第三次遇到结点时才访问。
以一棵二叉树说明其三种遍历顺序：
二叉树的前序遍历
前序遍历：-
+ a * b – c d / e f
中序遍历：a + b * c – d – e / f
后序遍历：a b c d – * + e f / -
中序遍历：a + b * c – d – e / f
后序遍历：a b c d – * + e f / -
前序遍历算法：
template
void BinaryTree::PreOrder(BinTreeNode *subTree,
void (*visit)(BinTreeNode *P)) {
//递归函数：此算法按照前序遍历以subTree为根的二叉树。
if(subTree!=NULL){ //递归结束条件
visit(subTree); //访问根节点
PreOrder(subTree->leftChild,visit); //前序遍历根的左子树
PreOrder(subTree->rightChild,visit); //前序遍历根的右子树
}
};
中序遍历算法：
template
void BinaryTree::InOrder(BinTreeNode *subTree,
void(*visit)(BinTreeNode *p)){
//递归函数：此算法按照中序次序遍历以subTree为根的子数
if(subTree!=NULL) { //如果subTree为NULL，则结束递归
InOrder(subTree->leftChild,visit); //中序遍历根的左子树
visit(subTree); //访问根节点
InOrder(subTree->rightChild,visit); //中序遍历根的右子数
}
};
后序遍历算法：
template
void BinaryTree::PostOrder(BinTreeNode *subTree,
void (*visit)(BinTreeNode *P)) {
//递归函数，此算法按照后序遍历以subTree为根的二叉树
if(subTree!=NULL) { //递归结束条件
PostOrder(subTree->leftChild,visit); //后序遍历根的左子树
PostOrder(subTree->rightChild,visit); //后序遍历根的右子树
visit(subTree); //访问根节点
}
};
除了文章中有特别说明，均为IT宅原创文章，转载请以链接形式注明出处。
本文链接：
本文链接：