第六章树和二叉树习题_数据结构
习题六树和二叉树
一、单项选择题
1．以下说法错误的是（）
A. 树形结构的特点是一个结点可以有多个直接前趋
B. 线性结构中的一个结点至多只有一个直接后继
C. 树形结构可以表达（组织）更复杂的数据
D. 树（及一切树形结构）是一种”分支层次”结构
E. 任何只含一个结点的集合是一棵树
2. 下列说法中正确的是（）
A. 任何一棵二叉树中至少有一个结点的度为2
B. 任何一棵二叉树中每个结点的度都为2
C. 任何一棵二叉树中的度肯定等于2
D. 任何一棵二叉树中的度可以小于2
3. 讨论树、森林和二叉树的关系，目的是为了（）
A. 借助二叉树上的运算方法去实现对树的一些运算
B. 将树、森林按二叉树的存储方式进行存储
C. 将树、森林转换成二叉树
D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（）
A. 有序数据元素 B .无序数据元素
C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据
5．若一棵二叉树具有10个度为2 的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定
6.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F
对应的二叉树根结点的右子树上的结点个数是（）。
A．M1 B ．M1+M2 C ．M3 D ．M2+M3
7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）
A．250 B ．500 C ．254 D ．505 E ．以上答案都不对
8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（）
A. 不确定B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（）
I I-1 I-1 I
A．2I
B ．2
I-1
-1 C ．2
I-1
D ．2
I
-1
10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1
11. 利用二叉链表存储树，则根结点的右指针是（）。
A.指向最左孩子B .指向最右孩子 C .空D .非空
14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）
A.都不相同 B .完全相同
C.先序和中序相同，而与后序不同 D .中序和后序相同，而与先序不同
15．在完全二叉树中，若一个结点是叶结点，则它没（）。
A.左子结点 B .右子结点
C.左子结点和右子结点 D .左子结点，右子结点和兄弟结点
A. 每个结点至多有两棵子树的树
B. 哈夫曼树
C. 每个结点至多有两棵子树的有序树
D. 每个结点只有一棵右子树
E. 以上答案都不对
17. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )
A. 0
B. 1
C. 2
D. 不确定
18. 引入二叉线索树的目的是( )
A.加快查找结点的前驱或后继的速度B ?为了能在二叉树中方便的进行插入与删除
C.为了能方便的找到双亲 D ?使二叉树的遍历结果唯一
19. n 个结点的线索二叉树上含有的线索数为( )
A. 2n B . n－l C . n＋l D . n
21.下面几个符号串编码集合中，不是前缀编码的是( )。
A. {0,10,110,1111} B . {11,10,001,101,0001}
C. {00,010,0110,1000} D . {b,c,aa,ac,aba,abb,abc}
22. 一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组
A[1..n] 中，则二叉树中第i 个结点(i 从1 开始用上述方法编号)的右孩子在数组A中的位置是()
A. A[2i](2i<=n) B . A[2i+1](2i+1<=n)
C. A[i-2] D .条件不充分，无法确定
23、以下说法错误的是( )
A. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B. 若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序
列中的第一个结点。
C. 已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪
一个。
D. 在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
二、判断题(在各题后填写“V 或“X”)
I. 完全二叉树一定存在度为1 的结点。( )
2 .对于有N个结点的二叉树，其高度为log 2n。()
3. 二叉树的遍历只是为了在应用中找到一种线性次序。( )
4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。( )
5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( )
6. 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。( )
7. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。( )
8. 二叉树只能用二叉链表表示。( )
9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。( )
10. 用链表(llink-rlink) 存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空
指针。( )
II. 树形结构中元素之间存在一个对多个的关系。
( )
12. 将一棵树转成二叉树，根结点没有左子树。
13. 度为二的树就是二叉树。()
14. 二叉树中序线索化后，不存在空指针域。()
15?霍夫曼树的结点个数不能是偶数。()
16. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。()
三、填空题
I. 在二叉树中，指针p所指结点为叶子结点的条件是——。2?深度为k的完全二叉树至少有___________ 个结点，至多有_______________ 个结点。
3?高度为8的完全二叉树至少有______个叶子结点。
4. 具有n个结点的二叉树中，一共有__________ 个指针域，其中只有_________ 个用来指向结点的左右孩子，其余的__________ 个指针域为NULL。
5. __________________________ 树的主要遍历方法有__ 、、等三种。
6. 一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左到右)用自然数依
此对结点编号，则编号最小的叶子的序号是_ _ ;编号是i的结点所在的层次号
是_ __ (根所在的层次号规定为1层)。
7 .如果结点A有3个兄弟，而且B是A的双亲，贝U B的度是__________ 。
&二叉树的先序序列和中序序列相同的条件是_ _ __________ 。
9. ________________________________________ 一个无序序列可以通过构造一棵树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
10. 若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的_ …序列中的最后一个结点。
II. 若以{4 , 5, 6, 7, 8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是____________
0*/
12. 以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。
Void countleaf(bitreptr t,int * count)/ * 根指针为t，假定叶子数count 的初值为
{if(t!=NULL)
{if((t->lchild==NULL)&&(t->rchild==NULL)) ______ ;
coun tleaf(t->lchild, &coun t);
0*/
14. 二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。
int depth(bitree bt) /*bt 为根结点的指针 */
{int hl,hr;
if (bt==NULL) return((1)_ __); _______________ hl=depth(bt->lchild); hr=depth(bt->rchild); if((2)_ __) (3)_ ____________________________ ；
return(hr+1);
}
15 .将二叉树bt 中每一个结点的左右子树互换的C 语言算法如下，其中
ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法 中得空白处，完成其功能。
typedef struct node
{int data ; struct node *lchild, *rchild; }bt no de; void EXCHANGE? node *bt) {bt node *p, *q; if (bt){ADDQ(Q,bt);
while(!EMPTY(Q)) {p=DELQ(Q); q=(1)_
; p->rchild=(2) __;⑶一 _=q ___________ _________
if(p->lchild) (4) _____ ld) (5)_
__;
______________
}
} }//
四、应用题
1 ?树和二叉树之间有什么样的区别与联系？
2. 分别画出具有 3个结点的树和3个结点的二叉树的所有不同形态。 3?分别给出下图所示二叉树的先根、中根和后根序列。
13.以下程序是二叉链表树中序遍历的非递归算法, 型的定义如下：
请填空使之完善。二叉树链表的结点类
typedef struct node /*C 语言 / {char data; struct node *lchild,*rchild;}*bitree; void vst(bitree bt) /*bt { bitree p; p=bt; in itstack(s); /*
while(p || !empty(s)) /* if(p) { push (s,p); (1)___ ; }
/*P
为根结点的指针*/ 初始化栈s 为空栈*/ 栈s 不为空*/
入栈*/ else { p=pop(s); printf(
“％(” ,p ->data);(2)
_____
栈顶元素出栈*/
4.一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K 棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：
1) 各层的结点的数目是多少？
2) 编号为n的结点的双亲结点(若存在)的编号是多少？
3) 编号为n的结点的第i个孩子结点(若存在)的编号是多少？
4) 编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？请给出计算和推导过程。
5?将下列由三棵树组成的森林转换为二叉树。(只要求给出转换结果)
6.设二叉树BT的存储结构如下：
1 2 3 4 5 6 7 8 9 10
Lchild 0 0 2 3 7 5 8 0 10 1
Data J H F D B A C E G I
Rchild 0 0 0 9 4 0 0 0 0 0
其中BT为树根结点的指针，其值为6,Lchild,Rchild 分别为结点的左、右孩子指针域，data
为结点的数据域。试完成下列各题：
(l )画出二叉树BT的逻辑结构；
(3)画出二叉树的后序线索树。
五、算法设计题
1?要求二叉树按二叉链表形式存储，
(1)写一个建立二叉树的算法。
(2)写一个判别给定的二叉树是否是完全二叉树的算法。
完全二叉树定义为：深度为K,具有N个结点的二叉树的每个结点都与深度为K的满二
叉树中编号从1至N的结点----- 对应。此题以此定义为准。
2. 设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，
数据结构树和二叉树实验报告
《数据结构》课程实验报告 实验名称树和二叉树实验序号 5 实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树 的深度、森林等定义。 (2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。 (3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。 (4)掌握二叉树的性质。 (5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。 (6)重点掌握二叉树的基本运算和各种遍历算法的实现。 (7)掌握线索二叉树的概念和相关算法的实现。 (8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。 (9)掌握并查集的相关概念和算法。 (10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。 二、实验项目摘要 1．编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）输出二叉树b; （2）输出H结点的左、右孩子结点值； （3）输出二叉树b的深度； （4）输出二叉树b的宽度； （5）输出二叉树b的结点个数； （6）输出二叉树b的叶子结点个数。 2．编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。 三、实验预习内容 二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）
三、实验结果与分析 7-1 #include
《数据结构》习题集：_树和叉树
第6章树和二叉树 一、选择题 1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ B ） A、向量 B、树 C、图 D、二叉树 2.树最适合用来表示（ B ） A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ） A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c) 4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中， 其左孩子的编号小于其右孩子的编号，则可采用（ C ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。 A、3 B、4 C、5 D、6 6.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高 度为（ E ），其叶结点数为（ H ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。 log+1 C、log2n D、n A、n/2 B、??n2 E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1K、n2L、n1+1 7.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 8.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B ），至多 为（D ）。 A、2h B、2h-1 C、2h-1 D、2h-1 9.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1） A、8 B、16 C、15 D、32 10.深度为5 的二叉树至多有（ C ）个结点。 A、16 B、32 C、31 D、10 11.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点 A、247 B、248 C、249 D、250 12.含有129 个叶子结点的完全二叉树，最少有（ D ）个结点 A、254 B、255 C、256 D、257 13.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。 A、15 B、16 C、17 D、47 14.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结 点（ B ）。 A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]
数据结构二叉树习题含答案
2.1 创建一颗二叉树 创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。我们在创建的时候为了方便，不妨用‘#’表示空节点，这时如果先序序列是：6 4 2 3 # # # # 5 1 # # 7 # #，那么创建的二叉树如下： 下面是创建二叉树的完整代码：穿件一颗二叉树，返回二叉树的根 2.2 二叉树的遍历 二叉树的遍历分为：先序遍历，中序遍历和后序遍历，这三种遍历的写法是很相似的，利用递归程序完成也是灰常简单的： 2.3 层次遍历 层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种广度优先搜索（BFS）。因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是说利用别的数据结构不能完成。 2.4 求二叉树中叶子节点的个数 树中的叶子节点的个数= 左子树中叶子节点的个数+ 右子树中叶子节点的 个数。利用递归代码也是相当的简单， 2.5 求二叉树的高度 求二叉树的高度也是非常简单，不用多说：树的高度= max(左子树的高度，右子树的高度) + 1 2.6 交换二叉树的左右儿子 交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。。 2.7 判断一个节点是否在一颗子树中 可以和当前根节点相等，也可以在左子树或者右子树中。 2.8 求两个节点的最近公共祖先 求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子树中。（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。（3）如果两个节点一个在根节点的右子树中，一个在根节点的
第六章树和二叉树习题数据结构
习题六树和二叉树 一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 16．在下列情况中，可称为二叉树的是（）
目前最完整的数据结构1800题包括完整答案树和二叉树答案
第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题
1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 树与二叉树 一.选择题 1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结 点数为（）个。 A．15B．16C．17D．47 2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 A. 5 B. 6 C. 30 D. 32 4.深度为5的二叉树至多有（）个结点。1 A. 16 B. 32 C. 31 D. 10 5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的 结点数至少为（）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 6.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。 A. n=h+m3 B. h+m=2n C. m=h-1 D. n=2 h-1 1深度为n的二叉树结点至多有2n-1 2满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉 树的后序为（）。 A. uwvts B. vwuts C. wuvts D. wutsv 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.在一非空二叉树的中序遍历序列中，根结点的右边（）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为 先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这棵数对应的二叉树。结论（）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。 4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。 1/ 9 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); } 树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结，希望对找工作的同学有所帮助。 二叉树节点定义如下： structBinaryTreeNode { intm_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; 相关链接： 轻松搞定面试中的链表题目 题目列表： 1. 求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历，中序遍历，后序遍历 4.分层遍历二叉树（按层次从上往下，从左往右） 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 7. 求二叉树中叶子节点的个数 8. 判断两棵二叉树是否结构相同 9. 判断二叉树是不是平衡二叉树 10. 求二叉树的镜像 11. 求二叉树中两个节点的最低公共祖先节点 12. 求二叉树中节点的最大距离 13. 由前序遍历序列和中序遍历序列重建二叉树 14.判断二叉树是不是完全二叉树 详细解答 1. 求二叉树中的节点个数 递归解法： （1）如果二叉树为空，节点个数为0 （2）如果二叉树不为空，二叉树节点个数= 左子树节点个数+ 右子树节点个数+ 1 参考代码如下： 1.int GetNodeNum(BinaryTreeNode * pRoot) 2.{ 3.if(pRoot == NULL) // 递归出口 4.return 0; 5.return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1; 6.} 数据结构-二叉树的建立与遍历 《数据结构》实验报告 ◎实验题目:二叉树的建立与遍历 ◎实验目的：1、掌握使用Visual C++6.0上机调试程序的基本方法； 2、掌握二叉树的存储结构和非递归遍 历操作的实现方法。 3、提高自己分析问题和解决问题的能 力，在实践中理解教材上的理论。 ◎实验内容：利用链式存储结构建立二叉树，然后先序输出该二叉树的结点序列，在在本实验中不使用递归的方法，而是用一个栈存储结点的指针，以此完成实验要求。 一、需求分析 1、输入的形式和输入值的范围：根据提示，输入二叉树的括号表示形式，按回车结束。 2、输出的形式：输出结果为先序遍历二叉树所得到的结点序列。 3、程序所能达到的功能：输入二叉树后，该程序可以建立二叉树的链式存储结构，之后按照一定的顺序访问结点并输出相应的值，从而完成二叉树的先序遍历。 4、测试数据： 输入二叉树的括号表示形式:A(B(D(,G)),C(E,F)) 先序遍历结果为:ABDGCEF 是否继续?（是,输入1;否,输入0）:1 输入二叉树的括号表示形式: 二叉树未建立 是否继续?（是,输入1;否,输入0）:0 Press any key to continu e 二概要设计 1、二叉树的链式存储结构是用一个链表来存储一棵二叉树，二叉树中每一个结点用链表中的一个链结点来存储。 每个结点的形式如下图所示。 其中data表示值域，用于存储对应的数据元素，lchild和rchild分别表示左指针域和右指针域，用于分别存储左孩子结点和右孩子结点的存储位置。 2、二叉树的建立 本程序中利用数组存储所输入的二叉树，然后从头到尾扫描数组中的每一个字符根据字符的不同分别执行不同的操作，并用一个存储结点指针的栈辅助完成。在扫描前先申请一个结点作为根结点，也是当前指针所指结点，在二叉树的建立的过程中，每次申请一个新结点，需对其进行初始化，即令lchild域和rchild域为空。按照本程序的思路，二叉树A（B（D（，G）），C（E，F））的链式存储结构如下图所示。二叉树建立的具体过程见详细设计部分。 3、二叉树的先序遍历 在二叉树的先序遍历过程中也需利用一个存储结点指针的栈辅助完成，初始时栈为空，二叉树遍历结束后栈也为空，所以在开始时将头结点入栈，之后根据当前指针所指结点的特性的不同执行不同的操作，以栈空作为二叉树遍历的结束条件。二叉树先序遍历的具体过程见详细设计部分。 数据结构练习（二叉树） 学号31301374 姓名张一博班级软件工程1301 . 一、选择题 1．按照二叉树定义，具有3个结点的二叉树共有 C 种形态。 (A) 3 (B) 4 (C) 5 (D) 6 2．具有五层结点的完全二叉树至少有 D 个结点。 (A) 9 (B) 15 (C) 31 (D) 16 3．以下有关二叉树的说法正确的是 B 。 (A) 二叉树的度为2 (B)一棵二叉树的度可以小于2 (C) 至少有一个结点的度为2 (D)任一结点的度均为2 4．已知二叉树的后序遍历是dabec，中序遍历是debac，则其前序遍历是 D 。 （A）acbed （B）decab (C) deabc (D) cedba 5．将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为 B 。 (A) 98 (B) 99 (C) 50 (D) 没有右孩子 6．对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有 D 为空。 (A) 50 (B) 99 (C) 100 (D) 101 7．设二叉树的深度为h，且只有度为1和0的结点，则此二叉树的结点总数为 C 。 (A) 2h (B) 2h-1 (C) h (D) h+1 8．对一棵满二叉树，m个树叶，n个结点，深度为h，则 D 。 (A) n=h+m (B) h+m=2n (C)m=h-1 (D)n=2h-1 9．某二叉树的先序序列和后序序列正好相反，则下列说法错误的是 A 。 (A) 二叉树不存在 (B) 若二叉树不为空，则二叉树的深度等于结点数 (C) 若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子 (D) 若二叉树不为空，则任一结点的度均为1 10．对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用 A 遍历实现编号。 (A) 先序(B)中序(C)后序(D)层序 11．一个具有1025个结点的二叉树的高h为 C 。 (A) 10 (B)11 (C)11~1025 (D)10~1024 12．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 C 。 ( A) n在m右方(B)n是m祖先 (C) n在m左方(D) n是m子孙 13．实现对任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用 C 存储结构。 (A) 二叉链表(B) 广义表(C)三叉链表(D)顺序 14. 一棵树可转换成为与其对应的二叉树，则下面叙述正确的是 A 。 (A) 树的先根遍历序列与其对应的二叉树的先序遍历相同 (B) 树的后根遍历序列与其对应的二叉树的后序遍历相同 (C) 树的先根遍历序列与其对应的二叉树的中序遍历相同 (D) 以上都不对 二、填空题 1．对一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度；当它为单分支二叉树时，具有最大高度。 第6章树和二叉树 6.1 知识点概述 树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。 1、树的定义 树（Tree）是n（n≥0）个数据元素的有限集合。当n＝0时，称这棵树为空树。在一棵非空树T中： （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 2、树的基本存储结构 （1）双亲表示法 由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的 存储空间（即一维数组）存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。 （2）孩子表示法 将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单 链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。 （3）双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。 （4）孩子兄弟表示法 这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。 3、二叉树的定义 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 4、满二叉树 定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 5、完全二叉树 定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 6、二叉树的性质 问题一：二叉树遍历 1.问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶求该二叉树的高度。 2.设计描述 （1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN 与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。 （2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。 （3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。 3．源程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include 学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990 学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图： 数据结构 实 验 报 告 1. 实验目的和内容： 掌握二叉树基本操作的实现方法2. 程序分析 2.1存储结构 链式存储 2．程序流程 2.3关键算法分析 算法一：Create(BiNode 算法三：PreOrder(BiNode 实验二二叉树的存储结构及各种运算的实现第一题： #include "stdio.h" #include "malloc.h" #define maxsize 66 typedef int datatype; typedef struct node { datatype data ; struct node *lchild,*rchild; } bitree; bitree *Q[maxsize]; bitree *creatree() { char ch; int front,rear; bitree *root,*s; root=NULL; front=1;rear=0; ch=getchar(); while (ch!='#') { s=NULL; if(ch!='@') { s=malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1) root=s; else { if (s&&Q[front]) if(rear%2==0) Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1) front++; } ch=getchar(); } return root; } preorder(bitree *t) //前{ if (t) { printf(" %c ",t->data); preorder(t->lchild); preorder(t->rchild); } } inorder(bitree *t) //中{ if (t) { inorder(t->lchild); printf(" %c ",t->data); inorder(t->rchild); } } postorder(bitree *t) //后{ if (t) { postorder(t->lchild); postorder(t->rchild); printf(" %c ",t->data); } } int height(bitree *t) //高度{ int hl,hr; if(!t) return 0; else { hl=height(t->lchild); hr=height(t->rchild); return ((hl>hr?hl:hr)+1); } } 实验四 二叉树的建立和应用 1、实验目的 （1）熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； （2）重点掌握二叉树的生成、遍历及求深度等算法； （3）掌握运用递归方式描述算法及编写递归C 程序的方法，提高算法分析和程序设计能力。 2、实验内容 按照已知二叉树，从键盘读入节点字符，建立二叉树（ABD#G###CE##FH###） ；分别采用先序、中序、后序遍历该二叉树，分别输出遍历结果。 3、实验步骤 （1）仔细分析实验内容，给出其算法和流程图； （2）用C 语言实现该算法； （3）给出测试数据，并分析其结果； （4）在实验报告册上写出实验过程。 4、测试数据 先序序列： ABDGCEFHjfkdkfakf 中序序列： DGBAECHF 后序序列： GDBEHFCA 5、结构定义 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 6、实验报告要求 实验报告要求书写整齐，步骤完整，实验报告格式如下： 1、［实验目的］ 2、［实验设备］ 3、［实验步骤］ 4、［实验内容］ 5、［实验结果(结论)］ G H B C D E F A 程序如下： #include "stdio.h" #include "string.h" typedef char TElemType ; typedef struct BiNode { TElemType data; struct BiNode * lchild ,* rchild; }BiNode ,*BiTree; BiTree CreateBiTree(BiTree bt) { char ch; B iTree h=NULL; c h=getchar(); i f(ch=='#') bt=NULL; e lse { if((bt=(BiNode *)malloc(sizeof(BiNode)))==NULL) exit(-2); bt->data=ch; bt->lchild=CreateBiTree(h); bt->rchild=CreateBiTree(h); } r eturn(bt); } void PreOrderTraverse(BiTree bt) 衡阳师范学院《数据结构》课程设计题目：树与二叉树的转换 系别：计算机科学系 专业：计算机科学与设计 班级：1302 学生姓名：戴志豪 学号：13190217 指导老师：赵磊 完成日期：2015年1月3号 目录 一．需求分析 (3) 二．概要设析 (3) 三．详细设计 (5) 1.树的建立 (5) 2.一般树转化成二叉树 (6) 3.先序遍历树的递归算法 (7) 4.后序遍历树的递归算法 (7) 5.先序遍历树的非递归算法 (7) 6.后序遍历树的非递归算法 (8) 7.层次序非递归的算法 (9) 四．设计与调试分析 (10) 五．用户手册 (10) 六．测试结果 (11) 七．附录（源程序） (14) 八．总结 (20) 一.需求分析 本程序的功能是对任意树进行递归前序遍历和后序遍历，以及实现树的非递归的前序、 和后序遍历，还有对树的层序遍历以及树与二叉树的转换。 二．概要设计 对于本次设计，需要用到树的建立,树与二叉树的转换算法先序后序二叉树的递归算法; 先序后序非递归算法;层次序遍历算法 1树的建立 用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 BiNode creat()，BiNode stree_creat(char *a,int k)。 开始 Y 参数数组是否空或 N 把数组的值赋给结点的数 返回空指针 递归的给左子树赋值参数变为a[2i+1] 递归的给右子树赋值参数变为a[2i+2] 返回根指针 结束 2一般树转化成二叉树 转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的右孩子。void exchange()，class Tree 3先序遍历树的递归算法 若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序 遍历右子树。void PreOrder(BiNode root)。数据结构树和二叉树习题
数据结构二叉树实验报告
数据结构中二叉树各种题型详解及程序
数据结构-二叉树的建
数据结构练习(二叉树)
数据结构—— 树和二叉树知识点归纳
数据结构二叉树遍历实验报告
数据结构实验报告之树与二叉树
数据结构二叉树的实验报告
数据结构二叉树遍历及线索化后各种操作(绝对无错)
数据结构课程实验(树和二叉树的建立和应用)
数据结构课程设计之-树与二叉树的转换
相关文档
- 数据结构树和二叉树习题及答案
- 计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编8
- 目前最完整的数据结构1800题包括完整答案树和二叉树答案
- 数据结构教程李春葆课后答案第7章树和二叉树
- 计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编6
- 数据结构树与二叉树-精
- 数据结构二叉树习题附标准答案
- 数据结构第六章树和二叉树习题及答案
- 数据结构课程设计之-树与二叉树的转换
- 严蔚敏数据结构(树和二叉树)
- 严蔚敏《数据结构(c语言版)习题集》答案第六章 树和二叉树文库
- 第六章树和二叉树习题数据结构
- 数据结构树和二叉树实验报告
- 数据结构二叉树实验报告
- 数据结构树和二叉树实验报告
- 数据结构第六章树和二叉树习题及答案
- 《数据结构》习题汇编06第六章树和二叉树试题
- 数据结构与算法_ 树和二叉树_
- 数据结构树和二叉树习题(有答案)
- 数据结构树和二叉树习题及答案