5 properties of binary trees

Binary tree has the following five properties:

#1. At the ith (i>=1) of the binary tree A layer has at most 2＾(i - 1) nodes.

2. A binary tree with depth k (k>=0) has at least k nodes and at most 2＾ｋｋ1 nodes.

3. For any non-empty binary tree, if the number of leaf nodes is n0 and the number of non-leaf nodes with degree 2 is n2, then n0 = n2 +1.

4. The depth of a complete binary tree with n nodes is int_UP (log (2, n 1)).

5. If a complete binary tree with n nodes is taken from top to bottom, the nodes in the same layer are numbered 1, 2, 3 continuously from left to right. ． ． ． ． ． , n, and then store each node in the tree sequentially in a one-dimensional array according to this node number, and call the node numbered i as node i (i>=1 && i<=n), then there is The following relationship:

(1) If i = 1, then node i is the root and has no parent node; if i> 1, then the parent node of node i is node int_DOWN (i / 2 );

(2) If 2*i <= n, then the left child of node i is node 2*i;

(3) If 2*i

(4) If the node number i is an odd number, and i! =1, it is in the right sibling position, then its left sibling is node i-1;

(5) If node number i is an even number, and i! =n, it is in the left sibling position, then its right sibling is node i+1;

(6) The level of node i is int_DOWN (log (2, i)) + 1.

Proof of some properties

Property 1 can be proved through mathematical induction

Proof of property 2:

By property 1 It can be seen that the maximum total number of nodes in layer k can be expressed as 2＾0＋2＾ 1＋...+2^ (k-1) = 2^k-1;

Proof of Property 3:

First, From the perspective of nodes, n1+n2+n0=n, let this be equation (1);

Looking from the perspective of edges, n2 is connected to two edges, n1 is connected to one edge, and n nodes are connected in pairs. We need n-1 sides, and we can get 2*n2+n1=n-1, which is equation (2);

From equation (1)-(2), we can get

n0 -n2=1.

The above is the detailed content of 5 properties of binary trees. For more information, please follow other related articles on the PHP Chinese website!