100题_01 把二元查找树转变成排序的双向链表

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

10 /   \ 6     14 / \    / \ 4 8 12 16 转换成双向链表4=6=8=10=12=14=16。   分析：可以采用递归的思想，先将左子树转成双向列表，再将右子树转成双向列表，最后将这两个双向列表及根结点组首尾相接，组合成一个双向列表。   以下是实现的代码： BSTreeNode.h

#pragma  once #include  < cstdlib > using   namespace  std; class  BSTree; class  BSTreeNode { friend  class  BSTree; public : BSTreeNode( int  data, BSTreeNode  * rc  =  NULL, BSTreeNode  * lc  =  NULL); private : int  data; BSTreeNode  * rc; BSTreeNode  * lc; };

BSTreeNode.cpp

#include  " BSTreeNode.h " BSTreeNode::BSTreeNode( int  data, BSTreeNode  * rc, BSTreeNode  * lc) { this -> data  =  data; this -> lc  =  lc; this -> rc  =  rc; }

BSTree.h

#pragma  once #include  " BSTreeNode.h " class  BSTree { public : BSTree( void ); ~ BSTree( void ); void  insert( int  data); void  convertToDoubleList(); private : BSTreeNode *  root; void  del(BSTreeNode *  node); BSTreeNode *  convertToDoubleList(BSTreeNode  *& node); };

BSTree.cpp

#include  " BSTree.h " #include  < cstdlib > using   namespace  std; BSTree::BSTree( void ) { root  =  NULL; } void  BSTree::insert( int  data) { if  (root  ==  NULL) { root  =   new  BSTreeNode(data); } else { BSTreeNode  * cur,  * pre; pre  =  NULL; cur  =  root; while  ( true ) { pre  =  cur; if  (cur -> data  <=  data) { cur  =  cur -> rc; if  ( ! cur) { pre -> rc  =   new  BSTreeNode(data); break ; } } else { cur  =  cur -> lc; if  ( ! cur) { pre -> lc  =   new  BSTreeNode(data); break ; } } } } } BSTree:: ~ BSTree( void ) { } void  BSTree::del(BSTreeNode  * node) { if  (node  ==  NULL) return ; del(node -> lc); del(node -> rc); delete node; root  =  NULL; } BSTreeNode *  BSTree::convertToDoubleList(BSTreeNode *&  node) { if  (node  ==  NULL) return  NULL; BSTreeNode  * lf,  * lt,  * rf,  * rt,  * f,  * t; lf  =  node -> lc; rf  =  node -> rc; lt  =  convertToDoubleList(lf); rt  =  convertToDoubleList(rf); if  (lt  !=  NULL) { lt -> rc  =  node; f  =  lf; } else f  =  node; node -> lc  =  lt; node -> rc  =  rf; if  (rf  !=  NULL) { rf -> lc  =  node; t  =  rt; } else t  =  node; node  =  f; return  t; } void  BSTree::convertToDoubleList() { convertToDoubleList(root); }

main.cpp

#include  < iostream > #include  " BSTree.h " using   namespace  std; int  main() { BSTree tr; tr.insert( 10 ); tr.insert( 7 ); tr.insert( 8 ); tr.insert( 52 ); tr.convertToDoubleList(); return   0 ; }