设二元树t有t片树叶,v1,v2...vt权分别为w1,w2,...wt层深(根到叶的路径长)分为称为T的权,权最小的二元树称为最优二元树.求最优二元树的夫曼算法如下:
给定实数w1,w2,...,wt且w1≤w2≤,...,wt.
(1)连接权为w1,w2的两片树叶,得-一个分支点,其权为w1+w2.
(2)在w1+w2,...,w3,...,wt中选出两个最小的权,连接它们对应的结点(不一定是树叶),得新支点及所带的权.
(3)重复(2),直到形成t-1个分支点,t片树叶为止.
使用哈夫曼算法求带权2,2,3,3,5的最优二元树.
(1)各层的结点个数是多少?
(2)编号为i的结点的父结点(若存在)的编号是多少?
(3)编号为i的结点的第m个孩子结点(若存在)的编号是多少?
(4)编号为i的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?
(5)若结点个数为n,则深度h是n的什么函数关系?
A、p
B、p-1
C、p-2
D、p-3
A、该树一定是一棵完全二叉树
B、树中一定没有度为1的结点
C、树中两个权值最小的结点一定是兄弟结点
D、树中任何一个非叶结点的权值一定不小于下一层任一结点的权值