【大话数据结构C语言】31 二叉树后序遍历算法

我的首发平台是公众号【CodeAllen】，学习交流QQ群：736386324

后序遍历的代码

/* 二叉树的后序遍历递归算法 */
/* 初始条件: 二叉树T存在 */
/* 操作结果: 后序递归遍历T */
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);   /* 先后序遍历左子树  */
    PostOrderTraverse(T->rchild);   /* 再后序遍历右子树  */
    printf("%c",T->data);           /* 显示结点数据，可以更改为其它对结点操作 */
}

二叉树后序遍历的实现思想是：从根节点出发，依次遍历各节点的左右子树，直到当前节点左右子树遍历完成后，才访问该节点元素。 如上图中，对此二叉树进行后序遍历的操作过程为：

• 从根节点 1 开始，遍历该节点的左子树（以节点 2 为根节点）；
• 遍历节点 2 的左子树（以节点 4 为根节点）；
• 由于节点 4 既没有左子树，也没有右子树，此时访问该节点中的元素 4，并回退到节点 2 ，遍历节点 2 的右子树（以 5 为根节点）；
• 由于节点 5 无左右子树，因此可以访问节点 5 ，并且此时节点 2 的左右子树也遍历完成，因此也可以访问节点 2；
• 此时回退到节点 1 ，开始遍历节点 1 的右子树（以节点 3 为根节点）；
• 遍历节点 3 的左子树（以节点 6 为根节点）；
• 由于节点 6 无左右子树，因此访问节点 6，并回退到节点 3，开始遍历节点 3 的右子树（以节点 7 为根节点）；
• 由于节点 7 无左右子树，因此访问节点 7，并且节点 3 的左右子树也遍历完成，可以访问节点 3；节点 1 的左右子树也遍历完成，可以访问节点 1；
• 到此，整棵树的遍历结束。

由此，对上图中二叉树进行后序遍历的结果为： 4 5 2 6 7 3 1