0001 #include <windows.h>
0002 #include "BST_test.h"
0003 
0004 Rank testID = 0; //测试编号
0005 
0006 template <typename T> void testBST(Rank n) {
0007    if (n < 1) return;
0008    BST<T> bst;
0009 
0010    printf("\n  ==== Test %2d. stretchToLPath\n", testID++);
0011    while (bst.size() < n) bst.insert(dice(3*n));  print(bst); //随机创建
0012    bst.stretchToLPath();  print(bst); //伸直成撇
0013    while (!bst.empty()) bst.remove(bst.root()->data);  print(bst); //清空
0014 
0015    printf("\n  ==== Test %2d. stretchToRPath\n", testID++);
0016    while (bst.size() < n) bst.insert(dice(3 * n));
0017    print(bst); // 随机创建
0018    bst.stretchToRPath();  print(bst); //伸直成捺
0019    while (!bst.empty()) bst.remove(bst.root()->data); //清空
0020 
0021    printf("\n  ==== Test %2d. stretchTo[L+R]\n", testID++);
0022    while (bst.size() < n) bst.insert(dice(3*n));  print(bst); //随机创建
0023    stretchByZig(bst.root()->lc); //左子树伸直成捺
0024    stretchByZag(bst.root()->rc); //右子树伸直成撇
0025    bst.root()->updateHeight();
0026    print(bst);
0027    while (!bst.empty()) bst.remove(bst.root()->data); //清空
0028 
0029    printf("\n  ==== Test %2d. stretchTo[R+L]\n", testID++);
0030    while (bst.size() < n) bst.insert(dice(3*n));  print(bst); //随机创建
0031    stretchByZag(bst.root()->lc); //左子树伸直成撇
0032    stretchByZig(bst.root()->rc); //右子树伸直成捺
0033    bst.root()->updateHeight();
0034    print(bst);
0035    while (!bst.empty()) bst.remove(bst.root()->data); //清空
0036 
0037    printf("\n  ==== Test %2d. Insert + Search + Remove\n", testID++);
0038    while (bst.size() < n) { // 随机插入、查询、删除
0039       T e = dice(3*n); //[0, 3n)范围内的e
0040       switch (dice((Rank) 3)) {
0041          case 0: { //查找，成功率 <= 33.3%
0042             printf("search(");  print(e);  printf("):");
0043             BNP<T> p = bst.search(e);
0044             p ?
0045                printf("\tfound with"), print(p->data), printf("\n") :
0046                printf("\tnot found\n");
0047             break;
0048          }
0049          case 1: { //删除，成功率 <= 33.3%
0050             printf("remove(");  print(e);  printf("):");
0051             bst.remove(e) ?
0052                printf("\tdone\n"), print(bst) :
0053                printf("\tnot exists\n");
0054             break;
0055          }
0056          default: {//插入，成功率 == 100%
0057             printf("insert(");  print(e);  printf("):");
0058             BNP<T> x = bst.insert(e);
0059             printf("\tdone with"), print(x), printf("\n");
0060             print(bst);
0061             break;
0062          }
0063       }
0064    }
0065    while (bst.size() > 0) { //清空
0066       printf("removeRoot():");
0067       bst.remove(bst.root()->data);
0068       printf("\tdone\n");
0069       print(bst);
0070    }
0071 } //testBST
0072 
0073 int main(int argc, char* argv[]) {
0074    SetConsoleOutputCP(CP_UTF8);  SetConsoleCP(CP_UTF8);
0075    if (3 > argc) { printf("Usage: %s <size> <tests> \a\a\n", argv[0]);  return 1; }
0076    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0077    Rank s = atoi(argv[1]), t = atoi(argv[2]);
0078    for (Rank k = 0; k < t; k++) {
0079       printf("\n[Test #%d/%d]\n", k, t);
0080       testBST<int>(s);
0081    }
0082    return 0;
0083 }