数据结构.
1)试推导出含12个节点的平衡二叉树的最大深度,并画出一棵这样的树.
2)假设要在七个城市之间建造天然气输送网,七个城市分别用序号1至7表示,已知两个城市间输气管道的费用如下表所示:
要求:
1,试在总的费用最小的情况下设计出连通七个城市的天然气输送网(给出设计思想)
2,求出建造此天然气输送网的总费用是多少?
谢谢各位了,,急用啊.!!!!!
[解决办法]
1) 含有n个节点的AVL-tree的最大深度log(sqrt(5)(n+1))-2，底数为 (1+sqrt(5))/2
N[k]表示深度为k的avl最少节点数目，N[0]=0, N[1]=1, N[2]=2, N[k]=N[k-1]+N[k-2]+1
接下去, N[3]=4, N[4]=7, N[5]=12
2) 网的最小生成树问题
