数据结构课后习题(二)

第五章

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