学步园

1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
   		   	  10
			/    \
		   6     14
		 /   \  /   \
		4    8 12   16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下：

struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node 
BSTreeNode *m_pRight; // right child of node
};

//二叉树转换成双向链表
BSTreeNode *treeToLinkedList(BSTreeNode *root )
{
	BSTreeNode *head,*tail;
	help(head,tail,root);
	return head;
} 

//root根节点，返回head、tail分别为双向链表的头尾节点  
//函数helper将root子树在中序下的头赋值给head，把尾赋值给tail。
//函数负责把root和左子树的tail及右子树的head连接。
void help(BSTreeNode *&head,BSTreeNode *&tail,BSTreeNode *&root)
{
	BSTreeNode *lt,*rh;
	if(root==NULL)
	{
		head=NULL;
		tail=NULL;
		return ;
	}
	help(head,lt,root->m_pLeft);
	help(rh,tail,root->m_pRight);
	
左节点和根节点调整关系 
	   		  10
			/    \
		   6     14
		 /   \  /   \
		4    8 12   16
相当于左子树的4 6 8 调整成 
	  		  8
			/ 
		   6     
		 /     
		4     
	if(lt!=NULL)
	{
		lt->m_pRight=root;
		root->m_pLeft=lt;
		
	}
	else
	{
		head=root;
	}
	//右节点和根节点调整关系  
	左节点和根节点调整关系 
	   		  10
			/    \
		   6     14
		 /   \  /   \
		4    8 12   16
相当于右子树的12 14 16 调整成 
	  		  12
			     \
		         14
		            \
		            16
	if(rh!=NULL)
	{
		root->m_pRight=rh;
		rh->m_pLeft=root;	
	}
	else
	{
		tail=NULL;
	}
}