后序遍历二叉树算法
⑴ 先序遍历和后序遍历是什么
1、先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。
首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
例如，下图所示二叉树的遍历结果是：ABDECF
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
如右图所示二叉树
后序遍历结果：DEBFCA
已知前序遍历和中序遍历，就能确定后序遍历。
(1)后序遍历二叉树算法扩展阅读：
图的遍历算法主要有两种，
一种是按照深度优先的顺序展开遍历的算法，也就是深度优先遍历；
另一种是按照宽度优先的顺序展开遍历的算法，也就是宽度优先遍历。宽度优先遍历是沿着图的深度遍历图的所有节点，每次遍历都会沿着当前节点的邻接点遍历，直到所有点全部遍历完成。
如果当前节点的所有邻接点都遍历过了，则回溯到上一个节点，重复这一过程一直到已访问从源节点可达的所有节点为止。
如果还存在没有被访问的节点，则选择其中一个节点作为源节点并重复以上过程，直到所有节点都被访问为止。
利用图的深度优先搜索可以获得很多额外的信息，也可以解决很多图论的问题。宽度优先遍历又名广度优先遍历。通过沿着图的宽度遍历图的节点，如果所有节点均被访问，算法随即终止。宽度优先遍历的实现一般需要一个队列来辅助完成。
宽度优先遍历和深度优先遍历一样也是一种盲目的遍历方法。也就是说，宽度遍历算法并不使用经验法则算法， 并不考虑结果的可能地址，只是彻底地遍历整张图，直到找到结果为止。图的遍历问题分为四类：
1、遍历完所有的边而不能有重复，即所谓“欧拉路径问题”（又名一笔画问题）；
2、遍历完所有的顶点而没有重复，即所谓“哈密顿路径问题”。
3、遍历完所有的边而可以有重复，即所谓“中国邮递员问题”；
4、遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。
对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。
⑵ c++二叉树的几种遍历算法
遍历二叉树的所有结点且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历（除此之外还有层次遍历，但不常用，此处不做解释）。
1.前序遍历：根节点->左子树->右子树（根节点在前面）。
2.中序遍历：左子树->根节点->右子树（根节点在中间）。
3.后序遍历：左子树->右子树->根节点（根节点在后边）。
例如：求下面树的三种遍历：
前序遍历：abdefgc；
中序遍历：debgfac；
后序遍历：edgfbca。
⑶ 用递归算法先序中序后序遍历二叉树
1、先序
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
枣芦 printf(“%d ”, BT->Data); //对节点做些访问比如打印
PreOrderTraversal(BT->Left); //访问左儿子
PreOrderTraversal(BT->Right); //访问右儿子
}
}
2、中序
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d ", BT->Data);
InOrderTraversal(BT->Right);
}
}
3、后序
void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d ", BT->Data);
}
}
(3)后序遍历二叉树算法扩展阅读：
注意事项
1、前序遍历
从整棵二叉树的根结点开始，对于任意结点VV，访问结点VV并将结点VV入栈，并判断结点VV的左子结点LL是否为空。若LL不为空，则将LL置为当前结点VV；若LL为空，则取出栈顶结点，并将栈顶结点的右子结点置为当前结点VV。
2、中序遍历
从整棵凳滑带二叉树的根结点开始，对于任一结点VV，判断其左子结点LL是否为空。若LL不为空，则将VV入栈并将L置为当前结点VV；若让袭LL为空，则取出栈顶结点并访问该栈顶结点，然后将其右子结点置为当前结点VV。重复上述操作，直到当前结点V为空结点且栈为空，遍历结束。
3、后序遍历
将整棵二叉树的根结点入栈，取栈顶结点VV，若VV不存在左子结点和右子结点，或VV存在左子结点或右子结点，但其左子结点和右子结点都被访问过了，则访问结点VV，并将VV从栈中弹出。若非上述两种情况，则将VV的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。