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 ( int n ) { 0010 BST<T> bst; 0011 while ( bst.size() < n ) bst.insert ( dice ( ( T ) n * 3 ) ); print ( bst ); //随机创建 0012 bst.stretchToLPath(); print ( bst ); //伸直成撇 0013 while ( !bst.empty() ) bst.remove ( bst.root()->data ); //清空 0014 while ( bst.size() < n ) bst.insert ( dice ( ( T ) n * 3 ) ); print ( bst ); //随机创建 0015 bst.stretchToRPath(); print ( bst ); //伸直成捺 0016 while ( !bst.empty() ) bst.remove ( bst.root()->data ); //清空 0017 while ( bst.size() < n ) { //随机插入、查询、删除 0018 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0019 switch ( dice ( 3 ) ) { 0020 case 0: { //查找,成功率 <= 33.3% 0021 printf ( "Searching for " ); print ( e ); printf ( " ... " ); 0022 BinNodePosi(T) & p = bst.search ( e ); 0023 p ? 0024 printf ( "Found with" ), print ( p->data ), printf ( "\n" ) : 0025 printf ( "not found\n" ); 0026 break; 0027 } 0028 case 1: { //删除,成功率 <= 33.3% 0029 printf ( "Removing " ); print ( e ); printf ( " ... " ); 0030 bst.remove ( e ) ? 0031 printf ( "Done\n" ), print ( bst ) : 0032 printf ( "not exists\n" ); 0033 break; 0034 } 0035 default: {//插入,成功率 == 100% 0036 printf ( "Inserting " ); print ( e ); printf ( " ... " ); 0037 printf ( "Done with" ), print ( bst.insert ( e )->data ), printf ( "\n" ), print ( bst ); 0038 break; 0039 } 0040 } 0041 } 0042 while ( bst.size() > 0 ) { //清空 0043 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0044 printf ( "Removing " ); print ( e ); printf ( " ... " ); 0045 bst.remove ( e ) ? printf ( "Done\n" ), print ( bst ) : printf ( "not exists\n" ); 0046 } 0047 } 0048 0049 /****************************************************************************************** 0050 * 测试主入口 0051 ******************************************************************************************/ 0052 int main ( int argc, char* argv[] ) { 0053 if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; } 0054 srand ( ( unsigned int ) time ( NULL ) ); 0055 testBST<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择 0056 return 0; 0057 }