data structures - For "any" binary tree, what is the relation between all nodes and internal nodes -
the original question below.
for any binary tree n nodes , internal nodes, relation between n , _____ <= i.
in opinion
i thought n/2 <= i, can't not figure out condition let n/2 = i. want ask root node internal node?
in full tree there 1 + 2 + ... + 2^(h-1)
internal nodes , 2^h
leaf nodes (where h
height of tree).
that means total number of nodes
n = 1 + 2 + .... + 2^h = 2^(h+1)-1 = 1 + 2 + ... + 2^h-1 = 2^h - 1
now, relation looking for:
n-i = 2^h+1 - 1 - 2^h + 1 = 2^h+1 - 2^h = 2*2^h - 2^h = 2^h
since 2^h = i+1
, get:
n - = i+1 n - 1 = 2i (n - 1)/2 =
(note there no issue non integer result, since n
odd in full tree).
now, have left show full tree indeed 1 highest such ratio (this left reader).
Comments
Post a Comment