0001 /****************************************************************************************** 0002 * Test of Binary Search Tree 0003 ******************************************************************************************/ 0004 #include "BST_test.h" 0005 0006 /****************************************************************************************** 0007 * Test a BST 0008 ******************************************************************************************/ 0009 template <typename T> void testBST ( Rank n ) { 0010 if ( n < 1 ) return; 0011 BST<T> bst; 0012 // 0013 while ( bst.size() < n ) bst.insert ( dice ( ( T ) n * 3 ) ); print ( bst ); //随机创建 0014 bst.stretchToLPath(); print ( bst ); //伸直成撇 0015 while ( !bst.empty() ) bst.remove ( bst.root()->data ); //清空 0016 // 0017 while ( bst.size() < n ) bst.insert ( dice ( ( T ) n * 3 ) ); print ( bst ); //随机创建 0018 bst.stretchToRPath(); print ( bst ); //伸直成捺 0019 while ( !bst.empty() ) bst.remove ( bst.root()->data ); //清空 0020 // 0021 while ( bst.size() < n ) bst.insert ( dice ( ( T ) n * 3 ) ); print ( bst ); //随机创建 0022 stretchByZig( bst.root()->lc ); //左子树伸直成捺 0023 stretchByZag( bst.root()->rc ); //右子树伸直成撇 0024 print ( bst ); 0025 while ( !bst.empty() ) bst.remove ( bst.root()->data ); //清空 0026 // 0027 while ( bst.size() < n ) bst.insert ( dice ( ( T ) n * 3 ) ); print ( bst ); //随机创建 0028 stretchByZag( bst.root()->lc ); //左子树伸直成撇 0029 stretchByZig( bst.root()->rc ); //右子树伸直成捺 0030 print ( bst ); 0031 while ( !bst.empty() ) bst.remove ( bst.root()->data ); //清空 0032 // 0033 while ( bst.size() < n ) { //随机插入、查询、删除 0034 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0035 switch ( dice ( 3 ) ) { 0036 case 0: { //查找,成功率 <= 33.3% 0037 printf ( "Searching for " ); print ( e ); printf ( " ... " ); 0038 BinNodePosi<T> & p = bst.search ( e ); 0039 p ? 0040 printf ( "Found with" ), print ( p->data ), printf ( "\n" ) : 0041 printf ( "not found\n" ); 0042 break; 0043 } 0044 case 1: { //删除,成功率 <= 33.3% 0045 printf ( "Removing " ); print ( e ); printf ( " ... " ); 0046 bst.remove ( e ) ? 0047 printf ( "Done\n" ), print ( bst ) : 0048 printf ( "not exists\n" ); 0049 break; 0050 } 0051 default: {//插入,成功率 == 100% 0052 printf ( "Inserting " ); print ( e ); printf ( " ... " ); 0053 printf ( "Done with" ), print ( bst.insert ( e )->data ), printf ( "\n" ), print ( bst ); 0054 break; 0055 } 0056 } 0057 } 0058 while ( bst.size() > 0 ) { //清空 0059 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0060 printf ( "Removing " ); print ( e ); printf ( " ... " ); 0061 bst.remove ( e ) ? printf ( "Done\n" ), print ( bst ) : printf ( "not exists\n" ); 0062 } 0063 } 0064 0065 /****************************************************************************************** 0066 * 测试主入口 0067 ******************************************************************************************/ 0068 int main ( int argc, char* argv[] ) { 0069 if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; } 0070 srand((unsigned int)time(NULL)); //随机种子 0071 //srand( 31415926 ); //固定种子(假种子,调试用) 0072 testBST<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择 0073 return 0; 0074 }