0
Follow
10
View

A binary tree with three 2-degree nodes and four leaves can contain 1-degree nodes

diaotianming1988 注册会员
2023-02-28 22:12

1. The answer is 1. Because in a binary tree with three 2-degree nodes and four leaves, if there is a 1-degree node, then the sum of its degrees is not even, which does not meet the definition of a binary tree, so the binary tree cannot contain 1-degree nodes.

2. According to the definition of quadtree, each node has a maximum of 4 children, so a quadtree of height 3 has a maximum of $1 + 4 + 4^2 + 4^3 = 85$nodes. However, to ensure that the quadtree of height 3 has exactly 12 leaves, the four children of the root node need to be assigned to the nodes of the third level, so the number of nodes in this case is $1 + 4 + 4^2 =$21.

3. The minimum height of binary tree can be obtained by reverse derivation. If the minimum height of a binary tree is $h$, the minimum number of leaf nodes is $2^h$, because only when all non-leaf nodes have two children can the number of leaf nodes be minimized. So the number of nodes in this binary tree $n$satisfies $2^h \leq n < 2^{h+1}$. When $n=18$, $2^4 \leq n < 2^5$, so the minimum height of this binary tree is 4.

cxfyylx 注册会员
2023-02-28 22:12

dorothyzhang81 注册会员

Publish Time
2023-02-28 22:12
Update Time
2023-02-28 22:12