0001 #include "binTree_test.h"
0002 
0003 int testID = 0; //测试编号
0004 
0005 // 随机生成期望高度为h的二叉树
0006 template <typename T> bool randomBinTree ( BinTree<T> & btA, BinNodePosi<T> x, int h ) {
0007    if ( 0 >= h ) return false; //至多h层
0008    if ( 0 < dice ( h ) ) //以1/h的概率终止当前分支的生长
0009       randomBinTree ( btA, btA.insert ( x, dice ( ( T ) h * h * h ) ), h - 1 );
0010    if ( 0 < dice ( h ) ) //以1/h的概率终止当前分支的生长
0011       randomBinTree ( btA, btA.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 ( IsLeaf ( root ) ) return root;
0018    if ( !root->lc )
0019       return dice ( 6 ) ? randomPosiInBinTree ( root->rc ) : root;
0020    if ( !root->rc )
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> btA; print ( btA );
0030    btA.insert ( dice ( ( T ) h * h * h ) ); print ( btA );
0031    randomBinTree<T> ( btA, btA.root(), h ); print ( btA );
0032 
0033    printf ( "\n  ==== Test %2d. Double and increase all nodes by traversal\n", testID++ );
0034    btA.travPre ( Double<T>() ); btA.travPre ( Increase<T>() ); print ( btA );
0035    btA.travIn ( Double<T>() ); btA.travIn ( Increase<T>() ); print ( btA );
0036    btA.travPost ( Double<T>() ); btA.travPost ( Increase<T>() ); print ( btA );
0037    btA.travLevel ( Double<T>() ); btA.travLevel ( Increase<T>() ); print ( btA );
0038    Hailstone<T> hs; btA.travIn ( hs ); print ( btA );
0039 
0040    printf ( "\n  ==== Test %2d. Create a shadow by copying\n", testID++ );
0041    BinTree<T> btB( btA ); //等效：BinTree<T> btB = btA;
0042    print( btB );
0043 
0044    printf ( "\n  ==== Test %2d. Create a HART by attaching\n", testID++ );
0045    BinNodePosi<T> p;
0046    p = btB.root(); while (p->lc) p = p->lc; btB.attach( btA, p );
0047    p = btB.root(); while (p->lc) p = p->lc; btB.attach( btA, p );
0048    BinNodePosi<T> q;
0049    q = btB.root(); while (q->rc) q = q->rc; btB.attach( q, btA );
0050    q = btB.root(); while (q->rc) q = q->rc; btB.attach( q, btA );
0051    print( btB );
0052 
0053    printf ( "\n  ==== Test %2d. Remove subtrees\n", testID++ );
0054    while ( !btB.empty() ) {
0055       BinNodePosi<T> p = randomPosiInBinTree ( btB.root() ); //随机选择一个节点
0056       if ( dice ( 2 ) ) {
0057          printf ( "removing " ); print ( p->data ); printf ( " ...\n" );
0058          printf ( "%d node(s) removed\n", btB.remove ( p ) ); print ( btB );
0059       } else {
0060          printf ( "releasing " ); print ( p->data ); printf ( " ...\n" );
0061          BinTree<T>* S = btB.secede ( p ); print ( S );
0062          printf ( "%d node(s) released\n", S->size() ); S->remove(S->root()); print ( btB );
0063       }
0064    }
0065 }
0066 
0067 int main ( int argc, char* argv[] ) { //测试二叉树
0068    if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; }
0069    srand ( ( unsigned int ) time ( NULL ) );
0070    //srand( 31415926 ); //固定种子（假种子，调试用）
0071    testBinTree<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择
0072    return 0;
0073 }