数据结构与算法面试题80道（15）-白红宇

数据结构与算法面试题80道（15）

阅读量：5884 次

发布时间：2019-06-19

本文共 1858 字，大约阅读时间需要 6 分钟。

第15题:

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

即在转换后的二元查找树中，左子树的结点都大于右子树的结点。

用递归和循环两种方法完成树的镜像转换。

例如输入:

/ \

6 10

/\ /\

5 7 9 11

输出:

/ \

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

};

挺简单的，直接上代码。都是套路

#include
     
      #include
      
       #include
       
        using namespace std;struct BSTreeNode{    int m_nValue;    BSTreeNode *m_pLeft;    BSTreeNode *m_pRight;};void addNode(BSTreeNode *&root,int value){    if(root==NULL){        BSTreeNode *tree=new BSTreeNode();        if(tree==NULL) {cout<<"内存错误"<
        
         m_nValue=value;        tree->m_pLeft=NULL;        tree->m_pRight=NULL;        root=tree;    }else if(root->m_nValue>value) addNode(root->m_pLeft,value);    else if(root->m_nValue
         
          m_pRight,value);    else cout<<"结点重复"<
          
           m_pLeft; root->m_pLeft=root->m_pRight; root->m_pRight=tree;}//递归方法求镜像void mirrorTree(BSTreeNode *root){ if(root==NULL) return ; mirrorTree(root->m_pLeft); mirrorTree(root->m_pRight); swap(root);}//可以用队列，也可以用栈，这里是用的队列，其实都是一样的，只是转换的顺序不同void loopMirrorTree(BSTreeNode *root){ queue
           
            q; q.push(root); while(!q.empty()){ BSTreeNode *t=q.front(); q.pop(); swap(t); if(t->m_pLeft!=NULL) q.push(t->m_pLeft); if(t->m_pRight!=NULL) q.push(t->m_pRight); }}//中序遍历看结果void inOrderTree(BSTreeNode *root){ if(root==NULL) return; if(root->m_pLeft!=NULL) inOrderTree(root->m_pLeft); cout<
            
             m_nValue<<" "; if(root->m_pLeft!=NULL) inOrderTree(root->m_pRight);}int main(){ //建树 BSTreeNode *root=NULL; addNode(root,8); addNode(root,6); addNode(root,10); addNode(root,5); addNode(root,7); addNode(root,9); addNode(root,11); //先中序遍历看结果 inOrderTree(root); cout<