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.insert ( x, dice ( ( T ) h * h * h ) ), h - 1 );
0010    if ( 0 < dice ( h ) ) //以1/h的概率终止当前分支的生长
0011       randomBinTree ( bt, bt.insert ( dice ( ( T ) h * h * h ), x ), 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.insert ( 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> hs; bt.travIn ( hs ); 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    //srand( 31415926 ); //固定种子（假种子，调试用）
0056    testBinTree<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择
0057    return 0;
0058 }