二叉树的镜像

纠正一下上图中的描述 只要当前节点有孩子就交换 也包括只有一个孩子的情况

递归代码

 void MirrTree(BtNode* ptr)
 {
	 //  树空             指向树的根节点为空
	 if(ptr == NULL)
		 return ;
	 //只有根 不需要交换
	 if(ptr->leftchild == NULL && ptr->rightchild == NULL)
		 return ;
	 BtNode* tmp = ptr->leftchild ;
	 ptr->leftchild = ptr->rightchild;
	 ptr->rightchild = tmp;
	 if(ptr->leftchild != NULL)
		 MirrTree(ptr->leftchild);
	 if(ptr->rightchild != NULL)
		 MirrTree(ptr->rightchild);

 }

利用栈实现非递归代码 

//利用栈实现非递归
 void swap(BtNode* ptr1,BtNode* ptr2)
 {
	 BtNode* tmp = ptr1;
	 ptr1 = ptr2;
	 ptr2 = tmp;
 }


 void MirrTree1(BtNode* ptr)
 {
	 if(ptr == NULL)
		 return ;
	 stack<BtNode*> st;
	 st.push(ptr);
	 while(!st.empty())
	 {
		 ptr = st.top();st.pop();
		 if(ptr->leftchild != NULL || ptr->rightchild != NULL)
		 {
			 swap(ptr->leftchild,ptr->rightchild);
		 }
		 if(ptr->leftchild != NULL)
			 st.push(ptr->leftchild);
		 if(ptr->rightchild != NULL)
			 st.push(ptr->rightchild);
	 }
 }

利用队列实现非递归

 //利用队列实现 非递归
 void MirrTree3(BtNode* ptr)
 {
	 if(ptr == NULL)
		 return ;
	 queue<BtNode*> qu;
	 qu.push(ptr);
	 while(!qu.empty())
	 {
		 ptr = qu.front();qu.pop();
		 if(ptr->leftchild != NULL || ptr->rightchild != NULL)
		 {
			 swap(ptr->leftchild,ptr->rightchild);
		 }
		 if(ptr->leftchild != NULL)
			 qu.push(ptr->leftchild);
		 if(ptr->rightchild != NULL)
			 qu.push(ptr->rightchild);
	 }
 }