0001 /******************************************************************************************
0002  * 二叉树输出打印
0003  ******************************************************************************************/
0004 #include "Bitmap/Bitmap.h" //使用位图记录分支转向
0005 
0006 #define ROOT 0
0007 #define L_CHILD 1
0008 #define R_CHILD -1*L_CHILD
0009 
0010 /******************************************************************************************
0011  * 基础BinTree
0012  ******************************************************************************************/
0013 template <typename T> //元素类型
0014 void UniPrint::p ( BinTree<T> & bt ) { //引用
0015    printf ( "%s[%d]*%d:\n", typeid ( bt ).name(), (int) &bt, bt.size() ); //基本信息
0016    Bitmap branchType; //记录当前节点祖先的方向
0017    printBinTree ( bt.root(), -1, ROOT, &branchType ); //树状结构
0018    printf ( "\n" );
0019 }
0020 
0021 /******************************************************************************************
0022  * 基于BinTree实现的BST
0023  ******************************************************************************************/
0024 template <typename T> //元素类型
0025 void UniPrint::p ( BST<T> & bt ) { //引用
0026    printf ( "%s[%d]*%d:\n", typeid ( bt ).name(), (int) &bt, bt.size() ); //基本信息
0027    Bitmap branchType; //记录当前节点祖先的方向
0028    printBinTree ( bt.root(), -1, ROOT, &branchType ); //树状结构
0029    printf ( "\n" );
0030 }
0031 
0032 /******************************************************************************************
0033  * 基于BST实现的AVL
0034  * 其中调用的BinNode的打印例程，可以显示BF状态
0035  ******************************************************************************************/
0036 template <typename T> //元素类型
0037 void UniPrint::p ( AVL<T> & avl ) { //引用
0038    printf ( "%s[%d]*%d:\n", typeid ( avl ).name(), (int) &avl, avl.size() ); //基本信息
0039    Bitmap branchType; //记录当前节点祖先的方向
0040    printBinTree ( avl.root(), -1, ROOT, &branchType ); //树状结构
0041    printf ( "\n" );
0042 }
0043 
0044 /******************************************************************************************
0045  * 基于BST实现的RedBlack
0046  * 其中调用的BinNode的打印例程，可以显示BF状态
0047  ******************************************************************************************/
0048 template <typename T> //元素类型
0049 void UniPrint::p ( RedBlack<T> & rb ) { //引用
0050    printf ( "%s[%d]*%d:\n", typeid ( rb ).name(), (int) &rb, rb.size() ); //基本信息
0051    Bitmap branchType; //记录当前节点祖先的方向
0052    printBinTree ( rb.root(), -1, ROOT, &branchType ); //树状结构
0053    printf ( "\n" );
0054 }
0055 
0056 /******************************************************************************************
0057  * 基于BST实现的Splay
0058  * 鉴于Splay不必设置bf之类的附加标识，其打印例程与BST完全一致
0059  ******************************************************************************************/
0060 template <typename T> //元素类型
0061 void UniPrint::p ( Splay<T> & bt ) { //引用
0062    printf ( "%s[%d]*%d:\n", typeid ( bt ).name(), (int) &bt, bt.size() ); //基本信息
0063    Bitmap branchType; //记录当前节点祖先的方向
0064    printBinTree ( bt.root(), -1, ROOT, &branchType ); //树状结构
0065    printf ( "\n" );
0066 }
0067 
0068 /******************************************************************************************
0069  * 二叉树各种派生类的统一打印
0070  ******************************************************************************************/
0071 template <typename T> //元素类型
0072 static void printBinTree ( BinNodePosi<T> bt, int depth, int type, Bitmap* bType ) {
0073    if ( !bt ) return;
0074    if ( -1 < depth ) //设置当前层的拐向标志
0075       R_CHILD == type ? bType->set ( depth ) : bType->clear ( depth );
0076    printBinTree ( bt->rc, depth + 1, R_CHILD, bType ); //右子树（在上）
0077    print ( bt ); printf ( " *" );
0078    for ( int i = -1; i < depth; i++ ) //根据相邻各层
0079       if ( ( 0 > i ) || bType->test ( i ) == bType->test ( i + 1 ) ) //的拐向是否一致，即可确定
0080          printf ( "      " ); //是否应该
0081       else  printf ( "│    " ); //打印横线
0082    switch ( type ) {
0083       case  R_CHILD  :  printf ( "┌─" );  break;
0084       case  L_CHILD  :  printf ( "└─" );  break;
0085       default        :  printf ( "──" );  break; //root
0086    }
0087    print ( bt );
0088 #if defined(DSA_HUFFMAN)
0089    if ( IsLeaf ( bt ) ) bType->print ( depth + 1 ); //输出Huffman编码
0090 #endif
0091    printf ( "\n" );
0092    printBinTree ( bt->lc, depth + 1, L_CHILD, bType ); //左子树（在下）
0093 }