## 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
};
下面是使用C++泛型写的一种算法：
#include "stdafx.h"
#include <string>
#include <iostream>
using namespace std; template<typename T>
struct BSTTreeNode
{
BSTTreeNode(T v, BSTTreeNode* lNode = NULL, BSTTreeNode* rNode=NULL)
:m_Value(v), m_pLeft(lNode), m_pRight(rNode){}
T m_Value;
BSTTreeNode* m_pLeft;
BSTTreeNode* m_pRight;
}; template<typename T>
void TravelBSTree(BSTTreeNode<T> *root)
{
if (NULL == root)
{
return;
} TravelBSTree(root->m_pLeft); printf("%d ", root->m_Value); TravelBSTree(root->m_pRight); } template<typename T>
void TravelBSTreeAsList(BSTTreeNode<T> *head, bool bReverseTravel = false)
{
BSTTreeNode<T>* pNode = head;
while (pNode)
{
printf("%d ", pNode->m_Value);
if (!bReverseTravel)
{
pNode = pNode->m_pRight;
}
else
{
pNode = pNode->m_pLeft;
}
}
} //思路：
//查找树，中序遍历得到的节点排序即为排序的链表，而要求排序的双向链表，
//1. 假设lt为左子树的中序遍历的尾结点，rh为右子树中序遍历的头结点
//2. 化繁为简，如果只有root, lt, rh三个节点，此时只须然这几个节点连接起来即可。
//3. 分别遍历左右子树，重复上述过程。
template<typename T>
void BSTreeHelper(BSTTreeNode<T>* &head, BSTTreeNode<T>* &tail, BSTTreeNode<T>* root)
{
//step 1.
BSTTreeNode<T>* lt = NULL;//左子树尾结点
BSTTreeNode<T>* rh = NULL;//右子树头结点 if (NULL == root)
{
head = nullptr;
tail = nullptr;
return;
} //step 3.
BSTreeHelper(head, lt, root->m_pLeft);
BSTreeHelper(rh, tail, root->m_pRight); //step 2.
if (NULL != lt)
{
lt->m_pRight = root;
root->m_pLeft = lt;
}
else
{
head = root;
} if (NULL != rh)
{
root->m_pRight = rh;
rh->m_pLeft = root;
}
else
{
tail = root;
}
} template<typename T>
BSTTreeNode<T>* TreeToLinkedList(BSTTreeNode<T>* root)
{
BSTTreeNode<T>* head = NULL;
BSTTreeNode<T>* tail = NULL; BSTreeHelper(head, tail, root); return head;
} int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = {, , , , , , }; BSTTreeNode<int> node4();
BSTTreeNode<int> node8();
BSTTreeNode<int> node6(, &node4, &node8);
BSTTreeNode<int> node12();
BSTTreeNode<int> node16();
BSTTreeNode<int> node14(, &node12, &node16);
BSTTreeNode<int> node10(, &node6, &node14);
BSTTreeNode<int>* pRoot = &node10; printf("Travel BSTree: \n");
TravelBSTree<int>(pRoot);
printf("\n"); TreeToLinkedList<int>(pRoot); printf("Travel BSTree: \n");
TravelBSTreeAsList<int>(&node4, false);
printf("\n"); TravelBSTreeAsList<int>(&node16, true);
printf("\n"); return ;
}