【题目】

输入一颗二叉查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完毕树的镜像转换。

比如输入：

       8

     /      \

   6      10

  /   \     /  \

 5  7    9   11

输出：

      8

     /    \

  10    6

   /  \    /  \

 11  9  7  5

【分析】

【代码】

/**********************************   日期：2013-12-22*   作者：SJF0115*   题目: 11.求二叉查找树的镜像*   来源：*   分类：程序猿面试题精选100题**********************************/#include 
     
      using namespace std;struct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x):val(x),left(NULL),right(NULL){}};// 求二叉查找树的镜像void BinaryTreeMirror(TreeNode*& root){    if(root == NULL){        return;    }    TreeNode *p = root;    // 左右子节点交换    TreeNode *tmp;    tmp = p->left;    p->left = p->right;    p->right = tmp;    // 左子树    if(p->left){        BinaryTreeMirror(p->left);    }//if    // 右子树    if(p->right){        BinaryTreeMirror(p->right);    }//if}// 中序遍历void InOrder(TreeNode* root){    if(root == NULL){        return;    }    if(root->left){        InOrder(root->left);    }    cout<
      
       val<
       
        right){        InOrder(root->right);    }}// 二叉查找树插入void TreeInsert(TreeNode*& root,int val){    // 创建新节点    TreeNode* node = new TreeNode(val);    if(root == NULL){        root = node;    }    else{        TreeNode *pre = NULL;        TreeNode *cur = root;        // 寻找插入位置        while(cur){            // 父节点            pre = cur;            // 沿左子树方向下降            if(val < cur->val){                cur = cur->left;            }            // 沿右子树方向下降            else{                cur = cur->right;            }        }//while        // 插入左子结点处        if(val < pre->val){            pre->left = node;        }        // 插入右子结点处        else{            pre->right = node;        }//if    }//if}int main(){    int array[] = {8,6,10,5,7,9,11};    // 创建二叉查找树    TreeNode *root = NULL;    for(int i = 0;i < 7;i++){        TreeInsert(root,array[i]);    }    // 二叉树镜像    BinaryTreeMirror(root);    // 中序遍历    InOrder(root);    return 0;}
       
      
     

【代码二】

// 求二叉查找树的镜像void BinaryTreeMirror(TreeNode*& root){    if(root == NULL){        return;    }    stack
     
       stack;    TreeNode *p = root;    // 先序遍历    while(p != NULL || !stack.empty()){        if(p != NULL){            // 左右子节点交换            TreeNode *tmp;            tmp = p->left;            p->left = p->right;            p->right = tmp;            // 入栈            stack.push(p);            //訪问左子树            p = p->left;        }//if        else{            //退栈            p = stack.top();            stack.pop();            //訪问右子树            p = p->right;        }    }//while}
     

【解析二】

因为递归的本质是编译器生成了一个函数调用的栈，因此用循环来完毕相同任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。

在循环中。仅仅要栈不为空，弹出栈的栈顶结点，交换它的左右子树。假设它有左子树，把它的左子树压入栈中。假设它有右子树，把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。

【代码三】

// 求二叉查找树的镜像void BinaryTreeMirror(TreeNode*& root){    if(root == NULL){        return;    }    stack
     
       stack;    stack.push(root);    TreeNode *p = NULL;    while(!stack.empty()){        p = stack.top();        stack.pop();        // 左右子节点交换        TreeNode *tmp;        tmp = p->left;        p->left = p->right;        p->right = tmp;        // 左子节点不空压入栈中        if(p->left){            stack.push(p->left);        }        // 右子节点不空压入栈中        if(p->right){            stack.push(p->right);        }    }//while}