0001 #include <windows.h>
0002 #include "BST/BST_test.h"
0003 
0004 //在子树t中，找到中序遍历次序为r的节点（从0开始编号）
0005 template <typename T> BNP<T> search(BNP<T> t, Rank k) {
0006    while (1) { //printf(" --> kth (%d)\t", r);
0007       Rank ls = t->lc ? t->lc->size() : 0;
0008       if (ls < k) { t = t->rc;  k = k-ls-1; }
0009       else if (k < ls) { t = t->lc; }
0010       else return t;
0011    }
0012 } //search
0013 
0014 //逐层伸展x，直到成为原祖先a的孩子
0015 template <typename T> BNP<T> splayTo(const BNP<T> a, BNP<T> x) {
0016    //printf(" --> splay(%d) : ", x->data);
0017    while (a != x->parent)
0018       IsLChild(x) ? x->parent->zig() : x->parent->zag();
0019    return x;
0020 } //splayTo
0021 
0022 //通过zig/zag变换，实现对X的临摹（使当前BST的姿势与X相同）
0023 template <typename T> BNP<T> BinNode<T>::imitate(const BNP<T> y) {
0024    BNP<T> s = splayTo(parent, search(this, y->lc ? y->lc->size() : 0));
0025    if (s->lc) s->lc->imitate(y->lc);
0026    if (s->rc) s->rc->imitate(y->rc);
0027    s->updateHeight();
0028    return s;
0029 } //imitate
0030 
0031 template <typename T> void testBST(Rank n) {
0032    BST<T> Y;  while (Y.size() < n) Y.insert(dice(n * 3));  print(Y); //随机创建
0033    BST<T> X;  while (X.size() < n) X.insert(dice(n * 3));  print(X); //随机创建
0034    X.imitate(Y); //临摹
0035    print(Y);  while (!Y.empty()) Y.remove (Y.root()->data); //清空
0036    print(X);  while (!X.empty()) X.remove (X.root()->data); //清空
0037 } //testBST
0038 
0039 int main(int argc, char* argv[]) {
0040    SetConsoleOutputCP(CP_UTF8);  SetConsoleCP(CP_UTF8);
0041    if (2 > argc) { printf("Usage: %s <size of test>\a\a\n", argv[0]);  return 1; }
0042    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0043    testBST<int>(atoi(argv[1]));
0044    return 0;
0045 } //main