。 2．二叉树的每一个结点至多有<2>棵子树,且子树有<左右>之分。3．树的结点包含一个<数据元素>及若干指向其<子树>的分支,结点拥有的子树数称为<度>,度为0的结点称为<树叶或终端结点>,度不为0的结点称为<非终端结点或分支结点>。 4．对二叉树来说,第k层上至多有<2k-1>个结点。
2 / 8
.
5．前序遍历序列为abc的不同二叉树有<5>种不同形态。
6．二叉树的前序遍历序列为IJKLMNO,中序遍历序列为JLKINMO,则后序遍历序列为。 7．一棵树转化为一棵二叉树后,二叉树没有<右>子树。 8．一棵含有n个结点的完全二叉树,它的高度是<[log2n]+1>。 一棵含有n个结点的完全二叉树,它的高度是<[log2n]+1>。 h-1层最后一个结点的编号2h-1-1 h层第一个结点的编号2h-1 h层最后一个结点的编号2h-1 2h-1≥n≥2h-1 n≥2h-1 h≤logn+1 h= [logn]+1 n=2k-1=>k= log29．深度为k的二叉树至多有<2k-1>个结点。
10．含有n个结点的二叉树用二叉链表表示,有个空链域。 有2n个链域 有n-1个非空链域11．哈夫曼树是带权路径长度<最短>的二叉树。 12．具有m个叶子结点的哈夫曼树共<2m-1>个结点。 13．前序为a,b,c且后序为c,b,a的二叉树有<4>棵。
14．树和二叉树从定义上说是两种不同的数据结构,那么将树转化为二叉树的基本目的是<利用已有的二叉树的算法来解决树的有关问题>。
15．深度为k的完全二叉树至多有<2k-1>个结点；至少有<2k-1>个结点,若按自上而下,从左到右的次序给结点编号<从1开始>,则编号最小的叶子结点的编号是<2k-2+1>。
16．已知完全二叉树的第8层有8个结点,则其叶子结点数为<68>个。 第7层的叶结点总数：26-4 第8层的叶结点总数：8
17．已知完全二叉树的第7层有10个叶子结点,则整个二叉树的结点个数最多为<235>个。 18．已知二叉树有50个叶子结点,且仅有一个孩子的结点数为30,则总结点数为<129>。 设度为i的结点有ni个,共n个结点 有n0+n1+n2=n<结点总数> 0*n0+1*n1+2*n2=n-1<边数> 所以：n0=n2+1 n1=30
19．用数组A[1…n]顺序存储完全二叉树的各结点,则当i ≤/2时,结点A[i]的右孩子是结点。20．一棵二叉树结点的前序序列为A,B,D,E,G,C,F,H,I,中序序列为D,B,G,E,A,C,H,F,I,则该二叉树结点的后序序列为。21．有m个叶子结点的哈夫曼树上的结点数是<2m-1>。
22．设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1和1,则T中叶子结点的个数为<8>。
3 / 8
.
设度为i的结点有ni个 n1=4 n2=2 n3=1 n4=1 n0+n1+n2+n3+n4=n
n-1=0*n0+1*n1+2*n2+3*n3+4*n4
23．6个结点可构造出132种不同形态的二叉树。 高度：6 高度：5 高度：4 高度：3
24．在一棵高度为3的四叉树中,最多含有21 结点。 1+1*4+1*4*4
25．一棵树的广义表表示为a , g >, i > >,结点f的层数为3。假定根结点的层数为0。 26．一棵树的广义表表示为a , g >, i > >,结点k的所有祖先的结点数为2 个。 27．假定一棵三叉树<即度为3的树>的结点个数为50,则它的最小高度为 4 。假定根结点的高度为0。 第一层：30=1个结点 第二层：1×3=3=3个结点 第三层：1×3×3=3=9个结点第四层：1×3×3×3=3=27个结点------------前四层,共40个结点 第五层：50-40=10个结点
28．对于一棵具有n个结点的树,该树中所有结点的度数之和为n-1。 即求边数
29．设二叉树根的高度为1,则：高度为h的完全二叉树的不同二叉树棵数：2h-1,<即最后一层分别有1,2,…,2h-1个结点的完全二叉树>高度为h的满二叉树的不同二叉树棵数：1。 三．判断题
1．<×>二叉树是一棵无序树。
2．<×>若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的中序遍历结果序列的最后一个结点。
3．<√>在一棵二叉树中,假定每个结点只有左子女,没有右子女,对它分别进行中序遍历和后序遍历,则具有相同的遍历结果。
4．<√>在树的存储中,若使每个结点带有指向前驱结点的指针,将在算法中为寻找前驱结点带来方便。 5．<√>二叉树是树的特殊情形。
6．<×>对于一棵具有n个结点的任何二叉树,进行前序、中序或后序的任一种次序遍历的空间复杂度为O。 7．<×>对于一棵具有n个结点,其高度为h的二叉树,进行任一种次序遍历的时间复杂度为O。8．<×>若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的中序遍历结果序列的最后一个结点。
9．<√>线索化二叉树中的每个结点通常包含有5个数据成员。
10．<×>若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点,则它一定是该子树的前序遍历结果序列的最后一个结点。 四．其他
4 / 8
321
.
1．二叉树的遍历方法有哪几种,分别简诉其遍历步骤。 二叉树的遍历方法有先序遍历、中序遍历、后序遍历三种。 <1>先序遍历二叉树算法是： 若二叉树为空,则空操作； 否则
访问根结点； 先序遍历左子树； 先序遍历右子树。 <2>中序遍历二叉树算法是： 若二叉树为空,则空操作； 否则中序遍历左子树； 访问根结点； 中序遍历右子树。 <3>后序遍历二叉树算法是： 若二叉树为空,则空操作； 否则后序遍历左子树； 后序遍历右子树； 访问根结点。2．若按中序遍历二叉树的结果为A,C,B。作出所有能得到这一遍历结果的二叉树。
3．二叉树结点数据采用顺序存储结构,存储数组中,如图所示,画出该二叉树的二叉链式表示形式。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
e a f d g c j h i b 4．已知一棵树的双亲表示如下,其中各兄弟结点是从左到右依次出现的,画出该树及对应的二叉树。 5．写出二叉树的先序,中序和后序遍历序列,并将该二叉树分解为森林。 二叉树的先序遍历序列：ABCDEFGHI 二叉树的中序遍历序列：BDCAFEHIG 二叉树的后序遍历序列：DCBFIHGEA 对应的森林：
6．以知一棵二叉树的先序遍历序列为ABECDFGHIJ,中序遍历序列为EBCDAFHIGJ,试画出这棵二叉树,并写出其后序遍历序列。
后序遍历序列为：EDCBIHJGFA
7．画以数据集{4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树,并求其带权路径长度WPL。
8．设用于通讯的电文仅有8个字母组成,字母在电文中出现的频率分别为7,19,2,6,32,3,21,10。试为这8个字母设计哈夫曼编码。
9．有一棵二叉树,其中序和后序遍历序列分别为dgbaechif,gdbeihfca。画出该二叉树,对该二叉树进行先序线索化,并求该二叉树所对应的森林。
5 / 8
.
10．二叉树以二叉链表结构存储,在下列中序遍历序列算法中填上正确的语句。
Status in_order {if < p !=NULL>
{ <1>in_orderlchild> ; printf < p->data>; <2>in_orderrchild>; } }11．以二叉链表作为存储结构,试完成下列程序
<1>下列函数是中序输出二叉树的各结点,读程序并在每一个空格初填写一个语句或表达式。 void printtree {BiTnode *p;InitStack ; //构造栈s p=<1>BT; s.top=0; while
{ while <<2>p!=NULL > { s.elem[s.top++]=p; <3>p=p->lchild;} if 0>{<4>p=s.elem[--top]; printf <\"%d\<5>p=p->rchild;}} }
<2>所谓二叉树T1和T2是等价的,那就是说,或者T1和T2都是空的二叉树；或者T1和T2都是非空的二叉树,且T1和T2的根结点的值相同,同时T1和T2的根结点的左子树是等价的,且T1和T2的根结点的右子树也是等价的。下面给出了判断二叉树T1和T2是否等价的程序。读程序并在每一个空格初填写一个语句或表达式。
int equalbitre { int equal=0;
if t2==null> equal=1; else if t2!=null> if data= =t2->data>if lchild, t2->lchild>> <3>if rchild, t2->rchild>>equal=1;
return equal; }
12．一棵用二叉链表表示的二叉树,其根指针为root,试写出求二叉树结点数目的算法。 答案一：int Size {if6 / 8
.
return 0; else
return<1+Sizelchild>+Sizerchild>>; } 答案二：i=0;
int in_order { if < p !=NULL>{in_orderlchild> ; printf < p->data>; i++;in_orderrchild>; } return i; }答案三：
void printtree {BiTnode *p; i=0；InitStack ; //构造栈s p=<1>BT; s.top=0; while
{ while { s.elem[s.top++]=p; p=p->lchild;}if 0>{<4>p=s.elem[--top]; printf <\"%d\ i++； p=p->rchild;}} }
13．以二叉链表作为存储结构,试编写求二叉树高度的算法。 int hight{//h1和h2分别是以BT为根的左右子树的高度 if return 0; else{h1=hightlchild>; h2=hightright>; return max{h1,h2}+1; }7 / 8
.
}
14. 对于下图给出的树,指出树中的根结点、叶结点和分支结点。并指出各个结点的度数和层数。 0703班15题
15. 对于表达式**,<1>画出相应的二叉树表示；<2>给出它的前缀表达式；<3>给出它的后缀表达式。 前缀表达式：**+ab+cd-ef 后缀表达式：ab+cd+*ef-*16．已知二叉树中的结点类型用BTNode表示,被定义为: struct BTNode { ElemType data; BTNode *lchild, *rchild; };
其中data为结点值域,lchild和rchild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。 Int DST < BTNode *BT, ElemType x > {
if < BT==NULL > return 0; else {
ifdata==x> { BT = NULL; return 1; } else {iflchild, x>> return 1; if rchild, x>> return 1; else return 0; } } }算法功能：从一棵二叉树中删除根结点值为x的子树,若删除成功则返回1,否则返回0
8 / 8
