二元查找树到双向链表的转换

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

　　比如将二元查找树
                                            10
                                          /    \
                                        6       14
                                      /  \     /　 \
                                   　4     8  12 　  16
转换成双向链表

4=6=8=10=12=14=16。

 

思路：
 本题的基本解题思路是使用递归，对于二元查找树的某个节点node, 递归的转换左子树和右子树为双向链表，然后将左子树的最大值,node本身, 右子树的最小值再顺序连接起来。

 

代码：
struct BSTreeNode  // Node Of Binary Search Tree
{
 int                 _value; // node content
 struct BSTreeNode  *_left;  // left child of node
 struct BSTreeNode  *_right; // right child of node
};

typedef pair TreeNodePair;

///////////////////////////////////////////////////////
/// Convert Binary Search Tree to Double LinkList
///
/// Input:
///         root - root node of Binary Search Tree
/// Output:
///         first node of Converted Double LinkList
///////////////////////////////////////////////////////
struct BSTreeNode* BSTreeToDBLinkList(struct BSTreeNode *root)
{
 // nodePair.first is minimum node of tree,
 // nodepair.second is maximum node of tree
 TreeNodePair nodePair;
 nodePair = ConvertNode(root);
 
 return nodePair.first;
}

///////////////////////////////////////////////////////
/// Convert a sub Binary Search Tree to Double LinkList
///
/// Input:
///         root - root node of sub Binary Search Tree
/// Output:
///         pair of BSTreeNode, first element is minimum
///         node of tree, second element is maximum node
///         of tree
///////////////////////////////////////////////////////
TreeNodePair ConvertNode(struct BSTreeNode *root)
{
 TreeNodePair tempPair, resultPair;
 
 if(root->_left != NULL)
 {
  tempPair = ConvertNode(root->_left);
  root->_left = tempPair.second;
  tempPair.second->_right = root;
 }
 else
 {
  resultPair.first = root;
 }
 
 if(root->_right != NULL)
 {
  tempPair = ConvertNode(root->_right);
  root->_right = tempPair.first;
  tempPair.first->_left = root;
 }
 else
 {
  resultPair.second = root;
 }
 
 return resultPair;
}