如果T是一棵满3叉树(满3元树),且有22个顶点,则它有_____(1)_____个内部顶点,且有_____(2)_____片叶子。
时间: 2024-02-01 17:12:53 浏览: 123
311172020-17182-37B_图论1
我们可以利用满3叉树的性质来解题。
(1) 对于一棵满3叉树,每个内部顶点(非叶子结点)都有3个子节点。因此,如果满3叉树有 $n$ 个顶点,则它有 $m = \lfloor \frac{n}{3} \rfloor$ 个内部顶点。(其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数)
对于这道题,满3叉树有22个顶点,因此它有 $m = \lfloor \frac{22}{3} \rfloor = 7$ 个内部顶点。
(2) 对于一棵满3叉树,每个叶子结点都没有子节点。因此,如果满3叉树有 $n$ 个顶点,则它有 $k = \frac{2n}{3} + 1$ 片叶子。
对于这道题,满3叉树有22个顶点,因此它有 $k = \frac{2 \times 22}{3} + 1 = 15$ 片叶子。
因此,答案是:
(1) 7个内部顶点;
(2) 15片叶子。
阅读全文