习题6答案--树和二叉树
习题6 树和二叉树
1. 名词解释
（1）二叉树
二叉树（binary tree）是树的度≤2的有序树。
（2）满二叉树
在一棵二叉树中，如果每层的结点都是满（不能再多）的，就称之为满二叉树。
（3）完全二叉树
对一棵满二叉树中的结点按从上至下、从左到右的顺序进行编号，如果从最后一个结点开始按编号递减的次序删除m（m≥0）个结点后得到的二叉树称为完全二叉树。
（4）线索二叉树
在二叉链表中的空闲指针域中存放某种遍历过程中得到的结点的前导或后继信息，并为链表中的每个结点增加两个标记域lflg和rflg，且作以下约定：如果lflg 为0时，lchild域存放结点的左孩子指针，否则，lchild域存放结点的前导指针；如果rflg为0时，rchild域存放结点的右孩子指针，否则，rchild域存放结点的后继指针。通常把采用这种存储结构的二叉树称为线索二叉树。
（5）树的带权路径长度
如果树中的每个叶子上都附带有一个权值，则通常把树中所有叶子的带权路径长度之和称为树的带权路径长度。
2. 填空题
（1）树是n（n≥0）个结点的有限集合，在一棵非空树中，有且仅有一个（根结点），其余结点分成m（m≥0）棵（互不相交）的子树。
（2）树中某结点的子树的个数称为该结点的（度），子树的根结点称为该结点的（孩子），该结点称为其子树根结点的（双亲）。
（3）一棵深度为k的正则二叉树（没有度为1的结点的二叉树）至少有（2k-1）个结点。
（4）一棵含有11个顶点的正则二叉树的最大深度可以是（6），最小深度可以是（4）。
（5）一棵深度为k的满二叉树的叶子有（2k-1）个。
（6）一棵深度为k的完全二叉树的结点至多有（2k-1）个，至少有（2k-1）个。（7）已知完全二叉树的第6层（从0层开始计）有10个叶子，则整个二叉树的结点数最多是（235）个。
说明：在完全二叉树中叶子只能出现在最底两层，故n=(27-1)+(26-10)*2
（8）具有n0个叶子的二叉树至少含有（2n0-1）个结点。
按二叉树性质可知，n=n0+n1+n2，n0=n2+1，故：n=2n0+n1-1，显然，n1最少时，n就最少，故，n=2n0-1。
（9）一棵含有n个结点的m叉树，可能达到的最大深度是（n），可能达到的最小深度是（（int）log m n+1，即完全m叉树）。
（10）已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…，n m个度为m的结点，问该树中有（n2+ 2n3+ 3n4+……+(m-1)×n m）个叶子结点。（11）已知一棵共有n个结点的树，其中所有分支结点的度均为k，则该树的叶子个数为（(n(k-1)+1)/k）。
证明：显然有b=n-1，b=kn k，n=n k+ n0，可得结论。
（12）已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（-+A*BC/DE）。
（13）算术表达式A+B*(C+D/E)转为后缀表达式后为（ABCDE/+*+）。（14）有n个叶子的哈夫曼树的结点总数为（2n-1）个。
（15）利用二叉链表（孩子兄弟表示法）存储树，则根结点的右指针为（空）值。
3. 简答题
（1）请简述一棵度为2的树与一棵二叉树之间的区别。
度为2的树是指树中结点的度的最大值为2，不一定是有序树。二叉树是有序树，二叉树的度可以为2，也可以为1或0。度为2的树可能是一棵二叉树，一棵二叉树也可能是度为2的树。
（2）一棵含70个结点的完全二叉树采用本书讲述的顺序存储结构存储，请问：
（A）最后一个非叶子结点的序号位置是多少？34
（B）序号为40的结点的双亲的序号位置是多少？19
（C）序号为20的结点的左孩子和右孩子的序号位置分别是多少？41,42（D）该树是否存在度为1的结点？是
（E）该树的叶子共有多少个？35
（F）该树的深度是多少？7
（3）根据先根序、中根序遍历写出后根序遍历序列。
先根序遍历序列：ABDGECFH
中根序遍历序列：DGBEACHF
后根序遍历序列：GDEBHFCA
（4）请分别分析满足下面条件的所有非空二叉树应是什么样的：①前根序序列和中根序序列相同；②中根序序列和后根序序列相同；③前根序序列和后根序列相同。
①右单支二叉树②左单支二叉树③只有根结点
（5）假设用于通讯的电文仅由8个字母{A，B，C，D，E，F，G，H}组成，字母在电文中出现的频率分
别为{7，19，2，6，32，3，21，10}。试为这8个字母设计Huffman编码。
3. 编程题
（1）已知某二叉树采用二叉链表存储结构，编写交换二叉树（每个结点）的左右孩子的算法。
void BTreeExchangeChild(BKBTree root)
{
BKBTree p;
if(root)
{
p=root->lchild;
root->lchild=root->rchild;
完全二叉树算法root->rchild=p;
if(root->lchild)
BTreeExchangeChild(root->lchild);
if(root->rchild)
BTreeExchangeChild(root->rchild);
}
}
（2）已知某二叉树采用二叉链表存储结构，编写统计出二叉树中度为1结点的数目的算法。
int BTreeD1(BKBTree root)
{
if(root==NULL || !root->lchild && !root->rchild)return 0;
else if(root->lchild && root->rchild )
return BTreeD1(root->lchild )+BTreeD1(root->rchild);
else
return 1+ BTreeD1(root->lchild )+BTreeD1(root->rchild);
}
（3）已知某二叉树采用顺序存储结构，编写求距离i和j两个结点的最近交汇结点的算法，最近交汇结点是指从结点i到根结点的路径与结点j到根结点的路径的最近交点，特殊情况包括：如果结点i与结点j是同一结点则结点i和结点j都是最近交汇结点，如果结点i是结点j的祖先，则结点i是最近交汇结点，如果结点j是结点i的祖先，则结点j是最近交汇结点。
BOOL BTreeCrossNode(SeqTree T, int *pcrossnode, int i, int j,
BOOL (*equal)(BTreeDT,BTreeDT))
{
BOOL flg=TRUE;
if(i<0 || i>T.spacesize-1 || (*equal)(T.base[i], T.nullvalue)
|| j<0 || j>T.spacesize-1 || (*equal)(T.base[j], T.nullvalue))
flg=FALSE;
else
{
while(i!=j)
{
if(i>j)
i=(i-1)/2;
else if(i<j)
j=(j-1)/2;
}
*pcrossnode=i;
}
return flg;
}
（4）已知某二叉树采用三叉链表存储结构，p和q为二叉树中两个结点的指针，试编写求p、q两个结点最近交汇结点的算法。

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