数据结构证明题 用数学归纳法证明，本题为2013版高分笔记126页上的题 请详细解答，先谢过各位大神！ 50
设T为一颗二叉树，其所有非叶节点的左，右子树都不为空，设T的双分支节点为n个,则显然其叶子节点有n+1个，我们称其双分支节点为内节点，叶子节点为外节点，I为其内部路径长度...
设T为一颗二叉树，其所有非叶节点的左，右子树都不为空，设T的双分支节点为n个,则显然其叶子节点有n+1个，我们称其双分支节点为内节点，叶子节点为外节点，I为其内部路径长度，是所有n个内节点到根的路径长度之和；E为外部路径长度，是所有n+1个外节点到根的路径长度之和，试证明，E=I+2n(n>=1)
展开
1个回答
展开全部
考虑最简单的情况进行验证：
1个根节点，两个叶子节点；此时，I=0，E=2;E=I+2;
再次考虑3层满二叉树，此时n=3,I=2,E=8,E~=I+2,但是E=2(I+2)
考虑四层满二叉树，n=7,E=8*3=24,I=0+2*1+4*2=10,E=2(I+2)
所以不知道是不是我理解的有问题 ，还是说你让证明的结果有点问题
1个根节点，两个叶子节点；此时，I=0，E=2;E=I+2;
再次考虑3层满二叉树，此时n=3,I=2,E=8,E~=I+2,但是E=2(I+2)
考虑四层满二叉树，n=7,E=8*3=24,I=0+2*1+4*2=10,E=2(I+2)
所以不知道是不是我理解的有问题 ，还是说你让证明的结果有点问题
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
