二叉树：后序遍历，递归和非递归方式

1、二叉树定义typedef struct BTreeNodeElement_t_ {
void *data;
} BTreeNodeElement_t;typedef struct BTreeNode_t_ {
BTreeNodeElement_t *m_pElemt;
struct BTreeNode_t_ *m_pLeft;
struct BTreeNode_t_ *m_pRight;
} BTreeNode_t;2、后序遍历定义：给定根节点，首先遍历左子树，然后遍历右子树，最后遍历根节点（1）递归实现如果根节点为空，则返回。如果根节点不为空，则首先遍历左子树，然后遍历右子树，最后遍历根节点。void PostorderTraverse（ BTreeNode_t *pRoot）{
if（ pRoot == NULL ）{
return;
} PostorderTraverse（ pRoot->m_pLeft）;
PostorderTraverse（ pRoot->m_pRight）;
Visit（pRoot）;
}（2）非递归方式第一步：给定pRoot，判断pRoot是否为NULL；如果不为NULL，执行第二步；如果为NULL，执行第三步；第二步：将pRoot入栈，并将pRoot的左结点赋给pRoot，执行第一步；第三步：如果栈不为空，则将栈顶元素赋给pRoot，判断pRoot是否有右子树以及右子树是否访问过；如果没有右子树或者已经访问过右子树，则访问pRoot并出栈，然后执行第一步；如果有右子树并且右子树还没有访问过，则将pRoot右结点赋给pRoot，然后执行第一步。void PostorderTraverse（ BTreeNode_t *pRoot ）{
if（ pRoot == NULL ）
return NULL; stack <BTreeNode_t *> st;
BTreeNode_t *visitedNode = NULL;
while（ pRoot ！= NULL || ！st.empty（））{
while（ pRoot ！= NULL ）{
st.push（ pRoot ）;
pRoot = pRoot->m_pLeft;
} if（！st.empty（））{
pRoot = st.top（）;
if（ pRoot->m_pRight == NULL || pRoot->m_pRight == visitedNode）{
Visited（ pRoot）;
st.pop（）;
pRoot = NULL; //防止重复遍历，如果不赋值NULL，则会重复遍历
} else {
pRoot = pRoot->m_pRight; //遍历右子树
}
}
}
}（3）非递归方式：使用双栈法参考： http://www.linuxidc.com/Linux/2015-01/111636.htm首先将根节点pRoot入栈1：步骤一：将栈1的栈顶元素赋给pRoot，然后将pRoot入栈2；然后先将pRoot左结点入栈1，后将pRoot右结点入栈1，顺序一定不能错。步骤二：出栈2，就获得后序遍历void PostorderTraverse（ BTreeNode_t *pRoot）{
if（ pRoot == NULL ）
return; stack <BTreeNode_t *> st1;
stack <BTreeNode_t *> st2;
st1.push（ pRoot）;
while（！st1.empty（））{
pRoot = st1.top（）;
st1.pop（）;
st2.push（ pRoot）;
if（ pRoot->m_pLeft）
st1.push（ pRoot->m_pLeft）;
if（ pRoot->m_pRight）
st1.push（ pRoot->m_pRight）;
} while（！st2.empty（）{
pRoot = st2.top（）;
st2.pop（）;
Visite（ pRoot ）;
}
return;
}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-01/111635.htm