Home  >  Article  >  How to count binary tree nodes

How to count binary tree nodes

尚
Original
2019-06-10 15:30:0128618browse

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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn