输入一颗二元查找树，将该树转换为它的镜像

第15题：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。 
例如输入：
  8
  / \
  6 10
 /\ /\
5 7 9 11

输出：
   8
  / \
 10 6
 /\ /\
11 9 7 5

定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
  int m_nValue; // value of node
  BSTreeNode *m_pLeft; // left child of node
  BSTreeNode *m_pRight; // right child of node
};

[cpp] #include<iostream>  
#include<iomanip>  
#include<stack>   
using namespace std; 
//定义二元查找树的结点为：  
struct BSTreeNode // a node in the binary search tree (BST)  
{ 
int m_nValue; // value of node  
BSTreeNode *m_pLeft; // left child of node  
BSTreeNode *m_pRight; // right child of node  
}; 
void cfun(BSTreeNode *pt) 
{ 
    if(!pt){ 
       return; 
    } 
    BSTreeNode * ptem=pt->m_pLeft; 
    pt->m_pLeft=pt->m_pRight; 
    pt->m_pRight=ptem; 
    if(pt->m_pLeft){ 
       cfun(pt->m_pLeft); 
    } 
    if(pt->m_pRight){ 
       cfun(pt->m_pRight); 
    } 
} 
//考虑用循环实现这个算法  
void MirrorIteratively(BSTreeNode *pTreeHead)   
{   
      if(!pTreeHead)   
            return;   
   
      std::stack<BSTreeNode *> stackTreeNode;   
      stackTreeNode.push(pTreeHead);   
   
      while(stackTreeNode.size())   
      {   
          BSTreeNode *pNode = stackTreeNode.top();   
          stackTreeNode.pop();   
   
          // swap the right and left child sub-tree    
          BSTreeNode *pTemp = pNode->m_pLeft;   
          pNode->m_pLeft = pNode->m_pRight;   
          pNode->m_pRight = pTemp;   
   
          // push left child sub-tree into stack if not null    
          if(pNode->m_pLeft)   
              stackTreeNode.push(pNode->m_pLeft);   
   
          // push right child sub-tree into stack if not null    
          if(pNode->m_pRight)   
              stackTreeNode.push(pNode->m_pRight);   
      }   
}    
//这个题目展示了递归变成循环的方法   
int main() 
{ 
 
    system("pause"); 
    return 0; 
} 

#include<iostream>
#include<iomanip>
#include<stack>
using namespace std;
//定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
void cfun(BSTreeNode *pt)
{
    if(!pt){
       return;
    }
    BSTreeNode * ptem=pt->m_pLeft;
    pt->m_pLeft=pt->m_pRight;
    pt->m_pRight=ptem;
    if(pt->m_pLeft){
       cfun(pt->m_pLeft);
    }
    if(pt->m_pRight){
       cfun(pt->m_pRight);
    }
}
//考虑用循环实现这个算法
void MirrorIteratively(BSTreeNode *pTreeHead) 
{ 
      if(!pTreeHead) 
            return; 
 
      std::stack<BSTreeNode *> stackTreeNode; 
      stackTreeNode.push(pTreeHead); 
 
      while(stackTreeNode.size()) 
      { 
          BSTreeNode *pNode = stackTreeNode.top(); 
          stackTreeNode.pop(); 
 
          // swap the right and left child sub-tree 
          BSTreeNode *pTemp = pNode->m_pLeft; 
          pNode->m_pLeft = pNode->m_pRight; 
          pNode->m_pRight = pTemp; 
 
          // push left child sub-tree into stack if not null 
          if(pNode->m_pLeft) 
              stackTreeNode.push(pNode->m_pLeft); 
 
          // push right child sub-tree into stack if not null 
          if(pNode->m_pRight) 
              stackTreeNode.push(pNode->m_pRight); 
      } 
}  
//这个题目展示了递归变成循环的方法
int main()
{

    system("pause");
    return 0;
}

补充：软件开发 , C++ ,

上一个：STM32 USB 问题汇总
下一个：三元组--数据结构