.void Count( BTreeNode * BT , int & C1 , int & C2 ) {
if ( BT != NULL ) {
C1++; // 统计所有结点数
if ( BT->left == NULL && BT->right == NULL ) C2++; // 统计叶子结点数 Count( BT->left , C1 , C2 ); Count( BT->right , C1 , C2 ); }
}
2 }
3.(1) abecfgkdhilmj (2) abcdefghijklm (3)
第六章 二叉树的应用
一、 单选题
1. C 2. B 3. D 4. C 5. A 6. D 二、填空题
1. 小于、大于等于 2. 按升序排列的有序序列 3. 找到、左子树、右子树 4. 2i+1、2i+2 5. 最小值、最大值 6. 堆尾、堆顶、向下 三、应用题 1.
2. 初态:空堆 ( ) 插入38后:( 38 ) 插入64后:( 38 , 64 ) 插入52后:( 38 , 64 , 52 ) 插入15后:( 15 , 38 , 52 , 64 ) 插入73后:( 15 , 38 , 52 , 64 , 73 ) 插入40后:( 15 , 38 , 40 , 64 , 73 , 52 )
插入48后:( 15 , 38 , 40 , 64 , 73 , 52 , 48 ) 插入55后:( 15 , 38 , 40 , 55 , 73 ,52 , 48 , 64 ) 插入26后:( 15 , 26 , 40 , 38 , 73 ,52 , 48 , 64 , 55 ) 插入12后:( 12 , 15 , 40 , 38 , 26 ,52 , 48 , 64 , 55 ,73 ) 3. 初态堆:( 12 , 15 , 40 , 38 , 26 ,52 , 48 , 64 ) 删除第1个元素后堆:( 15 , 26 , 40 , 38 , 64 , 52 , 48 ) 删除第2个元素后堆:( 26 , 38 , 40 , 48 , 64 , 52 ) 删除第3个元素后堆:( 38 , 48 , 40 , 52 , 64 ) 删除第4个元素后堆:( 40 , 48 , 64 , 52 ) 4. 哈夫曼树:
WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 131 四、算法设计
1.bool Find( BTreeNode * BST , ElemType & item )
{
while ( BST != NULL ) {
if ( item == BT->data ) { // 到
item = BST->data; return true;
}
else if (itemdata) BST=BST->left; // 找转