二叉树:后序遍历,递归和非递归方式

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)非递归方式:使用双栈法

参考:

首先将根节点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;
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

Java中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/4df93295e55eb2f33d96b6645d0e6a88.html