How to count binary tree nodes

1. The i-th level of the binary tree has at most 2^(i-1) nodes

2. The binary tree with depth h has at most 2^k- 1 node

3. For a binary tree, if it contains n0 leaf nodes and n2 nodes with degree 2, there must be a relationship: n2=n0-1

4. The depth of a complete binary tree with n nodes is [log2n] 1. [] means rounding

5. If the depth of a complete binary tree with n nodes is from top to bottom and from left to Numbering from 1 to n on the right, then for any node numbered i in the complete binary tree:

If i=1, then the node is the root of the binary tree and has no parents, otherwise, the number is [ The node i/2] is its parent node;

If 2i>n, then the node has no left child node, otherwise, the node numbered 2i is its left child node;

If 2i 1>n, then the node has no right child node, otherwise, the node numbered 2i 1 is its right child node.

If the number of nodes of a complete binary tree is n, find the height h of the numbers n0, n1, n2, the number of left child nodes nl and the number of right child nodes nr?

(n0 is a node with degree 0, n1 is a node with degree 1, n2 is a node with degree 2)

The above is the detailed content of How to count binary tree nodes. For more information, please follow other related articles on the PHP Chinese website!