第7章_二叉树

1、1李云清李云清 杨庆红杨庆红 揭安全揭安全高等学校精品课程高等学校精品课程（第（第2版）版）（第（第2版）版）234567089101112131415abdecf16abdcgfe 0 1 2 3 4 5 6 lchild data rchild root=0 n=717181920abdcgfeagfedbc root21222324abdfegc25262728293031ABCDE32333435363738ABCDE39ABCDE40ABCDE41ABCDE42ABCDE43ABCDE4445464748495051525354555657abcdfegabcdfeg58596061

2、6263646566676869abcdefgabcdefgabcdefgabcdefg70abcdefghiabcdefghiabcdefghiabcdefghi7172abdecfghiabdecfghiabdecfghiabdecfghi73747576习题习题77.1 选择题。选择题。（1）前序遍历和中序遍历结果相同的二叉树为（）；前序）前序遍历和中序遍历结果相同的二叉树为（）；前序遍历和后序遍历结果相同的二叉树为（）。遍历和后序遍历结果相同的二叉树为（）。A一般二叉树一般二叉树B只有根结点的二叉树只有根结点的二叉树C根结点无左孩子的二叉树根结点无左孩子的二叉树D根结点无右孩子的二叉树

3、根结点无右孩子的二叉树E所有结点只有左子树的二叉树所有结点只有左子树的二叉树 F所有结点只有右子树的二所有结点只有右子树的二叉树。叉树。（2）以下有关二叉树的说法正确的是（）。）以下有关二叉树的说法正确的是（）。A二叉树的度为二叉树的度为2B一棵二叉树的度可以小于一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为二叉树中至少有一个结点的度为2D二叉树中任一个结二叉树中任一个结点的度均为点的度均为277（3）一棵完全二叉树上有）一棵完全二叉树上有1 001个结点，其中叶子结点的个个结点，其中叶子结点的个数为（）。数为（）。A250B500C254D501（4）一棵完全二叉树有）一棵完全二叉树

4、有999个结点，它的深度为（）。个结点，它的深度为（）。A9B10C11D12（5）一棵具有）一棵具有5层的满二叉树所包含的结点个数为（）。层的满二叉树所包含的结点个数为（）。A15B31C63D32 7.2 用一维数组存放完全二叉树：用一维数组存放完全二叉树：A B C D E F G H I，则后，则后序遍历该二叉树的结点序列为（）。序遍历该二叉树的结点序列为（）。7.3 有有n个结点的二叉树，已知叶结点个数为个结点的二叉树，已知叶结点个数为n0，则该树中，则该树中度为度为1的结点的个数为（）；若此树是深度为的结点的个数为（）；若此树是深度为k的完全二的完全二叉树，则叉树，则n的最小值为（

5、）。的最小值为（）。787.4 设设F是由是由T1、T2和和T3三棵树组成的森林，与三棵树组成的森林，与F对应的二对应的二叉树为叉树为B。已知。已知T1、T2和和T3的结点数分别是的结点数分别是n1、n2和和n3，则二叉树则二叉树B的左子树中有（）个结点，二叉树的左子树中有（）个结点，二叉树B的右子树的右子树中有（）结点。中有（）结点。7.5 高度为高度为k的二叉树的最大结点数为（），最小结点的二叉树的最大结点数为（），最小结点数为（）。数为（）。7.6 对于一棵具有对于一棵具有n个结点的二叉树，该二叉树中所有结点个结点的二叉树，该二叉树中所有结点的度数之和为（）。的度数之和为（）。797.7

6、 已知一棵二叉树如图已知一棵二叉树如图7.12所示，试求：所示，试求：（1）该二叉树前序、中序和后序遍历的结果；）该二叉树前序、中序和后序遍历的结果；（2）该二叉树是否是满二叉树？是否是完全二叉树？）该二叉树是否是满二叉树？是否是完全二叉树？（3）将它转换成对应的树或森林；）将它转换成对应的树或森林；（4）这棵二叉树的深度为多少？）这棵二叉树的深度为多少？（5）试对该二叉树进行前序线索化；）试对该二叉树进行前序线索化；（6）试对该二叉树进行中序线索化。）试对该二叉树进行中序线索化。图图7.12 一棵二叉树一棵二叉树807.8 试述树和二叉树的主要区别。试述树和二叉树的主要区别。7.9 试分别画

7、出具有试分别画出具有3个结点的树和具有个结点的树和具有3个结点的二叉树的个结点的二叉树的所有不同形态。所有不同形态。7.10 已知一棵二叉树的中序遍历的结果为已知一棵二叉树的中序遍历的结果为ABCEFGHD，后，后序遍历的结果为序遍历的结果为ABFHGEDC，试画出此二叉树。，试画出此二叉树。7.11 已知一棵二叉树的前序遍历的结果为已知一棵二叉树的前序遍历的结果为ABCDEF，中序，中序遍历的结果为遍历的结果为CBAEDF，试画出此二叉树。，试画出此二叉树。7.12 若一棵二叉树的左、右子树均有若一棵二叉树的左、右子树均有3个结点，其左子树的个结点，其左子树的前序序列与中序序列相同，右子树的

8、中序序列与后序序列相前序序列与中序序列相同，右子树的中序序列与后序序列相同，试画出该二叉树。同，试画出该二叉树。7.13 分别采用递归和非递归方式编写两个函数，求一棵给分别采用递归和非递归方式编写两个函数，求一棵给定二叉树中叶子结点的个数。定二叉树中叶子结点的个数。7.14 试编写一个函数，将一棵给定二叉树中所有结点的左、试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。右子女互换。817.15 试编写一个函数，返回一棵给定二叉树在中序遍历下试编写一个函数，返回一棵给定二叉树在中序遍历下的最后一个结点。的最后一个结点。7.16 试编写一个函数，返回一棵给定二叉树在前序遍历下试编写一个函数，返回一棵给定二叉树在前序遍历下的最后一个结点。的最后一个结点。7.17 试编写一个函数，返回一棵给定二叉树在后序遍历下试编写一个函数，返回一棵给定二叉树在后序遍历下的第一个结点。的第一个结点。7.18 假设二叉树采用链式方式存储，假设二叉树采用链式方式存储，root为其根结点，为其根结点，p指指向二叉树中的任意一个结点，编写一个求从根结点到向二叉树中的任意一个结点，编写一个求从根结点到p所指所指结点之间路径长度