0001 /******************************************************************************************
0002 * 二叉树输出打印
0003  ******************************************************************************************/
0004 #include "Bitmap/Bitmap.h" //使用位图记录分支转向
0005 
0006 constexpr int ROOT = 0;
0007 constexpr int L_CHILD = +1;
0008 constexpr int R_CHILD = -1;
0009 
0010 template <typename T> void UniPrint::p(BinTree<T>& bt) { //基础BinTree
0011    printf("%s*%d/%d:\n", typeid(bt).name(), bt.size(), bt.root() ? bt.root()->height : -1); //基本信息
0012    Bitmap branchType; //记录当前节点祖先的方向
0013    printBinTree(bt.root(), -1, ROOT, &branchType); //树状结构
0014    printf("\n");
0015 }
0016 
0017 template <typename T> void UniPrint::p(BST<T>& bst) { //基于BinTree实现的BST
0018    printf("%s*%d/%d:\n", typeid(bst).name(), bst.size(), bst.root() ? bst.root()->height : -1); //基本信息
0019    Bitmap branchType; //记录当前节点祖先的方向
0020    printBinTree(bst.root(), -1, ROOT, &branchType); //树状结构
0021    printf("\n");
0022 }
0023 
0024 template <typename T> void UniPrint::p(AVL<T>& avl) { //基于BST实现的AVL
0025    printf("%s*%d/%d:\n", typeid(avl).name(), avl.size(), avl.root() ? avl.root()->height : -1); //基本信息
0026    Bitmap branchType; //记录当前节点祖先的方向
0027    printBinTree(avl.root(), -1, ROOT, &branchType); //树状结构
0028    printf("\n");
0029 }
0030 
0031 template <typename T> void UniPrint::p(RedBlack<T>& rbt) { //基于BST实现的RedBlack
0032    printf("%s*%d/%d:\n", typeid(rbt).name(), rbt.size(), rbt.root() ? rbt.root()->height : 0); //基本信息
0033    Bitmap branchType; //记录当前节点祖先的方向
0034    printBinTree(rbt.root(), -1, ROOT, &branchType); //树状结构
0035    printf("\n");
0036 }
0037 
0038 template <typename T> void UniPrint::p(Splay<T>& spl) { //基于BST实现的Splay
0039    printf("%s*%d/%d:\n", typeid(spl).name(), spl.size(), spl.root() ? spl.root()->height : -1); //基本信息
0040    Bitmap branchType; //记录当前节点祖先的方向
0041    printBinTree(spl.root(), -1, ROOT, &branchType); //树状结构
0042    printf("\n");
0043 }
0044 
0045 // 二叉树各种派生类的统一打印
0046 template <typename T> void printBinTree(BNP<T> t, int depth, int type, Bitmap* bType) {
0047    if (!t) return;
0048    if (-1 < depth) //设置当前层的拐向标志
0049       R_CHILD == type ? bType->set(depth) : bType->clear(depth);
0050    printBinTree(t->rc, depth+1, R_CHILD, bType); //右子树（在上）
0051    print(t); printf(" *");
0052    for (int i = -1; i < depth; i++) //根据相邻各层
0053       if ((0 > i) || bType->test(i) == bType->test(i+1)) //的拐向是否一致，即可确定
0054          printf("      "); //是否应该
0055       else  printf("│     "); //打印横线
0056    switch (type) {
0057       case  R_CHILD  :  printf("┌─");  break;
0058       case  L_CHILD  :  printf("└─");  break;
0059       default        :  printf("──");  break; //root
0060    }
0061    print(t);
0062 #if defined(DSA_HUFFMAN)
0063    if (IsLeaf(t)) bType->print(depth+1); //输出Huffman编码
0064 #endif
0065    printf("\n");
0066    printBinTree(t->lc, depth+1, L_CHILD, bType); //左子树（在下）
0067 }