《第6章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《第6章 树和二叉树.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第6章章树和二叉树树和二叉树一、判一、判断断题题1、二叉树是度为二叉树是度为2的有序树。的有序树。1、（、（）2、完全二叉树一定存在度为完全二叉树一定存在度为1的结点。的结点。2、（、（）3、二叉树的遍历结果不是唯一的。二叉树的遍历结果不是唯一的。3、（、（）4、二叉树的遍历是为了在应用中找到一种线二叉树的遍历是为了在应用中找到一种线性次序。性次序。4、（、（）5、一个树的叶子结点，在前序遍历和后序遍历下，、一个树的叶子结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。皆以相同的相对位置出现。5、（、（）6、用二叉树的前序遍历和中序遍历可以得出二叉树、用二叉树的前序遍历和中序遍历可以得出
2、二叉树的后序遍历。的后序遍历。6、（、（）7、完全二叉树中，若一个结点没有左孩子，、完全二叉树中，若一个结点没有左孩子，则它必是叶子。则它必是叶子。7、（、（）8、完全二叉树的存储结构通常采用顺序存储、完全二叉树的存储结构通常采用顺序存储结构。结构。8、（、（）9、赫夫曼树的结点个数不能是偶数。、赫夫曼树的结点个数不能是偶数。9、（、（）10、赫夫曼树无左右子树之分。、赫夫曼树无左右子树之分。10、（、（）二、选择题二、选择题1、一个具有一个具有1025个结点的二叉树的高个结点的二叉树的高h为（为（）A11B10C111025D101024答案：答案：C2、一棵二叉树高度为、一棵二叉树高度为h
3、，所有结点的度或为，所有结点的度或为0、或、或为为2，则这棵二叉树最少有（）个结点。，则这棵二叉树最少有（）个结点。A2hB2h-1C2h+1Dh+1答案：答案：B3、有关二叉树下列说法正确的是（有关二叉树下列说法正确的是（）A二叉树的度为二叉树的度为2B一棵二叉树的度可以小于一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为二叉树中任何一个结点的度都为2答案：答案：B4、对二叉树的结点从、对二叉树的结点从1开始进行连续编号，要求每个开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的结点的编号大于其左、右孩子的
4、编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）次序的遍历实现编号。可采用（）次序的遍历实现编号。A先序先序B.中序中序C.后序后序D.从根开始按层次从根开始按层次遍历遍历答案：答案：C5、由、由3个结点可以构造出多少种不同的二叉树？个结点可以构造出多少种不同的二叉树？（）A2B3C4D5答案：答案：D6、某二叉树、某二叉树T有有n个结点，设按某种顺序对个结点，设按某种顺序对T中的中的每个结点进行编号，编号为每个结点进行编号，编号为1，2，n，且有如，且有如下性质：下性质：T中任一结点中任一结点V，其编号等于左子树上的，其编
5、号等于左子树上的最小编号减最小编号减1，而，而V的右子树的结点中，其最小编号的右子树的结点中，其最小编号等于等于V左子树上结点的最大编号加左子树上结点的最大编号加1。这时是按（）。这时是按（）编号的。编号的。A.中序遍历序列中序遍历序列B.前序遍历序列前序遍历序列C.后序遍历序列后序遍历序列D.层次顺序层次顺序答案：答案：B7、一棵非空的二叉树的先序遍历序列与后序遍历序列、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（正好相反，则该二叉树一定满足（）A所有的结点均无左孩子所有的结点均无左孩子B所有的结点均无右孩子所有的结点均无右孩子C只有一个叶子结点只有一个叶子结点
6、D是任意一棵二叉树是任意一棵二叉树答案：答案：C8、在二叉树结点的先序序列，中序序列和后序序列中，、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（所有叶子结点的先后顺序（）A都不相同都不相同B完全相同完全相同C先序和中序相同，而与后序不同先序和中序相同，而与后序不同D中序和后序相同，而与先序不同中序和后序相同，而与先序不同答案：答案：B9、二叉树的先序遍历和中序遍历如下：二叉树的先序遍历和中序遍历如下：先序先序遍历：遍历：EFHIGJK；中序遍历；中序遍历:HFIEJKG。该。该二叉树根的右子树的根是：二叉树根的右子树的根是：AEBFCGDH答案：答案：C10、已知一算
7、术表达式的中缀形式为已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为，后缀形式为ABC*+DE/-，其前缀形式为，其前缀形式为()A-A+B*C/DEB.-A+B*CD/EC-+*ABC/DED.-+A*BC/DE答案：答案：D11、算术表达式算术表达式a+b*（c+d/e）转为后缀表达式）转为后缀表达式后为（后为（）Aab+cde/*Babcde/+*+Cabcde/*+Dabcde*/+答案：答案：B12、设树、设树T的度为的度为4，其中度为，其中度为1，2，3和和4的结的结点个数分别为点个数分别为4、2、1、1则则T中的叶子数为中的叶子数为（）A5B6C7D8答案：答案：D13
8、、在一棵三元树中度为在一棵三元树中度为3的结点数为的结点数为2个，度个，度为为2的结点数为的结点数为1个，度为个，度为1的结点数为的结点数为2个，个，则度为则度为0的结点数为（的结点数为（）个）个A4B5C6D7答案：答案：C14、设给定权值总数有设给定权值总数有n个，其哈夫曼树的结点个，其哈夫曼树的结点总数为（）总数为（）A不确定不确定B2nC2n+1D2n-1答案：答案：D15、有有n个叶子的哈夫曼树的结点总数为（个叶子的哈夫曼树的结点总数为（）。）。A不确定不确定B2nC2n+1D2n-1答案：答案：D16、下述编码中哪一个不是前缀码（下述编码中哪一个不是前缀码（）。）。A（00，01，
9、10，11）B（0，1，00，11）C（0，10，110，111）D（1，01，000，001）答案：答案：B17、下面几个符号串编码集合中，不是前缀编码的是下面几个符号串编码集合中，不是前缀编码的是（）。）。A0，10，110，1111B11，10，001，101，0001C00，010，0110，1000Db，c，aa，ac，aba，abb，abc答案：答案：B三、二叉树遍历、构建、应用三、二叉树遍历、构建、应用1、二叉树遍历、二叉树遍历v先序先序v中序中序v后序后序v遍历的序列遍历的序列v遍历的算法遍历的算法2、二叉树构建、二叉树构建v已知二叉树的前序（或后序）、中序，构已知二叉树的前序
10、（或后序）、中序，构建二叉树建二叉树v已知二叉链表的先序访问字符序列，构建已知二叉链表的先序访问字符序列，构建二叉树，如二叉树，如先序访问串为：ABCDEGF3、二叉树应用、二叉树应用v构建赫夫曼树构建赫夫曼树v赫夫曼编码赫夫曼编码若一棵赫夫曼树共有若一棵赫夫曼树共有9个顶点，则其叶子节个顶点，则其叶子节点的个数为多少？点的个数为多少？因为：赫夫曼树的构造过程是每权值小的结点产生一个新因为：赫夫曼树的构造过程是每权值小的结点产生一个新的根结点的根结点所以：从赫夫曼树的构造特征可知一个根结点要么就是有所以：从赫夫曼树的构造特征可知一个根结点要么就是有左右孩子，要不就无孩子左右孩子，要不就无孩子(叶子叶子)所以：赫夫曼树的总顶点所以：赫夫曼树的总顶点(结点结点)数叶子结点数数叶子结点数+度为度为2的结的结点数点数又因为：由前面提到的二叉树的性质又因为：由前面提到的二叉树的性质3：n0=n2+1所以：总顶点数所以：总顶点数(9)=n0+n2即：总顶点数即：总顶点数(9)=n2+1+n2所以：所以：n2=4所以：所以：n0=5