0001 #include "binTree_test.h" 0002 0003 int testID = 0; //测试编号 0004 0005 // 随机生成期望高度为h的二叉树 0006 template <typename T> bool randomBinTree ( BinTree<T> & bt, BinNodePosi(T) x, int h ) { 0007 if ( 0 >= h ) return false; //至多h层 0008 if ( 0 < dice ( h ) ) //以1/h的概率终止当前分支的生长 0009 randomBinTree ( bt, bt.insertAsLC ( x, dice ( ( T ) h * h * h ) ), h - 1 ); 0010 if ( 0 < dice ( h ) ) //以1/h的概率终止当前分支的生长 0011 randomBinTree ( bt, bt.insertAsRC ( x, dice ( ( T ) h * h * h ) ), h - 1 ); 0012 return true; 0013 } 0014 0015 // 在二叉树中随机确定一个节点位置 0016 template <typename T> BinNodePosi(T) randomPosiInBinTree ( BinNodePosi(T) root ) { 0017 if ( !HasChild ( *root ) ) return root; 0018 if ( !HasLChild ( *root ) ) 0019 return dice ( 6 ) ? randomPosiInBinTree ( root->rc ) : root; 0020 if ( !HasRChild ( *root ) ) 0021 return dice ( 6 ) ? randomPosiInBinTree ( root->lc ) : root; 0022 return dice ( 2 ) ? 0023 randomPosiInBinTree ( root->lc ) : 0024 randomPosiInBinTree ( root->rc ) ; 0025 } 0026 0027 template <typename T> void testBinTree ( int h ) { //测试二叉树 0028 printf ( "\n ==== Test %2d. Generate a binTree of height <= %d \n", testID++, h ); 0029 BinTree<T> bt; print ( bt ); 0030 bt.insertAsRoot ( dice ( ( T ) h * h * h ) ); print ( bt ); 0031 randomBinTree<T> ( bt, bt.root(), h ); print ( bt ); 0032 printf ( "\n ==== Test %2d. Double and increase all nodes by traversal\n", testID++ ); 0033 bt.travPre ( Double<T>() ); bt.travPre ( Increase<T>() ); print ( bt ); 0034 bt.travIn ( Double<T>() ); bt.travIn ( Increase<T>() ); print ( bt ); 0035 bt.travPost ( Double<T>() ); bt.travPost ( Increase<T>() ); print ( bt ); 0036 bt.travLevel ( Double<T>() ); bt.travLevel ( Increase<T>() ); print ( bt ); 0037 Hailstone<T> he; bt.travIn ( he ); print ( bt ); 0038 printf ( "\n ==== Test %2d. Remove/release subtrees in the Tree\n", testID++ ); 0039 while ( !bt.empty() ) { 0040 BinNodePosi(T) p = randomPosiInBinTree ( bt.root() ); //随机选择一个节点 0041 if ( dice ( 2 ) ) { 0042 printf ( "removing " ); print ( p->data ); printf ( " ...\n" ); 0043 printf ( "%d node(s) removed\n", bt.remove ( p ) ); print ( bt ); 0044 } else { 0045 printf ( "releasing " ); print ( p->data ); printf ( " ...\n" ); 0046 BinTree<T>* S = bt.secede ( p ); print ( S ); 0047 printf ( "%d node(s) released\n", S->size() ); release ( S ); print ( bt ); 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 testBinTree<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择 0056 return 0; 0057 }