后序遍历

后序遍历(LRD)是二来自叉树遍历的一种，也叫做后根遍历、后序易更企含呼编讲周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中调华概海持测客宣造，先左后右再根。巧记:左右根。

• 中文名 后序遍历
• 外文名 Postorder Traversal (LRD)
• 类型 二叉树遍历
• 别名 后根遍历

简介

　　后序来自遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍袁气分歌历左子树，然后遍历右子树，最后遍历根结点。即:

　　若二叉树为空则结束返回，

　　否则:(1)后序遍历左子树

　　(2)后序遍历右子树

　　(3)访问根结点

　　如右图所示二叉树

　　后序遍历结果:DEBFCA

　　已知前序遍历和中序遍历终绍甲重本毫师，就能确定后序遍历。

递归算法

　　算法5(Java语言)

非递归算法

算法核心思想:

　　首先要搞清楚先素陈置概序、中序、后序的非递归算法共同之处:用栈来保存先前走过的路径，以便可以在访问完子树后,可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。

　　后序遍历的非递归算法是三种顺序中来自最复杂的，原因在于，后序遍历是笑运先访问左、右子树,再访问根节点，而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，如果从左子树回退到根节点，此时就应该去访问右子树，而如果从右子树回退到根节点，此时就应该访问根节点。所以相比前序和后序，必须得在压栈时添加信息，以便在退栈时可以知道是从左360百科子树返回，还是从右子树返回进而决定下一步的操作。

算法1(c语言)

　　算法2