数据结构习题汇编06树和二叉树试题

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

2、h-1,所含结点个数不小于（）D、2 h在一棵具有在一棵具有A 、35个结点的完全二叉树中B、 6，该树的高度为（C、 7。假定空树的高度为-1。D、n个结点的完全二叉树中(n-1)/2B n/2分支结点的最大编号为C n/2o假定树根结点的编号为D n/2-10。在一棵完全二叉树中 编号为02i B在一棵完全二叉树中O(i+1)/2在一棵树的左子女兄弟,若编号为i的结点存在左孩子，则左子女结点的编号为（）。假定根结点的2i-1C、 2i+1D、 2i+2，假定根结点的编号为0,则对于编号为i（i>0）的结点，其双亲结点的编号为B、(i-1)/2C i/2D、i/2-1-右兄弟表示法中，

3、一个结点的右孩子就是该结点的B、子女C、祖先D、结点。子孙在一棵树的静态双亲表示中，每个存储结点包含（）B、 2个域。3D、13.已知一棵二叉树的广义表表示为a （b （c）, d （e （ , g （h） ）, f ）,则该二叉树的高度为（）假定根结点的高度为0。B、 4C、 5D、 614 .已知一棵树的边集表示为<A, B>, <A, C>, <B, D>, <C, E>, <C, F>, <C, G>, <F, H>,<F, I>,则该树的高度为()。假定根结点的高度为0。A 、 2B、 3

4、C、 4D、 5()个结点。15 .利用n个值作为叶结点上的权值生成的霍夫曼树中共包含有B、 n+1C 2*nD 2*n-116 .利用3, 6, 8, 12这四个值作为叶结点的权值生成一棵霍夫曼树，该树的带权路径长度为()A 、55B、29 C 、58D、3817 . 一棵树的广义表表示为a (b, c (e, f (g) ), d),当用左子女-右兄弟链表表示时，右指针域非空的结点个数为()。A 、1B、2C、3D、418 .向具有n个结点的堆中插入一个新元素的时间复杂度为()。A、O(1)B、 O(n)C、O(log2n)DO(nlog2n)参考答案:1、C2、C3、A4 C5、A6、D

5、7、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 (x, y),结点k的所有祖先的结点数为 个。5 .一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y),结点f的层数为 。假定根结点的层数为0。6 .假定一棵三叉树(即度为3的树)的结点个数为50,则它的最小高度

6、为 。假定根结点的高度为0。7 .在一棵高度为3的四叉树中，最多含有 结点。8 .在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有 个。9 . 一棵高度为5的完全二叉树中,最多包含有 个结点。假定根结点的高度为0。10 .假定一棵树的广义表表示为A (B (C, D (E, F, G), H (I, J),则该树的高度为 假定根结点的高度为0。11 .在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，则叶结点数为 个。12 .假定一棵二叉树的结点个数为18,则它的最小高度为 。假定根结点的高度为0。13 .在一棵高度为h的

7、理想平衡树(即从0层到h-1层都就是满的，第h层的结点分布在该层各处)中，最 少含有 个结点。假定根结点的高度为0。14 .在一棵高度为h的理想平衡树(即从0层到h-1层都就是满的，第h层的结点分布在该层各处)中，最 多含有 个结点。假定根结点的高度为0。15 .若将一棵树A (B (C, D, E), F (G (H), I)按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点个数为 个。16 . 一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中 结点肯定没有右子女。17 .在一个堆的顺序存储中，若一个元素的下标为i(0 wiWn-1),则它的左子女元素的下标为 。18

8、 .在一个堆的顺序存储中，若一个元素的下标为i(0 wiWn-1),则它的右子女元素的下标为 。19 .在一个小根堆(即最小堆)中，堆顶结点的值就是所有结点中的 。20 .在一个大根堆(即最大堆)中，堆顶结点的值就是所有结点中的 。21 . 6个结点可构造出 种不同形态的二叉树。22 .设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4,当把森林F转换成一棵二叉树后，其根结点的右子树中有 个结点。23 .设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4,当把森林F转换成一棵二叉树后，其根结点的左子树中有 个结点。24 .将含有82个结点

9、的完全二叉树从根结点开始顺序编号，根结点为第0号，其她结点自上向下，同一层自左向右连续编号。则第 40号结点的双亲结点的编号为参考答案：1、n-12、树根3、 叶子425、36、47、858、696310、311、612、413、2 h142 h+1 -115216、 根17、2i+1182i+219、 最小值20最大值21 、13222n 2+n3+n423 n 1-124 、19三、判断题1.当向一个小根堆(最小堆)中插入一个具有最小值的元素时，该元素需要逐层向上调整 ，直到被调整到堆顶位置为止。2.当从一个小根堆(最小堆)中删除一个元素时 层向下调整，直到调整到合适位置为止。,需要把堆尾

10、元素填补到堆顶位置，然后再按条件把它逐3.二叉树就是一棵无序树。4.在一棵二叉树中 相同的遍历结果。，假定每个结点只有左子女,没有右子女,对它分别进行前序遍历与后序遍历则具有5.在一棵二叉树中 相同的遍历结果。，假定每个结点只有左子女,没有右子女,对它分别进行中序遍历与后序遍历则具有6.在一棵二叉树中 相同的遍历结果。，假定每个结点只有左子女,没有右子女,对它分别进行前序遍历与中序遍历则具有7.在一棵二叉树中 相同的遍历结果。，假定每个结点只有左子女,没有右子女,对它分别进行前序遍历与按层遍历则具有8.在树的存储中,若使每个结点带有指向前驱结点的指针将在算法中为寻找前驱结点带来方便。9.对于一

11、棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。10.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为0(h)。11.对于一棵具有O(log 2n)。n个结点的任何二叉树,进行前序、中序或后序的任一种次序遍历的空间复杂度为12.在一棵具有n个结点的线索化二叉树中指向某一种遍历次序的前驱或后继结点,每个结点的指针域可能指向子女结点，也可能作为线索,所有结点中作为线索使用的指针域共有n个。13.线索化二叉树中的每个结点通常包含有5个数据成员。14.线索化二叉树中的每个结点通常包含有3个数据成员。15.对具有n个结点的堆进行插入一个元素运算的时

12、间复杂度为0(n)。16.从具有n个结点的堆中删除一个元素，其时间复杂度为 O(log 2n)。17.二叉树就是树的特殊情形。18.若有一个结点就是二叉树中某个子树的中序遍历结果序列的最后一个结点 序遍历结果序列的最后一个结点。,则它一定就是该子树的前19 .若有一个结点就是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定就是该子树的中序遍历结果序列的最后一个结点。20 .若有一个叶子结点就是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定就是该子树的前序遍历结果序列的最后一个结点。21 .若有一个叶子结点就是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定就是该

13、子树的中序遍历结果序列的最后一个结点。22 .若将一批杂乱无章的数据按堆结构组织起来，则堆中各数据必然按自小到大的顺序排列起来。参考答案：1、就是2、就是3、否4、否5、就是6、否7、就是8、 就是9、就是10、否11、 否12、 否13、 就是14、 否15、 否16、 就是17、就是18、 否19、 否20、 就是21、 否22、 否四、运算题1 .假定一棵二叉树的广义表表示为a (b (c), d (e, f),分别写出对它进行前序、中序、后序、按层遍历的结果。前序:中序:后序:按层:2 .假定一棵二叉树的广义表表示为A (B ( , D (G) ), C (E, F),分别写出对它进行

14、前序、中序、后序、按层遍历的结果。前序:中序:后序:按层:3 .假定一棵普通树的广义表表示为a (b (e), c (f (h, i, j), g), d),分别写出先根、后根、按层遍历的结果。先根:后根:按层:4 .已知一棵二叉树的前序与中序序列，求该二叉树的后序序列。前序序列: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前序序列:,求

15、该二叉树的前序序列。6.已知一棵二叉树的中序与后序序列如下 的结点及叶结点个数。中根序列:c, b, d, e, a, g, i, h, j, f后根序列:c, e, d, b, i, j, h, g, f, a，求该二叉树的高度（假定空树白高度为-1）与度为2、度为1高度:度为2:度为1： 叶子:7 .已知一棵二叉树的静态数组表示（即顺序存储表示）如下，其中0表示空指针，请分别写出该二叉树的前序、中序、后序遍历的序列。0 1 2 3 4 5 6 7 8 9 10 11 1220846515300001018035前序序列：中序序列：后序序歹“ ：8 .已知一棵树的静态双亲表示如下，其中用-1

16、表示空指针，树根结点存于0号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数与三分支结点数。序号：data: a bparent: -1 0c de fg hi jk1 13 056 60 9012345678910叶子结点数：单分支结点数 ：两分支结点数 ：三分支结点数：9 . 假定一个最大堆（大根堆）为（56, 38, 42, 30, 25, 40, 35, 20）,则依次向它插入 45与64两个元素后得到的最大堆为：10 .假定一个最小堆（小根堆）为（20, 35, 50, 57, 42, 70, 83, 65, 86）,则依次从中删除三个最小元素后得到的最小堆为：11 .已知

17、一组数为（56, 48, 25, 16, 74, 52, 83, 45）,请把该组数调整为最小堆（即小根堆）。最小堆:12 .有7个带权结点，其权值分别为3, 7, 8, 2, 6, 10, 14,试以它们为叶结点生成一棵霍夫曼树求出该树的带权路径长度、高度、度为 2的结点个数。带权路径长度：高度:度为2的结点数：13 .设二叉树根结点所在层次为0,树的高度h为距离根最远的叶结点所在层次，则:高度为h的完全二叉树的不同二叉树棵数：高度为h的满二叉树的不同二叉树棵数：14 .确定满足以下条件的二叉树的可能形态：二叉树的前序序列与中序序列相同：二叉树的中序序列与后序序列相同：二叉树的前序序列与后序

18、序列相同：参考答案：1. 前序:a, b, c, d, e, f/2 分中序：c,b,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 /24. 后序序列:C, B, F,

19、E, I, J, H, G, D, A /65. 前序序列: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分/69. (64, 56, 42, 38, 45, 40, 35, 20, 3

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

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

22、 ;else if ( BT->data = x )return 0 ;else int c1 = NodeLevel ( BT->leftChild, x ) if ( c1 >= 0 )(1)int c2 =(2);(3);else return -1 ;(2) 2.已知二叉树中的结点类型用BinTreeNode 表示，被定义为：struct BinTreeNode ElemType data ; BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild 与rightChild分别为指向左、右子女结点的指针域。

23、下面函数的功能就是从二叉树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) ;else

24、 (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 ;else BinTree

25、Node* 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; ;

26、其中data 为结点值域,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->leftCh

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

28、de* BT )if ( BT != NULL )if ( BT->leftChild != NULL&& BT->rightChild != NULL )if ( BT->leftChild->data > BT->rightChild->data )BinTreeNode* t = BT->leftChildBT->leftChild = BT->rightchild BT->rightChild = t; BTC ( BT->leftChild );BTC ( BT->rightChild );

29、算法功能：6 .已知二叉树中的结点类型用BinTreeNode表示，被定义为：struct BinTreeNode char data ; BinTreeNode *leftChild, *rightChild;其中data为结点值域,leftChild 与rightChild分别为指向左、右子女结点的指针域。假定指针bt指向一棵二叉树，该二叉树的广义表表示为a (b (a, d (f) ), c (e ( , a (k) ), b),整数变量C的值为0,若:(1)执行 BTC1( bt,'a'C )调用后,C的值为执行 BTC1( bt,'b , C )调用后,C的值

30、为执行 BTC1( bt,'c' , C)调用后,C的值为_执行 BTC1( bt,'g' , C)调用后,C的值为_void BTC1( BinTreeNode* 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 ;

31、BinTreeNode * leftChild, * rightChild ; ;其中data为结点值域，leftChild 与rightChild分别为指向左、右子女结点的指针域。下面函数的功能就是从二叉树BT中查找值为x的结点，若查找成功则返回结点地址，否则返回空。请在划有横线的地方填写合适内容。BinTreeNode* BTF ( BinTreeNode* BT, ElemType & x )if ( BT = NULL )(1) ;else if ( BT->data = x )(2) ;else BinTreeNode* t ;If ( t = BTF ( BT->

32、;leftChild, x ) )(3) (4);else return NULL ;(2) 8 .已知二叉树中的结点类型用BinTreeNode 表示，被定义为：struct BinTreeNode ElemType data ; BinTreeNode *leftChild, *rightChild ; ;其中data为结点值域，leftChild 与rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。;return 1 ; return 1return 1int DST ( BinTreeNode* & B

33、T , ElemType x ) if ( BT = NULL ) return 0 ;else if ( BT->data = x ) BT = NULLelse if ( DST ( BT->leftChild, x )if ( DST ( BT->rightChild, x ) else return 0;算法功能：9 .已知二叉树中的结点类型用BinTreeNode 表示，被定义为：struct BinTreeNode char data ; BinTreeNode *leftChild, *rightChild ; ;其中data为结点值域,leftChild 与r

34、ightChild分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r (b (, d (f, g) ), t (e) ),rt, bt, dt与et指 针变量分别保存指向r, b, d 与e结点的指针值，则:(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

35、 = BTM ( BT->leftChild );k2 = BTM ( BT->rightChild);if ( k1 > max ) max = k1;else if ( k2 > max ) max = k2;else if ( BT->data > max ) max = BT->data returnmax ;10 .已知二叉树中的结点类型用BinTreeNode 表示，被定义为：struct BinTreeNode ElemType data ; BinTreeNode *leftChild, *rightChild ; ;其中data为结点

36、值域,leftChild 与rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数 BT指向一棵二叉树的根结点。void preserve ( BinTreeNode* BT, ElemType a , int n )static int i = 0;if ( BT != NULL )preserve ( BT->leftChild, a, n );ai+ = BT->data ;preserve ( BT->rightChild, a, n );算法功能：11 .假定在a10数组中数据为 16, 42, 35, 73, 54, 3

37、8, 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 )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

38、)调用下面算法后数组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 )if ( j < n-1&& HBTj > HBTj+1 ) j+;if ( x <= HBTj )break;HBTi = HBTj ;i = j ; j = 2*i+1

39、;HBTi = x ;return temp ;参考答案：/2 分/3 分/3 分/2return PT /4/21. (1) return c1+1(2) NodeLevel ( BT->rightChild, X )(3) if (c2 >= 0 ) return c2+12. (1) returnPT(2) if ( PT = ParentPtr ( BT->rightChild, BT, X )(3) returnNULL 或 return 03 .算法功能：生成一棵新二叉树并返回树根指针，该二叉树就是已知二叉树 BT中所有结点的左、右子树交换的结果。4 .算法功能：

40、从树根指针为T的二叉树中查找值为 X的结点，返回指向父结点的指针。5 .算法功能：对二叉树BT进行处理，当BT中每个结点的左孩子的值大于右孩子的值则交换左右子树。6.(1) 3(2) 2(3) 1(4) 0/2/2/2/2分 分分 分7.(1) returnNULL/2 分(2) returnBT/2分(3) return t/2分(4) if ( t = BTF ( BT->rightChild, x )return t/2 分8.算法功能：从一棵二叉树中删除根结点值为x的子树，若删除成功则返回1,否则返回9.(1) ' t '/2分(2) ' g'/2

41、分(3) ' g'/2分(4) e /2分,把得到的结点值序列保存到数组a中。/有一处错则不得分/有一处错则不得分10. 算法功能：对具有n个结点的二叉树进行中根遍历11. 16, 25, 35, 42, 54, 38, 80, 7312. 26, 35, 42, 73, 54, 68, 80六、算法设计题1.已知二叉树中的结点类型用BinTreeNode 表示，被定义为：struct BinTreeNode char其中data 为结点值域，leftChilddata ; BinTreeNode *leftChild与rightChild分别为指向左、, *rightChil

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

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

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

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

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

47、*rightChild; ;其中data为结点值域，leftChild 与rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出复制一棵二叉树的算法，并返回复制得到的二叉树的树根指针。算法中参数BT初始指向待复制二叉树的根结点。BinTreeNode* BTreeCopy ( BinTreeNode* BT );8 .已知二叉树中的结点类型用BinTreeNode 表示，被定义为：struct BinTreeNode char data ; BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild 与right

48、Child分别为指向左、右子女结点的指针域，根据下面函数声明编写出从一棵二叉树中求出结点值大于x初始指向二叉树的根结点。int BTreeCount ( BinTreeNode* BT参考答案：1.算法如下int BTreeHeight ( BinTreeNode* BT )if ( BT = NULL )return T ;分else int h1 = BTreeHeight ( BT->leftChild ) int h2 = BTreeHeight (BT->rightChild ) if ( h1 > h2 ) return h1+1 ;的结点个数的算法，并返回所求结

49、果。算法中参数 BT , ElemType x );/对于空树，返回-1并结束递归,1;/计算左子树的高度,2分;/计算右子树的高度,2分else returnh2+1 ;/返回树的高度,3分2 .算法如下int BTreeCount ( BinTreeNode* BT )if ( BT = NULL ) return 0 ;/2分elsereturn BTreeCount ( BT->leftChild ) + BTreeCount ( BT->rightChild )+ 1 ;/6 分)3 .算法如下int BTreeLeafCount ( BinTreeNode* BT )/1=NULL) return 1;)+ BTreeLeafCountif ( BT = NULL )