题目
将一颗二叉搜索树变成排序的双向链表，要求只改动指针，不创建新的节点。
思路一
对于二元查找树（Binary Search Tree），其中序遍历的结果即为排序的结果，只需将此结果用双链表表示即可。根据中序遍历的思想， 对于当前节点而言，其左子树已经成功转换，接下来先将当前节点插入链表尾部，再处理其右子树。
伪代码
1.若当前节点为空,则处理结束,返回.
2.否则:
2.1递归处理左子树；
2.2将当前节点加入链表尾部；
2.3递归处理右子树；
代码
/*
* =====================================================================================
*
* Filename: bst2list.cpp
*
* Description: convert a BST into a sorted double linked list in place.
*
* Version: 1.0
* Created: 2011年08月24日 19时54分33秒
* Revision: none
* Compiler: gcc
*
* Author: XuDingxin (xdxn), xdxn2010@gmail.com
* Company: GUCAS
*
* =====================================================================================
*/
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
struct BSTreeNode
{
int m_nValue;
BSTreeNode *m_pLeft;
BSTreeNode *m_pRight;
};
typedef BSTreeNode DoubleList;
DoubleList *pHead;
DoubleList *pListIndex;
void convertToDoubleList(BSTreeNode *pCurrent);
void addBSTreeNode(BSTreeNode *&pCurrent, int value);
/**
* @brief add a new node to the current BST.
*
* @param pCurrent the root of the current BST.
* @param value the data element of the new node.
*/
void
addBSTreeNode (BSTreeNode *&pCurrent, int value )
{
if ( NULL == pCurrent ) {
BSTreeNode *pBSTree = new BSTreeNode();
pBSTree->m_pLeft = NULL;
pBSTree->m_pRight = NULL;
pBSTree->m_nValue = value;
pCurrent = pBSTree;
}
else {
if ( pCurrent->m_nValue > value ) {
addBSTreeNode(pCurrent->m_pLeft, value);
}
else if(pCurrent->m_nValue < value){
addBSTreeNode(pCurrent->m_pRight, value);
}
else {
cout << "ignore duplicate node" << endl;
}
}
return ;
} /* ----- end of function addBSTreeNode ----- */
/**
* @brief traverse the BST in inorder and form the double list accordingly.
*
* @param pCurrent the root of the current BST.
*/
void
ergodicBSTree ( BSTreeNode *pCurrent )
{
if(NULL == pCurrent) {
return;
}
if(NULL != pCurrent->m_pLeft){
ergodicBSTree(pCurrent->m_pLeft);
}
convertToDoubleList(pCurrent);
if(NULL != pCurrent->m_pRight) {
ergodicBSTree(pCurrent->m_pRight);
}
return ;
} /* ----- end of function ergodicBSTreeeNode ----- */
/**
* @brief add the current node into the doulbe list.
*
* @param pCurrent. the current node to be converted.
*/
void
convertToDoubleList (BSTreeNode *pCurrent )
{
pCurrent->m_pLeft = pListIndex;
if(NULL != pListIndex) {
pListIndex->m_pRight = pCurrent;
}else {
pHead = pCurrent;
}
pListIndex = pCurrent;
cout << pCurrent->m_nValue << endl;
return ;
} /* ----- end of function converToDoubleList ----- */
/*
* === FUNCTION ======================================================================
* Name: main
* Description:
* =====================================================================================
*/
int
main ( int argc, char *argv[] )
{
BSTreeNode *pRoot = NULL;
pHead = NULL;
pListIndex = NULL;
addBSTreeNode(pRoot, 10);
addBSTreeNode(pRoot, 4);
addBSTreeNode(pRoot, 6);
addBSTreeNode(pRoot, 8);
addBSTreeNode(pRoot, 12);
addBSTreeNode(pRoot, 14);
addBSTreeNode(pRoot, 15);
addBSTreeNode(pRoot, 16);
addBSTreeNode(pRoot, 1);
addBSTreeNode(pRoot, 18);
ergodicBSTree(pRoot);
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
思路二
上述方法虽然本质上用的是递归,但是硬要跟树的遍历扯上关系,有点含混不清.何不直接用一个纯脆的递归方法呢?
伪代码
BST2Dlist(root):
if root=null
then return null; #base case:null tree to null list.
else preList=BST2Dlist(left[root]);
postList=BST2Dlist(right[root]);
combine preList, root, and postList to form one double list.
源代码
/*
* =====================================================================================
*
* Filename: bst2list-3.cpp
*
* Description: convert a BST to sorted double list in place.
*
* Version: 1.0
* Created: 2011年09月10日 00时41分00秒
* Revision: none
* Compiler: gcc
*
* Author: Xu Dingxin (xdxn), xdxn2010@gmail.com
* Company: GUCAS
*
* =====================================================================================
*/
#include <stdlib.h>
#include <iostream>
using namespace std;
template <class T>
class Node
{
public:
T data;
Node *left;
Node *right;
Node(){
data = 0;
left = NULL;
right = NULL;
}
Node(T data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
/**
* @brief insert a new element to the BST.
*
* @param root reference to root of the BST.
* @param data data field of the new element.
*
* @return
*/
template <class T>
void TreeInsert(Node<T> *&root, T data)
{
if(root == NULL){
root = new Node<T>(data);
}else{
if ( data < root->data ) {
TreeInsert(root->left, data);
}else{
TreeInsert(root->right, data);
}
}
}
/**
* @brief traverse the BST in inorder.
*
* @param root
*/
template <class T>
void
InorderTraverse (Node<T> *root)
{
if ( root == NULL ) {
return;
}
InorderTraverse(root->left);
cout << root->data << "\t";
InorderTraverse(root->right);
return ;
} /* ----- end of function InorderTraverse ----- */
/**
* @brief traverse the BST in preorder.
*
* @param root
*/
template <class T>
void
PreOrderTraverse ( Node<T>* root )
{
if(root == NULL)
return;
cout << root->data << "\t";
PreOrderTraverse(root->left);
PreOrderTraverse(root->right);
return ;
} /* ----- end of function PreOrderTraverse ----- */
/**
* @brief traverse the BST in postorder.
*
* @param root
*/
template <class T>
void
PostOrderTraverse ( Node<T>* root )
{
if(root == NULL)
return;
PostOrderTraverse(root->left);
PostOrderTraverse(root->right);
cout << root->data << "\t";
return ;
} /* ----- end of function PostOrderTraverse ----- */
/**
* @brief convert the BST to a sorted double list.
*
* @param root root of BST.
*
* @return pointer to the list head.
*/
template <class T>
Node<T>*
BST2DList ( Node<T>* root )
{
if(root == NULL)
return NULL;
Node<T>* left = BST2DList(root->left);
Node<T>* right = BST2DList(root->right);
Node<T>* listHead;
if(left == NULL) {
listHead = root;
}else{
//append root to the left list.
listHead = left;
Node<T>* tmp = listHead;
while(tmp != NULL && tmp->right != NULL){
tmp = tmp->right;
}
tmp->right = root;
root->left = tmp;
}
if ( right != NULL ) {
root->right = right;
right->left = root;
}
return listHead;
} /* ----- end of function BST2DList ----- */
/**
* @brief append bNode to aNode.
*
* @param aNode
* @param bNode
*/
template <class T>
static void
Join ( Node<T>*aNode, Node<T>* bNode )
{
aNode->right = bNode;
bNode->left = aNode;
return ;
} /* ----- end of function Join ----- */
/**
* @brief append bList to aList.
*
* @param aList
* @param bList
*
* @return
*/
template <class T>
static Node<T>*
ListJoin ( Node<T>* aList, Node<T>*bList )
{
if(aList == NULL)
return bList;
if(bList == NULL)
return aList;
Node<T>* aLast = aList->left;
Node<T>* bLast = bList->left;
//append bList to aLast
aLast->right = bList;
bList->left = aLast;
//link bLast to aList to form a circular list..
bLast->right = aList;
aList->left = bLast;
return aList;
} /* ----- end of function ListJoin ----- */
/**
* @brief convert a BST to a sorted double circular list.
*
* @param root
*
* @return
*/
template <class T>
Node<T>*
BST2DCList ( Node<T>* root )
{
if(root == NULL)
return NULL;
char tmp;
Node<T>* left = BST2DCList(root->left);
Node<T>* right = BST2DCList(root->right);
//make the root node length-1 double circular list.
root->left = root;
root->right = root;
//combine the left, root and right sub-list.
left = ListJoin(left, root);
left = ListJoin(left, right);
return left;
} /* ----- end of function BST2DCList ----- */
/**
* @brief print double list.
*
* @param list
*/
template <class T>
void
PrintList ( Node<T>*list )
{
if(list == NULL)
return;
Node<T> *tmp = list;
while(tmp != NULL) {
cout << tmp->data << "\t";
tmp = tmp->right;
}
return ;
} /* ----- end of function PrintList ----- */
/**
* @brief print double circular list.
*
* @param list
*/
template <class T>
void
PrintDCList ( Node<T>* list )
{
if(list == NULL)
return;
Node<T>* tmp = list;
do{
cout << tmp->data << "\t";
tmp = tmp->right;
}while(tmp != list);
return ;
} /* ----- end of function PrintDCList ----- */
/*
* === FUNCTION ======================================================================
* Name: main
* Description:
* =====================================================================================
*/
int
main ( int argc, char *argv[] )
{
Node<int> *root = new Node<int>(10);
TreeInsert(root, 6);
TreeInsert(root, 8);
TreeInsert(root, 4);
TreeInsert(root, 12);
TreeInsert(root, 14);
TreeInsert(root, 16);
TreeInsert(root, 11);
InorderTraverse(root);
cout << endl;
PreOrderTraverse(root);
cout << endl;
PostOrderTraverse(root);
cout << endl;
//Node<int>* list = BST2DList(root);
//cout << "convertion result:" << endl;
//PrintList(list);
//cout << endl;
Node<int>* dclist = BST2DCList(root);
cout << "convertion result:" << endl;
PrintDCList(dclist);
cout << endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
注
在上述思路二中，提供了两种方法，即转换为普通双链表和带环双链表。
在普通双链表中，每次插入当前链表时需要遍历到链表尾端，耗时O(n)；在带环双链表中，可以直接从头结点找到尾结点，耗时为
常数时间。
Reference
1.http://blog.csdn.net/v_JULY_v/article/details/6057286
2.http://cslibrary.stanford.edu/109/TreeListRecursion.html
我写故我在 