第六章  树
一．名词解释：
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<=i<=n)的结点X有：
（1） 若i=1,则结点X是_根_____；若i〉1,则X的双亲PARENT(X)的编号为__i/2取整____。
（2） 若2i>n，则结点X无_左孩子_____且无_右孩子_____；否则，X的左孩子LCHILD(X)的编号为__2
i____。
（3） 若2i+1>n，则结点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 hftree[2*n-1];
在这种存储结构上的哈夫曼算法可描述如下：
void Huffman(int k,float W[k],hftree T)          /*求给定权值W的哈夫曼树T*/
{int i,j,x,y;
float m,n;
for(i=0;i<2*k-1;i++)
{  T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1;
  if(________)T[i].wt=W[i];
      else T[i].wt=0
}
for(i=0;i<k-1;i++)
{  x=0;y=0;m=maxint;n=maxint;
    for(j=0;j<k=i;j++)
    if((T[j].wt<m)&&(T[j].parent==-1)){n=m;y=________;m=________;x=j;}
        else if((T[j].wt<n)&&(T[j].parint==-1)){n=T[j].wt;y=j;}
      T[x].parent=________;T[y].parent=________;
      T[k+i].wt=________;
      T[k+i].lchild=________;T[k+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,，结点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  )
①树形结构的特点是一个结点可以有多个直接前趋
②线性结构中的一个结点至多只有一个直接后继

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。