求二叉树的镜像,递归和非递归方式

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、求二叉树镜像

例如:

A                                                                    A

B                C                    ====>                    C            B


    D    E                                                                            E      D 


(1)递归方式

如果pRoot为NULL,则为空树,返回;

如果pRoot不为NULL,交换pRoot左右结点,然后分别求左右子树的镜像;

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

BTreeNode_t *pTemp = pRoot->m_pLeft;
    pRoot->m_pLeft = pRoot->m_pRight;
    pRoot->m_pLeft = pTemp;

BTreeMirror( pRoot->m_pLeft);
    BTreeMirror( pRoot->m_pRight);
    return;
}

(2)非递归方式

步骤描述:借助队列

首先,将根节点pRoot入队;

第一步:当队列未空时,获取当前层次的节点总数,即当前队列的长度;执行第二步;

第二步:按照当前层的节点总数,出队进行遍历节点,在遍历时,交换左右节点,如果左右节点存在,则入队;当遍历完当前层所有节点时,遍历下一层,执行第一步。

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

queue <BTreeNode_t *> que;
    que.push(pRoot);
    int curLevelNodesTotal = 0;
    while( !que.empty()){
        curLevelNodesTotal = que.size();
        int cnt = 0;
        while( cnt < curLevelNodesTotal ){
            ++cnt;
            pRoot = que.front();
            que.pop();
            BTreeNode_t *pTemp = pRoot->m_pLeft:
            pRoot->m_pLeft = pRoot->m_pRight;
            pRoot->m_pRight = pTemp;

if( pRoot->m_pLeft != NULL)
                que.push( pRoot->m_pLeft);
            if( pRoot->m_pRight != NULL )
                que.push( pRoot->m_pRight);
        }
    }

return;
}

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

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

Java中实现的二叉树结构

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

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

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

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

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

转载注明出处:https://www.heiqu.com/12d5027ce50c58c24804de05798b9c18.html