Type of Binary Trees
A binary tree is full
if every node contains 0 or 2 children.
A binary tree is complete:
If all levels, except possibly the last level, contain all possible nodes and all nodes in the last level are as far left as possible.
A binary tree is perfect if all internal nodes have 2 children and all leaf nodes are at the same level.

Which of the following are complete and full, but NOT perfect binary trees?

Question

Type of Binary Trees
A binary tree is full
if every node contains 0 or 2 children.
A binary tree is complete:
If all levels, except possibly the last level, contain all possible nodes and all nodes in the last level are as far left as possible.
A binary tree is perfect if all internal nodes have 2 children and all leaf nodes are at the same level.

Which of the following are complete and full, but NOT perfect binary trees?

BlackTom AI · Accepted Answer

D is correct because that tree is both full and complete, but its leaves are not all on the same level so it is not perfect.

1) Relevant concepts
- Full: every node has either 0 or 2 children (no node with exactly one child).
- Complete: every level except possibly the last is completely filled, and nodes on the last level are as far left as possible.
- Perfect: full plus all leaves at exactly the same depth.

2) Step-by-step reasoning for each option
- Check A: Inspecting A, every internal node has two children (so A is full). Also every level up to the last is full and the last level is filled left-to-right with no holes, and all leaves appear at the same depth. Because all leaves are at the same level, A is perfect. The question asks for trees that are complete and full but NOT perfect, so A is excluded because it is perfect.

- Check B: Look at B and find an internal node that has only one child (a single child on the right subtree near the top). That violates the “full” definition (0 or 2 children). Therefore B is not full (even if it might be complete), so it cannot be an answer.

- Check C: In C there are internal nodes with two children (so parts are full), but the placement of nodes in the last level leaves a gap that violates the “as far left as possible” requirement — the last level is not left-packed. That means C is not complete (even if it is full), so C is excluded.

- Check D: Every internal node in D has exactly two children (so it is full). Levels above the last are fully filled and any nodes on the last level are left-packed, so it satisfies completeness. However, some leaves are at a shallower depth than others (leaves are not all at the same level), so it is not perfect.

3) Why the correct answer is correct
D meets both required properties (full and complete) and fails the perfect criterion (leaf depths differ). The other diagrams each fail at least one required property (A is perfect, B is not full, C is not complete).

Final confirmation: only D is complete and full but NOT perfect, which matches the provided answer D.

类似问题

How many children can a node have in a binary tree?

A perfect binary tree has leaves at least a half of the total number of nodes.

How many nodes in a perfect binary tree if the tree has 4 levels?

Which XXX would replace the missing statement in the given RBTreeReplaceChild utility function? RBTreeReplaceChild(parent, currentChild, newChild) { if (parent⇢left == currentChild) return RBTreeSetChild(parent, "left", newChild) XXX return RBTreeSetChild(parent, "right", newChild) return false }

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单