The number of leaf nodes of a complete binary tree

A complete binary tree with n nodes, the number of leaf nodes n0 is: n/2 rounded up, or (n 1)/2 rounded down Whole

Extended information:

Complete binary tree

Complete binary tree is a very efficient data structure. A complete binary tree is composed of a full binary tree. elicited. For a binary tree with depth K and n nodes, it is called a complete binary tree if and only if each node corresponds one-to-one with the nodes numbered from 1 to n in the full binary tree with depth K.

Definition

If the depth of the binary tree is h, except for the h-th layer, all other layers (1 ~h-1) The number of nodes has reached the maximum number, and all the nodes in the h-th level are continuously concentrated on the leftmost side. This is a complete binary tree.

Complete binary trees are derived from full binary trees. For a binary tree with depth K and n nodes, it is called a complete binary tree if and only if each node corresponds one-to-one with the nodes numbered from 1 to n in the full binary tree with depth K.

(1) All leaf nodes appear in the k-th layer or k-l layer (the two largest layers)

(2) For any node, if its right subtree The maximum level of is L, then the maximum level of its left subtree is L or L l.

In a binary tree, at most, the degree of the nodes on the bottom two levels can be less than 2, and the nodes on the bottom level are all concentrated in the leftmost positions of the level, then the binary tree becomes complete A binary tree in which the nodes on the lowest level are concentrated in the leftmost positions of the level, and on the last level, a number of nodes on the right are missing, then this binary tree becomes a complete binary tree.

For more technical articles related to frequently asked questions, please visit the FAQ column to learn more!

The above is the detailed content of The number of leaf nodes of a complete binary tree. For more information, please follow other related articles on the PHP Chinese website!