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 ? 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）非递归方式：使用双栈法

首先将根节点pRoot入栈1：

步骤一： 将栈1的栈顶元素赋给pRoot，然后将pRoot入栈2；然后先将pRoot左结点入栈1，后将pRoot右结点入栈1，顺序一定不能错。

步骤二：出栈2，就获得后序遍历

void? PostorderTraverse( BTreeNode_t *pRoot){
? ? if( pRoot == NULL )
? ? ? ? return;

? ? stack st1;
? ? stack 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;
}