【100题】第十五题（树的镜像问题）

一，题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入：
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
};

二，分析：

采用递归方法，比较简单。主要是采用循环方法时候采用压栈的方式来模拟递归

三，源码（递归）：

#include"stdio.h"
#include"malloc.h"

struct node
{
	int data;
	node *right;
	node *left;
};
node *root;
void insert(node *&root,int data)
{	
	if(root==NULL)
    {
	    	printf("%d\n",data);   
            root=(node*)malloc(sizeof(node)); 
	    	root->data=data;
	        root->right=NULL;
	        root->left=NULL;
	}
    else
    {    
    	if(root->data<data)//要插入的数据 data大于节点 则插入右边 
            insert(root->right,data);
        else
            insert(root->left,data);
    }
}
node *creatTree(int a[],int n)
{   
    int i;   	 	 	
	for(i=0;i<n;i++)	 			    	
	    insert(root,a[i]);	
	return root;
}
void outPut(node *root)//先序遍历树 
{
	if(root==NULL)
       return;
	else//不是空
	{
        printf("data=%d\n",root->data);
		outPut(root->left);
		outPut(root->right); 
	} 	
}
void Revertsetree(node *&root)//获取二叉查找树的镜像 
{
    if(!root)
       return;
    node *p;
    p=root->left;
    root->left=root->right;
    root->right=p;
    
    if(root->left)
      Revertsetree(root->left);
    if(root->right)
      Revertsetree(root->right);
}
int main()
{
	int a[]={8,6,5,7,10,9,11};
	root=creatTree(a,7);
    Revertsetree(root);
	outPut(root);
	return 0;
} 

源码（循环）：

#include "stdio.h"
#include "malloc.h"
#include "stack.h"
struct node
{
	int data;
	node *right;
	node *left;
};
node *root;
void insert(node *&root,int data)
{	
	if(root==NULL)
    {
	    	printf("%d\n",data);   
            root=(node*)malloc(sizeof(node)); 
	    	root->data=data;
	        root->right=NULL;
	        root->left=NULL;
	}
    else
    {    
    	if(root->data<data)//要插入的数据 data大于节点 则插入右边 
            insert(root->right,data);
        else
            insert(root->left,data);
    }
}
node *creatTree(int a[],int n)
{   
    int i;   	 	 	
	for(i=0;i<n;i++)	 			    	
	    insert(root,a[i]);	
	return root;
}
void outPut(node *root)//先序遍历树 
{
	if(root==NULL)
       return;
	else//不是空
	{
        printf("data=%d\n",root->data);
		outPut(root->left);
		outPut(root->right); 
	} 	
}
void Revertsetree(node *&phead)//采用循环的方式 
{
    if(!phead)
       return;
    stack<node*> stacklist;
    stacklist.push(phead);         //首先把树的头结点放入栈中。
    while(stacklist.size())
    //在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树
    {
      node* pnode=stacklist.top(); 
      stacklist.pop();
   
      node *ptemp;
      ptemp=pnode->left;
      pnode->left=pnode->right;
      pnode->right=ptemp;
      if(pnode->left)
        stacklist.push(pnode->left);   //若有左子树，把它的左子树压入栈中
      if(pnode->right)
        stacklist.push(pnode->right);  //若有右子树，把它的右子树压入栈中
    }
}

int main()
{
	int a[]={8,6,5,7,10,9,11};
	root=creatTree(a,7);
        Revertsetree(root);//采用循环的方式 
	outPut(root);
	return 0;
}