第六章 树一名词解释：1 树 2。结点的度 3。叶子 4。分支点 5。树的度6父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树21 哈夫曼树二、填空题1、 树（及一切树形结构）是一种“_分支层次_”结构。在树上，_根_结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的_前驱_。2、 一棵树上的任何结点（不包括根本身）称为根的_。若B是A的子孙，则称A是B的_3、 一般的，二叉树有_二叉树、_只根_的二叉树、只有_左子树_的二叉树、只有_右子树_的二叉树、同时有 左右_的二叉树五种基本形态。4、 二叉树第i(i=1)层上至多有_个结点。5、 深度为k(k=1)的二叉树至多有_个结点。6、 对任何二叉树，若度为2的节点数为n2，则叶子数_。7、 满二叉树上各层的节点数已达到了二叉树可以容纳的_最大值_。满二叉树也是_完全二叉树_二叉树，但反之不然。8、 具有n个结点的完全二叉树的深度为_。9、 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1=in，则结点X无_左孩子_且无_右孩子_；否则，X的左孩子LCHILD(X)的编号为_2i_。（3） 若2i+1n，则结点X无_右孩子_；否则，X的右孩子RCHILD(X)的编号为_为2i+1_。10.二叉树通常有 顺序_存储结构和_链式_存储结构两类存储结构。11.每个二叉链表的访问只能从_根_结点的指针，该指针具有标识二叉链表的作用。12.对二叉链表的访问只能从_根_指针开始，若二叉树为空，则_root_=NULL.13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是_指向孩子的_的指针，或者是_空指针Null_。14.具有n个结点的二叉树中,一共有_2n_个指针域,其中只有_n-1_个用来指向结点的左右孩子，其余的_n+1_个指针域为NULL。15二叉树有不同的链式存储结构，其中最常用的是_二叉链表_与_三叉链表_。16可通过在非完全二叉树的“残缺”位置上增设“_虚结点_”将其转化为完全二叉树。*17以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ if(t!=NULL) if(t-lchild=NULL)&(t-rchild=NULL)_*count+_; countleaf(t-lchild,&count); _ countleaf(t-rchild,&count);_ 18一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成_访问根结点_、_遍历左子树_、_遍历右子树_三项“子任务”。19若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：_、_、_三种，按这三种次序进行的遍历分别称为_、_、_。20树的主要遍历方法有_先序遍历_、_中序遍历_、_后序遍历_等三种。*21判定树的每个_非终端节点_包含一个条件，对应于一次比较或判断，每个_终端节点_对应一种分类结果。22设定T是一判定树，其终端结点为n1,，nk。每个终端结点ni对应的百分为pi（通常将pi称为n1的权）。再假定ni的祖先数为li，这样，按T进行分类的平均比较次数为_。23根据文字说明，请在以下横线处填充适当的语句。采用静态链表作存储结构，设置一个大小为2n-1的数组,令数组每个元素由四个域组成：wt是结点的权值；lchild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下：typedef struct float wt /*权值*/int parent,lchild rchild; /*指针域*/ node; typedef node hftree2*n-1;在这种存储结构上的哈夫曼算法可描述如下：void Huffman(int k,float Wk,hftree T) /*求给定权值W的哈夫曼树T*/int i,j,x,y;float m,n;for(i=0;i2*k-1;i+) Ti.parent=-1;Ti.lchild=-1;Ti.rchild=-1; if(_)Ti.wt=Wi; else Ti.wt=0for(i=0;ik-1;i+) x=0;y=0;m=maxint;n=maxint; for(j=0;jk=i;j+) if(Tj.wtm)&(Tj.parent=-1)n=m;y=_;m=_;x=j; else if(Tj.wtn)&(Tj.parint=-1)n=Tj.wt;y=j; Tx.parent=_;Ty.parent=_; Tk+i.wt=_; Tk+i.lchild=_;Tk+i.rchild=_;24若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的_第一_个结点。25在_先序_遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。*26具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号），则编号最大的分支结点序号是_n/2取整_，编号最小的分支结点序号是_1_，编号最大的叶子结点序号是_n_，编号最小的叶子结点序号是_n/2取整+1_。*27二叉树的先根遍历序列中，除根结点外，任一结点均处在其双亲结点的_后面_。*28先根遍历树和先根遍历与该树对应的二叉树，其结果_相同_。*29树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为_左子树_和右子树_，即使在结点只有一棵子树的情况下，也要明确指出该子树是_左子树_还是_右子树_。*30由_树_转换成二叉树时，其根结点的右子树总是空的。*31哈夫曼树是带权路径度_最小_的树，通常权值较大的结点离根_近_。*32有m个叶子结点的哈夫曼树，其结点总数为_2m-1_。33一棵树的形状如图填空题33所示，它的根结点是_A_，叶子结点是_e,j,k.g.l,o,p,q,r,n,i_，结点H的度是_3_，这棵树的度是_4_，这棵树的深度是_5_，结点F的儿子结点是_j,k_，结点G的父结点是_c_。*34树的结点数目至少为_1_，二叉树的结点数目至少为_0_。35_树_中结点的最大度数允许大于2，而_二叉树_中结点的最大度数不允许大于2。*36结点最少的树为_只有一个结点的树_，结点最少的二叉树为_空二叉树_。37若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为_n-1_。*38任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为_n+1-2m_个。*39现有按中序遍历二叉树的结果为ABC，问有_5_种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_。*40以数据集4，5，6，7，10，12，18为叶结点权值所构造的哈无曼树为_，其带权路径长度为_165_。41有m个叶子结点的哈夫曼树上的结点数是_2m-1_。42已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有_12_个叶子结点。43设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是_。三、单向选择题1 以下说法错误的是 ( 1 )树形结构的特点是一个结点可以有多个直接前趋线性结构中的一个结点至多只有一个直接后继树形结构可以表达(组织)更复杂的数据树(及一切树形结构)是一种分支层次结构任何只含一个结点的集合是一棵树2，以下说法错误的是 ( 3 ) 二叉树可以是空集*二叉树的任一结点都有两棵子树二叉树与树具有相同的树形结构二叉树中任一结点的两棵子树有次序之分3、以下说法错误的是 ( 4 )完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达在三叉链表上，二叉树的求双亲运算很容易实现在二叉链表上，求根，求左、右孩子等很容易实现在二叉链表上，求双亲运算的时间性能很好&4、以下说法错误的是 ( 4 ) *一般在哈夫曼树中，权值越大的叶子离根结点越近哈夫曼树中没有度数为1的分支结点若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树5深度为6的二叉树最多有( )个结点 ( 2 )64 63 32 316将含