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