0001 #include <windows.h>
0002 #include "binTree_test.h"
0003 
0004 //随机生成期望高度为h的二叉树
0005 template <typename T> bool randomBinTree(BinTree<T>& A, BNP<T> x, Rank h) {
0006    if (-1 == h) return false; //至多h层
0007    if (0 < dice(h)) //以1/h的概率终止当前分支的生长
0008       randomBinTree(A, A.insert(x, dice(h*h*h)), h-1);
0009    if (0 < dice(h)) //以1/h的概率终止当前分支的生长
0010       randomBinTree(A, A.insert(dice(h*h*h), x), h-1);
0011    return true;
0012 }
0013 
0014 //在二叉树中随机确定一个节点位置
0015 template <typename T> BNP<T> randomPosiInBinTree(BNP<T> root) {
0016    if (IsLeaf(root)) return root;
0017    if (!root->lc)
0018       return dice((Rank) 6) ? randomPosiInBinTree(root->rc) : root;
0019    if (!root->rc)
0020       return dice((Rank) 6) ? randomPosiInBinTree(root->lc) : root;
0021    return dice((Rank) 2) ?
0022       randomPosiInBinTree(root->lc) :
0023       randomPosiInBinTree(root->rc) ;
0024 }
0025 
0026 template <typename T> void testBinTree(Rank h) {
0027    int testID = 0; //测试编号
0028 
0029    printf("\nTest %2d. Generate a binTree of height <= %d\n", testID++, h);
0030    BinTree<T> A;  print(A);
0031    A.insert(dice(h*h*h));  print(A);
0032    randomBinTree<T>(A, A.root(), h);  print(A);
0033 
0034    printf("\nTest %2d. Double and increase all nodes by traversal\n", testID++);
0035    A.traverse(Double<T>());  A.traverse(Increase<T>());  print(A);
0036 
0037    printf("\nTest %2d. Hailstone all nodes by traversal\n", testID++);
0038    Hailstone<T> hs;  A.traverse(hs);  print(A);
0039 
0040    printf("\nTest %2d. Create a MINI HART by attaching\n", testID++);
0041    BinTree<T> L(A), R(A);
0042    BNP<T> x;
0043    x = L.root();  while (x->lc) x = x->lc;  L.attach(A, x);  print(L); //A作为参数被深复制
0044    x = R.root();  while (x->rc) x = x->rc;  R.attach(x, A);  print(R);
0045 
0046    printf("\nTest %2d. Create a shadow by copying\n", testID++);
0047    BinTree<T> B(A);  print(B);
0048 
0049    printf("\nTest %2d. Create a BIG HART by attaching\n", testID++);
0050    x = B.root();  while (x->lc) x = x->lc;  B.attach(L, x); //A作为参数被深复制
0051    x = B.root();  while (x->lc) x = x->lc;  B.attach(L, x);
0052    x = B.root();  while (x->rc) x = x->rc;  B.attach(x, R); //A作为参数被深复制
0053    x = B.root();  while (x->rc) x = x->rc;  B.attach(x, R);
0054    print(B);
0055 
0056    printf("\nTest %2d. Remove subtrees\n", testID++);
0057    while (!B.empty()) {
0058       BNP<T> p = randomPosiInBinTree(B.root()); //随机选择一个节点
0059       if (dice((Rank) 2)) {
0060          printf("removing ");  print(p->data);  printf(" ...\n");
0061          printf("%d node(s) removed\n", B.remove(p));  print(B);
0062       } else {
0063          printf("releasing ");  print(p->data);  printf(" ...\n");
0064          BinTree<T> S = B.secede(p);  print(S);
0065          printf("%d node(s) released\n", S.size());  S.remove(S.root());  print(B);
0066       }
0067    }
0068 } //testBinTree
0069 
0070 int main(int argc, char* argv[]) {
0071    SetConsoleOutputCP(CP_UTF8);  SetConsoleCP(CP_UTF8);
0072    if (3 > argc) { printf("Usage: %s <depth> <tests>\a\a\n", argv[0]);  return 1; }
0073    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0074    Rank s = atoi(argv[1]), t = atoi(argv[2]);
0075    for (Rank k = 0; k < t; k++) {
0076       printf("\n[Round #%d/%d]\n", k, t);
0077       testBinTree<int>(s);
0078    }
0079    return 0;
0080 }