河南厂播电现大学现数中心 第六章树和二叉树课后习题答案 1、单项选择题 (1)B (2)B (3)A 书96页 (4)C (5)C 书92页 (6)D 书2页 (7)A书92页 (8)A书92页 (9)A 书92页 (10)B单支结点就是度为1的结点 图 D (11)B 书90页 (12)D 书119页 (13)B 总结点数减去叶子结点数就是双枝结点数 (14)A 叶子最长箭权路径为：3”6=18 H=3*3+6*3+8*2+12*1=9+18+16+12=55 第1风共3项 版权所有河南电大现教中心范额，邮箱@m加m
河南广播电视大学现教中心 第1页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 第六章 树和二叉树 课后习题答案 1、 单项选择题 （1） B （2） B （3） A 书 96 页 （4） C （5） C 书 92 页 （6） D 书 92 页 （7） A 书 92 页 （8） A 书 92 页 （9） A 书 92 页 （10） B 单支结点就是度为 1 的结点 图： A B D I J F H E （11） B 书 90 页 （12） D 书 119 页 （13） B 总结点数减去叶子结点数就是双枝结点数 （14） A 叶子最长带权路径为：3*6=18 WPL=3*3+6*3+8*2+12*1=9+18+16+12=55
河南广播电视大学现黄中心 29 12 9 3 2、运算题 (1) 先序：a.b.c,d.e.f 中序：c,b,a,e,d,f 后序16b0,f,4,a 按层：a,b,d,c,e,f (2)根据先根和中根，得出图： B D G H 后根序列：GBR,E,LJ.H,6,D,A 3、算法分析题 (1》retum+1 NodeLevelBT->rghChild,X) (c2>=1)retum c2+1 第2项共3页 版权所有河南电大规教中心抛顾，都箱Ba血m
河南广播电视大学现教中心 第2页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 29 12 17 9 3 8 6 2、 运算题 （1） a b d c e f 先序：a,b,c,d,e,f 中序：c,b,a,e,d,f 后序：c,b,e,f,d,a 按层：a,b,d,c,e,f （2）根据先根和中根，得出图： A B D I J G H C E J 后根序列：C,B,F,E,I,J,H,G,D,A 3、 算法分析题 （1）return cl+1 NodeLevel(BT—>rightChild，X) (c2>＝1) return c2+1
河南广播电视大学现黄中心 (2)对具有n个结点的二叉树进行中序遍历，把得到的结点值序列保存到数组a中。 4、算法设计题 (1)参考答案 int BTreeCoun(struct BTreeNode'BT) if(BT--NULL)return 0; retum BTreeCounBT->lchild+BTreeCoun BT->rchid)+1: (2)参考答案 nt BTreeLeafCounl(struct BTreeNode“BT刀 iNBT==NULL)retum0: else if(BT->left--NULL &BT-right--NULL)retum 1: else retum BTreeLeafCoun(BT-lett)+BTreeLeatCoun(BT->right 1 (3)参考答案： int BtreeCountBig(struct BTreeNode"BT,int x) if(BT==NULL)retumO; else(BT-data>x) retumn BTreeCounl[BT->left x)+BTreeCount(BT-right.x)+1: else retum BTreeCount(BT->left x)+BTreeCount BT->right,x 第3项共3项 版权所有河南电大现教中心植额，都箱dpm恒cn
河南广播电视大学现教中心 第3页 共3页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （2）对具有 n 个结点的二叉树进行中序遍历，把得到的结点值序列保存到数组 a 中。 4、 算法设计题 （1）参考答案： int BTreeCount(struct BTreeNode*BT) { if(BT==NULL) return 0; return BTreeCount(BT->lchild)+BTreeCount(BT->rchild) +1; } （2）参考答案： int BTreeLeafCount(struct BTreeNode * BT) { if(BT==NULL) return 0; else if(BT->left==NULL && BT->right==NULL) return 1; else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right); } （3）参考答案： int BtreeCountBig(struct BTreeNode * BT, int x) { if(BT==NULL) return 0; else if( BT->data>x) return BTreeCount( BT->left, x)+BTreeCount( BT->right, x)+1; else return BTreeCount( BT->left, x)+BTreeCount( BT->right, x); }