第6章 树和二叉树 例题精讲1. 一棵二叉树的叶结点终端结点数为5单分支结点数为2该树共有11个结点。解析叶结点数为5 双分支结点数为4单分支结点数为2共有54211个结点。2. 设一棵哈夫曼树共有11个非叶结点则该树有D个叶结点。A. 22B. 10C. 11D. 12解析哈夫曼树除叶结点外全为双分支结点。二叉树中叶结点比双分支结点数多1。11个非叶结点 双分支结点数11 叶结点数123. 设一棵哈夫曼树共有18个叶结点则该树共有C个结点。A. 37B. 19C. 35D. 174. 一棵具有38个结点的完全二叉树最后一层有A个结点。A. 7B. 5C. 6D. 8解析在一棵二叉树中除最后一层外若其余层都是满的并且最后一层或者是满的或者在最右边缺少连续若干个结点则此树为完全二叉树。而满二叉树是完全二叉树的特例。前5层12481631第6层38-3175. 一棵完全二叉树共有6层且第6层上有6个结点该树共有D个结点。A. 38B. 72C. 31D. 37解析前5层12481631第6层6总共316376. 在一棵二叉树中编号为13的结点的双亲结点的顺序编号为D。A. 34B. 7C. 9D. 6解析二叉树的编号按完全二叉树的编号分准。若父节点编号为i则子结点编号为2i和2i1。2i113 i67. 在一棵二叉树中编号为3的结点的右孩子的结点的顺序编号为B。A. 5B. 7C. 8D. 68. 一棵有20个结点的二叉树采用链式存储其中共有A个指针域为空。A. 21B. 20C. 19D. 18解析n个结点 有2n个指针域。除根结点外每个结点前有一个指针。 共有n-1个指针。空指针域为2n-(n-1)n19. 设有一棵采用链式存储的二叉树除叶结点外每个结点度数都为2该树结点中共有20个指针域为空则该树有D个叶结点。A. 21B. 22C. 9D. 10解析20个指针域为空 共有19个结点。除叶结点外每个结点度数都为2 叶结点以外的结点都为双分支节点。理论“叶结点比双分支节点多1。” 设叶结点数为n则总结点数nn-12n-119 n10。10. 设有一棵采用链式存储的哈夫曼树该树的结点中共有20个指针域为空则该树共有C个非叶子结点。A. 21B. 22C. 9D. 10解析哈夫曼树只有叶子结点和双分支节点。20个指针域为空 共有19个结点。由“叶结点比双分支节点多1”设双分支节点数为n则叶结点数为n1总结点数nn119 n911. 一棵采用链式存储的二叉树中共有n个指针域被有效使用即指针域为非空。该二叉树有A个结点。A. n1B. nC. n-1D. n-2解析除根结点外每个结点对应一个指针。12. 设有一棵采用链式存储的二叉树除叶结点外每个结点度数都为2该树结点中共有2n个指针域为空。则该树有D个叶结点。A. 2nB. 2n1C. 2n2D. n解析:有2n个指针域为空 有2n-1个结点。除叶结点外每个结点度数都为2 除叶结点外全是双分支结点。“叶结点比双分支节点多1” 设叶结点数为x则总结点数x(x-1)2x-12n-1所以xn。13. 设有一棵采用链式存储的二叉树除叶结点外每个结点度数都为2该树结点中共有10个指针域为空。则该树有D个非叶结点。A. 11B. 10C. 9D. 4解析:有10个指针域为空 有9个结点。除叶结点外每个结点度数都为2 除叶结点外全是双分支结点。“叶结点比双分支节点多1” 设非叶结点数为x则总结点数x(x1)2x12x19所以x414. 先序遍历下述二叉树将结果填入下表中abdghecf解析先序访问根节点 → 遍历左子树 → 遍历右子树15. 中序遍历下述二叉树将结果填入下表中dgbheacf解析中序遍历左子树→ 访问根节点→ 遍历右子树16. 后序遍历下述二叉树将结果填入下表中gdehbfca解析后序遍历左子树 → 遍历右子树 → 访问根节点17. 已知权重a, b, c, d, e3, 5, 6, 7, 9构造Huffman树。求该树的Huffman编码和带权路径长度。解构造Huffman树Huffman编码a:000b:001c:10d:11e:01带权路径长度3*35*39*26*27*29151812146818. 以1233为叶结点的权构造两棵不同高度的哈夫曼树分别求它们的带权路径长度。解两棵不同高度的哈夫曼树如下左边的带权路径长度为1*32*33*23*118右边的带权路径长度为1*22*23*23*21819. 已知一棵有15个结点的二叉树根结点的右子树有6个结点对其进行先序遍历的第一个结点是7问在中序遍历该二叉树的结果序列中7处于第几个位置。答7处于第8个位置.解析根结点的右子树有6个结点 根结点的左子树有8个结点68115。先序遍历的第一个结点是7 7一定是根结点。因为中序遍历时先访问根结点的左子树再访问根结点最后访问根结点的右子树。所以中序遍历时根结点处于第819的位置。20. 先序遍历时序列为stuwvh中序遍历序列为uwtvsh求二叉树。答二叉树如下解析由先序stuwvh s是根由中序uwtvsh h是根s的右子树由先序tuwv t是左子树的根由中序uwtv v是t的右子树uw是t的左子树由先序uw u是左子树根由中序uw 左子树空右子树w21. 后序遍历efcdb中序ecfbd求该二叉树及先序遍历序列。答二叉树如下先序遍历序列为bcefd解析由后序efcdb b为根由中序ecfbd d为右子树ecf为左子树由后序efc c为根由中序ecf e为左子树f为右子树22. 以下程序是后序遍历二叉树的递归算法的程序完成程序中空格部分树结构中左、右指针域分别为left和right数据域data为字符型BT指向根结点。void Postorder(struct BTreeNode *BT){if(BT!NULL){Postorder(BT-left);Postorder(BT-right);printf(“%c”,BT-data);}}23. 以下程序是先序遍历二叉树的递归算法的程序完成程序中空格部分树结构中左、右指针域分别为left和right数据域data为字符型BT指向根结点。void Postorder(struct BTreeNode *BT){if(BT!NULL){printf(“%c”,BT-data);Postorder(BT-left);Postorder(BT-right);}}24.以下程序是中序遍历二叉树的递归算法的程序完成程序中空格部分树结构中左、右指针域分别为left和right数据域data为字符型BT指向根结点。void Postorder(struct BTreeNode *BT){if(BT!NULL){Postorder(BT-left);printf(“%c”,BT-data);Postorder(BT-right);}}