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(), &bt, bt.size() ); //基本信息 0016 Bitmap* branchType = new Bitmap; //记录当前节点祖先的方向 0017 printBinTree ( bt.root(), -1, ROOT, branchType ); //树状结构 0018 release ( branchType ); 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(), &bt, bt.size() ); //基本信息 0027 Bitmap* branchType = new Bitmap; //记录当前节点祖先的方向 0028 printBinTree ( bt.root(), -1, ROOT, branchType ); //树状结构 0029 release ( branchType ); 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(), &avl, avl.size() ); //基本信息 0039 Bitmap* branchType = new Bitmap; //记录当前节点祖先的方向 0040 printBinTree ( avl.root(), -1, ROOT, branchType ); //树状结构 0041 release ( branchType ); 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(), &rb, rb.size() ); //基本信息 0051 Bitmap* branchType = new Bitmap; //记录当前节点祖先的方向 0052 printBinTree ( rb.root(), -1, ROOT, branchType ); //树状结构 0053 release ( branchType ); 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(), &bt, bt.size() ); //基本信息 0063 Bitmap* branchType = new Bitmap; //记录当前节点祖先的方向 0064 printBinTree ( bt.root(), -1, ROOT, branchType ); //树状结构 0065 release ( branchType ); 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 }