试证明：高度为h的2-3树中叶子结点的数目在2h-1与3h-

[问答题]

试证明：高度为h的2-3树中叶子结点的数目在2h-1与3h-1之间。

推荐

赞花婆

在2-3树中，每个内部结点（非叶子结点）有两个或三个孩子，而且所有叶子都在同一层上；

一方面，若某棵2-3树只包含2-结点，则就是一颗满二叉树。高度为h的满二叉树的叶子结点数是2^（h-1）;

另一方面，若某棵2-3树只包含3-结点，那么第i层的结点数目为3^（i-1）。高度为h的“3树”的叶子结点数是3^（h-1）;

高度为h的2-3树中叶子结点数目在2^（h-1）与3^(h-1)之间。

发表于 2018-03-25 09:55:25 回复(0)

提交观点

问题信息

树

上传者：赞花婆

难度：

1条回答 3收藏 2320浏览

扫一扫，把题目装进口袋