第六章 树和二叉树
第一次作业
6.1试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 分析：一棵度为2的有序树与一棵二叉树的区别是：度为2的树有二个分支，没有左右之分；一棵二叉树也有两个分支，但有左右之分，且左右不能交换.
3
3个结点的二叉树：
6.4先序中序后序遍历二叉树
一个深度为H 的满k 叉树有如下性质：第H 层上的结点都是叶子结点，其余各层上每个结点都有k 棵非空子树。如果按层次顺序（同层自左至右）从未有过开始对全部结点编号，问：
（1）    各层的结点数目是多少？
（
2）    编号为i 的结点的双亲结点（若存在）的编号是多少？
（3）
编号为i 的结点的第j 个孩子结点（若存在）的编号是多少？
（4）    编号为
i 的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 解：
（1）    K i -1
（2）  i =1时，该节点为根，无父节点；
否则其父节点编号为(2)i k k +-⎢⎥⎢⎥⎣⎦
（k ≥2） 分析：编号为p 的孩子结点的范围[（p -1）*k +2, p *k +1] 得出(i -1)/k ≤p ≤(i -2)/k +1
（3） K *i +j +1-k
（4）(i -1)MOD K <>0，该结点有右兄弟，其右兄弟的编号是i +1
6.5 已知一棵度为k 的树中有1n 个度为1的结点，2n 个度为2的结点，…，k n 个度为k 的结点，问该树中有多少个叶子结点?
解: ∑=-+
=k 1i i 0n )1i (1n
分析：
结点总数：n=n 0+n 1+n 2+……+n k ，n=1+n 1+2n 2+……+kn k
所以得n 0 = n 2 + 2n 3 + …… + (k -1)n k + 1  6.6 已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点，试求该树的叶子结点数目
解：
度：一个结点含有的子树的个数称为该节点的度；
设有n k 个度为k 的分支结点，n 0个度为0的分支结点
各点度数总和为：n=k*n k +1,
最后计算得到叶节点个数为n-(n-1)/k  。
第二次作业
6.3描述满足下列条件的二叉树形态：
（1）先序遍历序列与中序遍历序列相同；
（2）后序遍历序列与中序遍历序列相同；
（3）先序遍历序列与后序遍历序列相同；
答：先序遍历DLR ，中序遍历LDR ，后序遍历LRD ；
（1）各结点均无左孩子；
（2）各结点均无右孩子；
（3）只有一个根节点
（或三个答案中都加入空二叉树也正确）
6.8 画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列 答：
先根遍历序列：ABCEIJFGKHD；后根遍历序列：BIJEFKGHCDA 6.9 将题目所示的森林转化为相应的二叉树
6.10 画出给出二叉树相应的森林
答：
6.11 已知某二叉树的中序序列为DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树
答：
6.14 假设某电文由（a,b,c,d,e,f,g,h）8个字母组成，每个字母在电文中出现的次数分别为（7,19,2,6,32,3,21,10），试解答下列问题：
（1）画出huffman树；
（2）写出每个字母的huffman编码；
（3）在对该电文进行最优二进制编码处理后，电文的二进制位数。
答：（1）
（2）a:1100; b:00; c:11110; d:1110; e:10; f:11111; g:01; h:1101
（3）
8
1
261 i i
i
l ω
=
=
∑
6.17 写出按层次遍历二叉树的算法6.47
void LayerOrder(Bitree T)//层序遍历二叉树
{
InitQueue(Q); //构造一个空队列Q
EnQueue(Q,T);//插入元素T为Q的新队尾元素while(!QueueEmpty(Q))//若为空，则返回ture  {
DeQueue(Q,p);//删除对头元素，用p返回
visit(p);//对结点操作
if(p->lchild) EnQueue(Q,p->lchild);
if(p->rchild) EnQueue(Q,p->rchild);
}
}//LayerOrder
6.21 写出统计树中叶子节点个数的算法，树用孩子兄弟的链表表示。
int LeafCount_CSTree(CSTree T)//求孩子兄弟链表表示的树T的叶子数目{
if(!T->firstchild) return 1; //叶子结点
else
{
count=0;
for(child=T->firstchild;child;child=child->nextsib)
count+=LeafCount_CSTree(child);
return count; //各子树的叶子数之和
}
}//LeafCount_CSTree

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