Five important properties of binary tree

Attach a diagram first

nature 1： On the second of the binary tree i There is a maximum of 2^(i-1) Nodes （i≥1）

nature 2： Depth is k At most, the binary tree of 2^k-1 Nodes （k≥1）

Note that 2 Of k Subtract... To the power of 1, instead of 2^(k-1).

The figure above shows a full binary tree , The number of nodes is 2^4 - 1 = 15

nature 3： Any binary tree , If the number of terminal nodes is zero n0, Degree is 2 The node number of is n2, be n0=n2+1

As shown in the figure above ,8–15 Is the number of terminal nodes ,n0 = 8, 1-- 7 For the degree of 2 The node of ,n2 = 7

nature 4： have n The depth of a complete binary tree of nodes is |log2(n)| + 1

（ No greater than log2(n) + 1 The maximum value of logarithm ）

|log2(15)| = 3 , 3 + 1 = 4

nature 5： If there is n Complete binary tree of nodes （ Its depth is |log2(n)| + 1） The nodes of are numbered by sequence （ From the first floor to the |log2(n)| + 1 layer , Left to right for each floor ）, For any node i（1<=i<=n）, Yes

1． If i = 1, Then node i It's the root of a binary tree , Unmarried parents ; If i>1, Then their parents are nodes |i / 2|( integer ).
2． If 2i > n, Then node i No left child （ node i For leaf nodes ）; Otherwise, the left child is the node 2i.
3． If 2i+1>n, Then node i No right child ; Otherwise, the right child is the node 2i+1