《数据结构》习题汇编-第六章树和二叉树试题

《《数据结构》习题汇编-第六章树和二叉树试题》由会员分享，可在线阅读，更多相关《《数据结构》习题汇编-第六章树和二叉树试题（17页珍藏版）》请在装配图网上搜索。

1、第六章 树和二叉树 试题一、单项选择题1. 树中所有结点的度等于所有结点数加（ ）。 A. 0 B. 1 C. -1 D. 22. 在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点3. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2 B. 1 C. 0 D. -14. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。 A. n B. n-1 C. n+1 D. 2*n5. 在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），最多具有（ ）个结点。 A. 2i B. 2i+1

2、 C. 2i-1 D. 2n6. 在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（ ）。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h7. 在一棵具有35个结点的完全二叉树中，该树的高度为（ ）。假定空树的高度为-1。 A. 5 B. 6 C. 7 D. 88. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ ）。假定树根结点的编号为0。 A. (n-1)/2 B. n/2 C. n/2 D. n/2 -19. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（ ）。假定根结点的编号为0 A. 2i B. 2i-1 C. 2

3、i+1 D. 2i+210. 在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i0）的结点，其双亲结点的编号为（ ）。 A. (i+1)/2 B. (i-1)/2 C. i/2 D. i/2 -111. 在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（ ）结点。 A. 兄弟 B. 子女 C. 祖先 D. 子孙12. 在一棵树的静态双亲表示中，每个存储结点包含（ ）个域。 A. 1 B. 2 C. 3 D. 413. 已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为（ ）。假定根结点的高度为0。 A. 3

4、B. 4 C. 5 D. 614. 已知一棵树的边集表示为 , , , , , , , ，则该树的高度为（ ）。假定根结点的高度为0。 A. 2 B. 3 C. 4 D. 515. 利用n个值作为叶结点上的权值生成的霍夫曼树中共包含有（ ）个结点。 A. n B. n+1 C. 2*n D. 2*n-116. 利用3, 6, 8, 12这四个值作为叶结点的权值生成一棵霍夫曼树，该树的带权路径长度为（ ）。 A. 55 B. 29 C. 58 D. 3817. 一棵树的广义表表示为a (b, c (e, f (g) ), d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为（ ）。 A.

5、 1 B. 2 C. 3 D. 418. 向具有n个结点的堆中插入一个新元素的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(log2n) D. O(nlog2n)参考答案：1. C 2. C 3. A4. C5. A6. D7. A8. D9. C10. B11. A12. B13. B14. B15. D16. A17. C18. C二、填空题1. 对于一棵具有n个结点的树，该树中所有结点的度数之和为_。2. 在一棵树中，_结点没有前驱结点。3. 在一棵树中，_结点没有后继结点。4. 一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k

6、 (x, y) ) )，结点k的所有祖先的结点数为_个。5. 一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为_。假定根结点的层数为0。6. 假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为_。假定根结点的高度为0。7. 在一棵高度为3的四叉树中，最多含有_结点。8. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有_个。9. 一棵高度为5的完全二叉树中，最多包含有_个结点。假定根结点的高度为0。10. 假定一棵树的广义表表示为A (B (C,

7、D (E, F, G), H (I, J) ) )，则该树的高度为_。假定根结点的高度为0。11. 在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，则叶结点数为_个。12. 假定一棵二叉树的结点个数为18，则它的最小高度为_。假定根结点的高度为0。13. 在一棵高度为h的理想平衡树（即从0层到h-1层都是满的，第h层的结点分布在该层各处）中，最少含有_个结点。假定根结点的高度为0。14. 在一棵高度为h的理想平衡树（即从0层到h-1层都是满的，第h层的结点分布在该层各处）中，最多含有_个结点。假定根结点的高度为0。15. 若将一棵树A (B (C, D, E), F (G

8、(H), I) ) 按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点个数为_个。16. 一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中_结点肯定没有右子女。17. 在一个堆的顺序存储中，若一个元素的下标为i（0in-1），则它的左子女元素的下标为_。18. 在一个堆的顺序存储中，若一个元素的下标为i（0in-1），则它的右子女元素的下标为_。19. 在一个小根堆（即最小堆）中，堆顶结点的值是所有结点中的_。 20. 在一个大根堆（即最大堆）中，堆顶结点的值是所有结点中的_。21. 6个结点可构造出_种不同形态的二叉树。22. 设森林F中有4棵树，第1、2、3、4棵树

9、的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的右子树中有_个结点。23. 设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的左子树中有_个结点。24. 将含有82个结点的完全二叉树从根结点开始顺序编号，根结点为第0号，其他结点自上向下，同一层自左向右连续编号。则第40号结点的双亲结点的编号为_。参考答案：1. n-12. 树根3. 叶子4. 25. 36. 47. 858. 69. 6310. 311. 612. 413. 2h14. 2h+1-115. 216. 根17. 2i+118.

10、2i+219. 最小值20. 最大值21. 13222. n2+n3+n423. n1-124. 19三、判断题1. 当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。2. 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。3. 二叉树是一棵无序树。4. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果。5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结

11、果。6. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中序遍历，则具有相同的遍历结果。7. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的遍历结果。8. 在树的存储中，若使每个结点带有指向前驱结点的指针，将在算法中为寻找前驱结点带来方便。9. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。10. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。11. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(lo

12、g2n)。12. 在一棵具有n个结点的线索化二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。13. 线索化二叉树中的每个结点通常包含有5个数据成员。14. 线索化二叉树中的每个结点通常包含有3个数据成员。15. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。16. 从具有n个结点的堆中删除一个元素，其时间复杂度为O(log2n)。17. 二叉树是树的特殊情形。18. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。19.

13、若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。20. 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。21. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。22. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中各数据必然按自小到大的顺序排列起来。参考答案：1. 是2. 是3. 否4. 否5. 是6. 否7. 是8. 是9. 是10. 否11. 否12. 否13. 是14. 否15. 否

14、16. 是17. 是18. 否19. 否20. 是21. 否22. 否四、运算题1. 假定一棵二叉树的广义表表示为a (b (c), d (e, f) )，分别写出对它进行前序、中序、后序、按层遍历的结果。 前序：_ 中序：_ 后序：_ 按层：_2. 假定一棵二叉树的广义表表示为A (B ( , D (G) ), C (E, F) )，分别写出对它进行前序、中序、后序、按层遍历的结果。 前序：_ 中序：_ 后序：_ 按层：_3. 假定一棵普通树的广义表表示为a (b (e), c (f (h, i, j), g), d)，分别写出先根、后根、按层遍历的结果。 先根：_ 后根：_ 按层：_4.

15、已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, E, F, D, I, H, J, G后序序列：_5. 已知一棵二叉树的中序和后序序列如下，求该二叉树的前序序列。中序序列：c, b, d, e, a, g, i, h, j, f后序序列：c, e, d, b, i, j, h, g, f, a前序序列：_6. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1的结点及叶结点个数。 中根序列：c, b, d, e, a, g, i, h, j, f 后根序

16、列：c, e, d, b, i, j, h, g, f, a高度：_ 度为2：_ 度为1：_ 叶子：_7. 已知一棵二叉树的静态数组表示（即顺序存储表示）如下，其中0表示空指针，请分别写出该二叉树的前序、中序、后序遍历的序列。 0 1 2 3 4 5 6 7 8 9 10 11 12 20 8 46 5 15 30 0 0 0 10 18 0 35 前序序列：_ 中序序列：_后序序列：_8. 已知一棵树的静态双亲表示如下，其中用 -1表示空指针，树根结点存于0号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。序号： 0 1 2 3 4 5 6 7 8 9 10 dat

17、a: a b c d e f g h i j k parent: -1 0 1 1 3 0 5 6 6 0 9叶子结点数： _单分支结点数：_两分支结点数：_三分支结点数：_9. 假定一个最大堆（大根堆）为（56, 38, 42, 30, 25, 40, 35, 20），则依次向它插入45和64两个元素后得到的最大堆为：_10. 假定一个最小堆（小根堆）为（20, 35, 50, 57, 42, 70, 83, 65, 86），则依次从中删除三个最小元素后得到的最小堆为：_11. 已知一组数为（56, 48, 25, 16, 74, 52, 83, 45），请把该组数调整为最小堆（即小根堆）。

18、最小堆：_12. 有7个带权结点，其权值分别为3, 7, 8, 2, 6, 10, 14，试以它们为叶结点生成一棵霍夫曼树，求出该树的带权路径长度、高度、度为2的结点个数。 带权路径长度：_ 高度：_ 度为2的结点数：_13. 设二叉树根结点所在层次为0，树的高度h为距离根最远的叶结点所在层次，则：高度为h的完全二叉树的不同二叉树棵数：_高度为h的满二叉树的不同二叉树棵数：_14. 确定满足以下条件的二叉树的可能形态：二叉树的前序序列与中序序列相同：_二叉树的中序序列与后序序列相同：_二叉树的前序序列与后序序列相同：_参考答案：1. 前序：a, b, c, d, e, f /2分中序：c, b

19、, a, e, d, f /2分后序：c, b, e, f, d, a /1分按层：a, b, d, c, e, f /1分2. 前序：A, B, D, G, C, E, F/2分中序：B, G, D, A, E, C, F/2分后序：G, D, B, E, F, C, A/1分按层：A, B, C, D, E, F, G/1分3. 先根：a, b, e, c, f, h, i, j, g, d /2分 后根：e, b, h, i, j, f, g, c, d, a /2分按层：a, b, c, d, e, f, g, h, i, j /2分4. 后序序列：C, B, F, E, I, J,

20、H, G, D, A /6分5. 前序序列：a, b, c, d, e, f, g, h, i, j /6分6. 高度：5 /2分 度为2：3 /2分度为1：3 /1分叶子：4 /1分7. 前序序列：20, 8, 5, 15, 10, 18, 46, 30, 35 /2分中序序列：5, 8, 10, 15, 18, 20, 30, 35, 46 /2分后序序列：5, 10, 18, 15, 8, 35, 30, 46, 20 /2分8. 叶子结点数： 5 /2分单分支结点数：3 /2分两分支结点数：2 /1分三分支结点数：1 /1分9. (64, 56, 42, 38, 45, 40, 35,

21、 20, 30, 25)/6分10. (50, 57, 70, 65, 86, 83) /6分11. (16, 45, 25, 48, 74, 52, 83, 56) /6分12. 带权路径长度：131 /3分 高度：4 /2分度为2的结点数：6 /1分13. 高度为h的完全二叉树的不同二叉树棵数：2h；/3分高度为h的满二叉树的不同二叉树棵数：1；/3分14. 二叉树的前序序列与中序序列相同：所有结点的左子树为空；/2分二叉树的中序序列与后序序列相同：所有结点的右子树为空；/2分二叉树的前序序列与后序序列相同：只有一个结点，左右子树为空；/2分五、算法分析题1. 已知二叉树中的结点类型用Bi

22、nTreeNode表示，被定义为: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为x的结点所在的层号，请在划有横线的地方填写合适的内容。int NodeLevel ( BinTreeNode * BT, ElemType& x ) if ( BT = NULL ) return 1; /空树的层号为-1 else if ( BT-data = x ) return

23、0; /根结点的层号为0 else int c1 = NodeLevel ( BT-leftChild, x ); /向子树中查找x结点 if ( c1 = 0 ) _(1)_; int c2 =_(2)_; _(3)_; else return -1; /在树中不存在x结点返回-1(1) _(2) _(3) _2. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指

24、向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为x的结点，返回指向其父结点的指针。若该结点不存在或为树根结点则返回空。算法中参数PT的初值为NULL。请在划有横线的地方填写合适的内容。BinTreeNode* ParentPtr ( BinTreeNode* BT, BinTreeNode* PT, ElemType& x ) if ( BT = NULL ) return NULL; else if ( BT-data = x ) return PT; else if ( PT = ParentPtr ( BT-leftChild, BT, x ) ) _(1)_; _(2)

25、_; else _(3)_; (1) _(2) _(3) _3. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的树根结点。BinTreeNode* BinTreeSwopX ( BinTreeNode * BT ) if ( BT = NULL ) return NULL;e

26、lse BinTreeNode* pt = new BinTreeNode;pt-data = BT-data;pt-rightChild = BinTreeSwopX ( BT-leftChild );pt-lefthild = BinTreeSwopX ( BT-rightChild ); return pt; 算法功能：_4. 已知二叉树中的结点类型用ThreeTreeNode表示，被定义为: struct ThreeTreeNode datatype data; ThreeTreeNode *leftChild, *rightChild, *parent; ; 其中data为结点值域，

27、leftChild和rightChild分别为指向左、右子女结点的指针域，parent为指向父结点的指针域。根据下面函数的定义指出函数的功能。算法中参数T指向一棵二叉树的树根结点，x保存一个结点的值。ThreeTreeNode* PN ( ThreeTreeNode * T, datatype& x ) if ( T = NULL ) return NULL; else ThreeTreeNode* mt;if ( T-data = x ) return T-parent;else if ( mt = PN ( T-leftChild, x ) ) return mt;else if ( mt

28、 = PN ( T-rightChild, x ) ) return mt;return NULL; 算法功能：_5. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。void BTC ( BinTreeNode* BT ) if ( BT != NULL ) if (

29、 BT-leftChild != NULL & BT-rightChild != NULL ) if ( BT-leftChild-data BT-rightChild-data ) BinTreeNode* t = BT-leftChild; BT-leftChild = BT-rightchild; BT-rightChild = t; BTC ( BT-leftChild );BTC ( BT-rightChild ); 算法功能：_6. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode char data; BinTreeNode *

30、leftChild, *rightChild;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定指针bt指向一棵二叉树，该二叉树的广义表表示为a (b (a, d (f) ), c (e ( , a (k) ), b) )，整数变量C的值为0，若：(1) 执行BTC1( bt, a, C ) 调用后，C的值为_;(2) 执行BTC1( bt, b, C ) 调用后，C的值为_;(3) 执行BTC1( bt, c, C) 调用后，C的值为_;(4) 执行BTC1( bt, g, C) 调用后，C的值为_;void BTC1( BinTreeNo

31、de* BT, char x, int& k ) if ( BT != NULL ) if ( BT-data = x ) k+;BTC1( BT-leftChild, x, k );BTC1( BT-rightChild, x, k );7. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode ElemType data;BinTreeNode * leftChild, * rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为x的结

32、点，若查找成功则返回结点地址，否则返回空。请在划有横线的地方填写合适内容。BinTreeNode* BTF ( BinTreeNode* BT, ElemType& x ) if ( BT = NULL ) _(1)_; else if ( BT-data = x ) _(2)_; else BinTreeNode* t;If ( t = BTF ( BT-leftChild, x ) ) _(3)_; _(4)_; else return NULL;(1) _(2) _(3) _(4) _8. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNod

33、e ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。int DST ( BinTreeNode*& BT, ElemType x ) if ( BT = NULL ) return 0;else if ( BT-data = x ) BT = NULL; return 1; else if ( DST ( BT-leftChild, x ) ) return 1;if

34、( DST ( BT-rightChild, x ) ) return 1;else return 0; 算法功能：_9. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode char data; BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r (b (, d (f, g) ), t (e) )，rt, bt, dt和et指针变量分别保存指向r, b, d和e结点的指针值，

35、则：(1)执行BTM (rt) 调用后，得到的函数值为_;(2)执行BTM (bt) 调用后，得到的函数值为_;(3)执行BTM (dt) 调用后，得到的函数值为_;(4)执行BTM (et) 调用后，得到的函数值为_;char BTM(BinTreeNode* BT) static char max = 0;if ( BT != NULL ) char k1, k2;k1 = BTM ( BT-leftChild );k2 = BTM ( BT-rightChild );if ( k1 max ) max = k1;else if ( k2 max ) max = k2;else if (

36、BT-data max ) max = BT-data;return max;10. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。void preserve ( BinTreeNode* BT, ElemType a , int n ) static int i =

37、 0;if ( BT != NULL ) preserve ( BT-leftChild, a, n );ai+ = BT-data;preserve ( BT-rightChild, a, n ); 算法功能：_11. 假定在a10数组中数据为 16, 42, 35, 73, 54, 38, 80 ，n为整型变量，其值为7，则执行IH ( a, n, 25 ) 调用下面算法后数组a中的数据变为：_void IH ( int HBT , int& n, int item ) HBTn = item;n+; int x = item; int i = n-1; while ( i != 0 )

38、int j = (i-1)/2; if ( x = HBTj ) break; HBTi = HBTj; i = j; HBTi = x;12. 假定在a10数组中数据为 16, 35, 42, 73, 54, 68, 80, 26，n为整型变量，其值为8，则执行DH ( a, n ) 调用下面算法后数组a中的数据变为：_int DH ( int HBT , int& n ) if ( n = 0 ) cerr null! endl; exit (1); int temp = HBT0;n-;int x = HBTn;int i = 0, j = 2*i+1;while ( j = n-1 )

39、 if ( j HBTj+1 ) j+;if ( x rightChild, X )/3分(3) if (c2 = 0 ) return c2+1 /3分2. (1) return PT /2分(2) if ( PT = ParentPtr ( BT-rightChild, BT, X ) ) return PT /4分(3) return NULL或return 0 /2分3. 算法功能：生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树交换的结果。4. 算法功能：从树根指针为T的二叉树中查找值为X的结点，返回指向父结点的指针。5. 算法功能：对二叉树BT进行处理

40、，当BT中每个结点的左孩子的值大于右孩子的值则交换左右子树。6. (1) 3 /2分(2) 2 /2分(3) 1 /2分(4) 0 /2分7. (1) return NULL /2分(2) return BT /2分(3) return t /2分(4) if ( t = BTF ( BT-rightChild, x ) ) return t /2分8. 算法功能：从一棵二叉树中删除根结点值为x的子树，若删除成功则返回1，否则返回0。9. (1) t /2分(2) g /2分(3) g /2分(4) e/2分10. 算法功能：对具有n个结点的二叉树进行中根遍历，把得到的结点值序列保存到数组a中

41、。11. 16, 25, 35, 42, 54, 38, 80, 73 /有一处错则不得分12. 26, 35, 42, 73, 54, 68, 80 /有一处错则不得分六、算法设计题1. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树高度的算法，该高度由函数返回。假定根结点的层次为0，参数BT初始指向这棵二叉树

42、的根结点。 int BTreeHeight ( BinTreeNode* BT );2. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。 int BTreeCount ( BinTreeNode* BT );3. 已知二叉树中的结点类型用B

43、inTreeNode表示，被定义为: struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。 int BTreeLeafCount ( BinTreeNode* BT );4. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode char data;Bi

44、nTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出删除一棵二叉树中所有结点的算法，并使树根指针为空。假定引用参数BT初始指向这棵二叉树的根结点。 void ClearBinTree ( BinTreeNode*& BT);5. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，le

45、ftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1，否则返回0。算法中参数T1和T2为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值相同时才被认为相等。int BTreeEqual ( BinTreeNode* T1, BinTreeNode* T2 );6. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，l

46、eftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出交换一棵二叉树中所有结点的左、右指针域值的算法，算法中参数BT初始指向这棵二叉树的根结点。void BTreeSwop ( BinTreeNode* BT );7. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出复制一棵二叉树的算法

47、，并返回复制得到的二叉树的树根指针。算法中参数BT初始指向待复制二叉树的根结点。 BinTreeNode* BTreeCopy ( BinTreeNode* BT );8. 已知二叉树中的结点类型用BinTreeNode表示，被定义为: struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ; 其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出从一棵二叉树中求出结点值大于x的结点个数的算法，并返回所求结果。算法中参数BT初始指向二叉树的根结点。 int BTreeCount ( BinTreeNode* BT, ElemType x );参考答案：1. 算法如下int BTreeHeight ( BinTreeNode* BT ) if ( BT = NULL )return 1;/对于空树，返回-1并结束递归，1分else int h1 = BTreeHeight ( BT-leftChild ); /计算左子树的高度，2分int h2 = BTreeHeight (BT-rightChild );/计算右子树的