给定完全二叉树G=(V，E)，试证明：|E|=2(n-1)，其中n是树叶结点数目．
展开全部
【答案】：证明 G的结点数为|V|，边数为|E|，i个分枝结点，n个叶结点，根据定理有i=n-1．
又|V|=i+n=2n-1，由于G是树，所以又有：
|E|=|V|-1=2n-1-1=2(n-1)．本题所用定理是对于完全m叉树，其树叶数为n，分枝点数为i，则有
(m-1)i=m-1．
由于本题是完全二叉树，m=2，故有i=n-1可用．
又|V|=i+n=2n-1，由于G是树，所以又有：
|E|=|V|-1=2n-1-1=2(n-1)．本题所用定理是对于完全m叉树，其树叶数为n，分枝点数为i，则有
(m-1)i=m-1．
由于本题是完全二叉树，m=2，故有i=n-1可用．
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
