0001 /******************************************************************************************
0002 * BTree输出打印
0003  ******************************************************************************************/
0004 #include "Bitmap/Bitmap.h" //使用位图记录分支转向
0005 
0006 template <typename T> void UniPrint::p(BTree<T>& bt) { //BTree打印（入口）
0007    printf("%s*%d/%d:\n", typeid(bt).name(), bt._N, bt._root->height); //基本信息
0008    Bitmap* leftmosts = new Bitmap; //记录当前节点祖先的方向
0009    Bitmap* rightmosts = new Bitmap; //记录当前节点祖先的方向
0010    printBTree(bt._root, 0, true, true, leftmosts, rightmosts); //输出树状结构
0011    delete leftmosts; delete rightmosts; printf("\n");
0012 }
0013 
0014 template <typename T> //BTree打印（递归）
0015 static void printBTree(BTNP<T> bt, int depth, bool isLeftmost, bool isRightmost, Bitmap* leftmosts, Bitmap* rightmosts) {
0016    if (!bt) return;
0017    isLeftmost ? leftmosts->set(depth) : leftmosts->clear(depth); //设置或清除当前层的拐向标志
0018    isRightmost ? rightmosts->set(depth) : rightmosts->clear(depth); //设置或清除当前层的拐向标志
0019    int k = bt->way.size()-1; //找到当前节点的最右侧孩子，并
0020    printBTree(bt->way[k], depth+1, false, true, leftmosts, rightmosts); //递归输出之
0021    while (0 < k--) { //自右向左，输出各子树及其右侧的关键码
0022       print(bt->key[k]); printf(" *>");
0023       for (int i = 0; i < depth; i++) //根据相邻各层
0024          (leftmosts->test(i) && leftmosts->test(i+1) || rightmosts->test(i) && rightmosts->test(i+1)) //的拐向是否一致，即可确定
0025             ? printf("     ")
0026             : printf("│    "); //是否应该打印横向联接线
0027       if (((0 == depth && 1 < bt->key.size()) || !isLeftmost && isRightmost) && bt->key.size() == k+1)
0028          printf("┌─");
0029       else if (((0 == depth && 1 < bt->key.size()) || isLeftmost && !isRightmost) && 0 == k)
0030          printf("└─");
0031       else
0032          printf("├─");
0033       print(bt->key[k]); printf(" (%2d)\n", bt->height);
0034       printBTree(bt->way[k], depth+1, 0 == k, false, leftmosts, rightmosts); //递归输出子树
0035    }
0036 } //printBTree