【C/C++练习题】二叉树的镜像

《剑指Offer》面试题27：二叉树的镜像

1 题目

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

2 代码

  

   

    

     

    
    

     

      #include "iostream"
     
    
   

    

     

    
    

     

      #include "cstdlib"
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //问题：二叉树的镜像
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct Node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int m_nValue;
     
    
   

    

     

    
    

     

      	Node* m_pLeft;
     
    
   

    

     

    
    

     

      	Node* m_pRight;
     
    
   

    

     

    
    

     

      }BinaryTreeNode;		
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：利用递归方式实现打印二叉树的镜像
     
    
   

    

     

    
    

     

      //输入：
     
    
   

    

     

    
    

     

      //返回：
     
    
   

    

     

    
    

     

      void Mirror_btree(BinaryTreeNode* pNode)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.回归条件1，空指针pNode（也检查参数有效性）
     
    
   

    

     

    
    

     
	if (nullptr == pNode)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return ;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//2.回归条件2，叶子节点
     
    
   

    

     

    
    

     
	if (nullptr == pNode->m_pLeft && nullptr == pNode->m_pRight)
     
    
   

    

     

    
    

     

      	{//
     
    
   

    

     

    
    

     
		return ;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//4.至上而下，交换左右子树
     
    
   

    

     

    
    

     

      	BinaryTreeNode* pTemp = pNode->m_pLeft;
     
    
   

    

     

    
    

     

      	pNode->m_pLeft = pNode->m_pRight;
     
    
   

    

     

    
    

     

      	pNode->m_pRight = pTemp;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//3.进行递归调用
     
    
   

    

     

    
    

     
	Mirror_btree(pNode->m_pLeft);
     
    
   

    

     

    
    

     
	Mirror_btree(pNode->m_pRight);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //先序打印二叉树
     
    
   

    

     

    
    

     

      void Print_Btree(BinaryTreeNode* pNode)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.回归条件1，空指针pNode（也检查参数有效性）
     
    
   

    

     

    
    

     
	if (nullptr == pNode)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return ;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//2.打印二叉树
     
    
   

    

     

    
    

     

      	cout << pNode->m_nValue << ",";
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//3.进行递归调用
     
    
   

    

     

    
    

     
	Print_Btree(pNode->m_pLeft);
     
    
   

    

     

    
    

     
	Print_Btree(pNode->m_pRight);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      // ====================测试代码====================
     
    
   

    

     

    
    

     

      // 测试完全二叉树：除了叶子节点，其他节点都有两个子节点
     
    
   

    

     

    
    

     

      // 8(node1)
     
    
   

    

     

    
    

     

      // 6(node2) 10(node3)
     
    
   

    

     

    
    

     

      // 5(node4) 7(node5) 9(node6) 11(node7)
     
    
   

    

     

    
    

     

      void test01()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node1  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node2  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node3  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node4  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node5  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node6  = new BinaryTreeNode();
     
    
   

    

     

    
    

     

      	BinaryTreeNode* node7  = new BinaryTreeNode();
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node1
     
    
   

    

     

    
    

     

      	node1->m_nValue = 8;
     
    
   

    

     

    
    

     

      	node1->m_pLeft = node2;
     
    
   

    

     

    
    

     

      	node1->m_pRight = node3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node2
     
    
   

    

     

    
    

     

      	node2->m_nValue = 6;
     
    
   

    

     

    
    

     

      	node2->m_pLeft = node4;
     
    
   

    

     

    
    

     

      	node2->m_pRight = node5;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node3
     
    
   

    

     

    
    

     

      	node3->m_nValue = 10;
     
    
   

    

     

    
    

     

      	node3->m_pLeft = node6;
     
    
   

    

     

    
    

     

      	node3->m_pRight = node7;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node4
     
    
   

    

     

    
    

     

      	node4->m_nValue = 5;
     
    
   

    

     

    
    

     

      	node4->m_pLeft = nullptr;
     
    
   

    

     

    
    

     

      	node4->m_pRight = nullptr;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node5
     
    
   

    

     

    
    

     

      	node5->m_nValue = 7;
     
    
   

    

     

    
    

     

      	node5->m_pLeft = nullptr;
     
    
   

    

     

    
    

     

      	node5->m_pRight = nullptr;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node6
     
    
   

    

     

    
    

     

      	node6->m_nValue = 9;
     
    
   

    

     

    
    

     

      	node6->m_pLeft = nullptr;
     
    
   

    

     

    
    

     

      	node6->m_pRight = nullptr;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//node7
     
    
   

    

     

    
    

     

      	node7->m_nValue = 11;
     
    
   

    

     

    
    

     

      	node7->m_pLeft = nullptr;
     
    
   

    

     

    
    

     

      	node7->m_pRight = nullptr;	
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//测试部分
     
    
   

    

     

    
    

     
	Print_Btree(node1);
     
    
   

    

     

    
    

     

      	cout << endl;
     
    
   

    

     

    
    

     
	Mirror_btree(node1);
     
    
   

    

     

    
    

     
	Print_Btree(node1);
     
    
   

    

     

    
    

     

      	cout << endl;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	delete node1;delete node2;
     
    
   

    

     

    
    

     
	delete node3;delete node4;
     
    
   

    

     

    
    

     
	delete node5;delete node6;
     
    
   

    

     

    
    

     
	delete node7;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char const *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	test01();
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

3 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/99195146