一棵高度为h(h≥1)的完全二叉树至少有几个结点,为什么,请形象一点描述
时间: 2024-01-02 19:57:37 浏览: 229
一棵高度为h(h≥1)的完全二叉树至少有2^(h-1)个节点。
这是因为完全二叉树的定义是:除了最后一层外,每一层都是满的,并且最后一层的结点都靠左排列。
因为最后一层结点不一定满,所以最少有2^(h-1)个结点。可以想象,一棵高度为1的完全二叉树只有一个根节点,高度为2的完全二叉树有一个根节点和两个子节点,高度为3的完全二叉树有一个根节点、两个子节点各有两个子节点,共7个节点。因此,每增加一层,节点数就会至少翻倍,所以节点数最少为2^(h-1)个。
阅读全文