首页 > 代码库 > 二叉树(2)----中序遍历,递归和非递归实现

二叉树(2)----中序遍历,递归和非递归实现

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)递归实现

如果根节点为NULL,则返回

如果根节点不为NULL,则首先访问左子树,然后访问根节点,最后访问右子树


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

    InorderTraverse( pRoot->m_pLeft);
    Visiste( pRoot );
    InorderTraverse( pRoot->m_pRight);
}


(2)非递归实现

第一步:给定根节点pRoot,判断pRoot是否为空,如果不为空,然后进行第二步;如果为空,则进行第三步;

第二步:将pRoot入栈,将pRoot的左结点赋给pRoot,然后进行第一步;

第三步:判断栈是否为空;如果为空,则结束,如果不为空,则取出栈顶元素给pRoot,并出栈,访问pRoot,然后将pRoot的右结点赋给pRoot,然后进行第一步。


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

    stack < BTreeNode_t *> st;
    while( pRoot != NULL || !st.empty() ){
        while( pRoot != NULL ){
            st.push( pRoot);
            pRoot = pRoot->m_pLeft;
        }

        if( !st.empty() ){
            pRoot = st.top();
            st.pop();
            Visit( pRoot );
            pRoot = pRoot->m_pRight;
        }
    }

    return;
}


二叉树(2)----中序遍历,递归和非递归实现