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(), &bt, bt.size() ); //基本信息 0012 Bitmap* leftmosts = new Bitmap; //记录当前节点祖先的方向 0013 Bitmap* rightmosts = new Bitmap; //记录当前节点祖先的方向 0014 printBTree ( bt.root(), 0, true, true, leftmosts, rightmosts ); //输出树状结构 0015 release ( leftmosts ); release ( 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 }