数据结构课后习题(二)
第五章
1.设树T的度为4,其中度为1,2,3,4的节点个数分别为4,2,1,1,则T中的叶结点点数为8
度:某个结点孩子的个数。 树的总结点:N=度度的个数+根节点(1) = 所有度的个数
建立等式: 14+22+31+41+1= 4+2+1+1+e e=8
2.若一颗二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数为=102+51+1-10-5=11
3.有n个叶节点的哈夫曼树的结点总数:N=2n−1
在哈夫曼树中,每增加一个叶节点,就会增加一个新的路径节点,从而每增加一个叶节点会使得总节点数增加1,并且树的根节点是必须存在的。
4.一颗具有1025个结点的二叉树高度为h:11-1025
设树的结点为n,则树的最大高度为n,[最小高度为log2(n+1)] (向上取整)
高度为h的树至多有2^h-1个结点
满二叉树:节点数为2^h-1;
扩充二叉树:不存在度为1的结点
完全二叉树:只有最下面两层的度可以小于2 具有n个结点的完全二叉树的高度为[log2(n+1)],设其某个结点编号为i,则双亲结点编号为[(i-1)/2]
若2i-1 < n , 则该结点有左孩子,孩子编号为 21+1 , 若2i+2 < n ,则该结点有右孩子,孩子编号为2*i+2
5.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左,右孩子的编号,其左孩子的编号小于其右孩子的编号,可采用后序遍历。
遍历:先:根左右 中:左根右 后:左右根
6.n个结点的线索二叉树含有的线索数为n+1