In computer science, a binary tree is a tree structure with at most two subtrees per node. Usually subtrees are called "left subtree" and "right subtree". Binary trees are often used to implement binary search trees and binary heaps.
A binary tree with depth k and 2^k-1 nodes is called a full binary tree. The characteristic of this kind of tree is that the number of nodes on each level is the maximum number of nodes. In a binary tree, except for the last level, if all other levels are full, and either the last level is full, or there are several consecutive nodes missing on the right, then the binary tree is a complete binary tree. The depth of a complete binary tree with n nodes is floor(log2n) 1. A complete binary tree with depth k has at least 2k-1 leaf nodes and at most 2k-1 nodes.
A certain binary tree has 5 nodes with degree 2. What is the number of leaf nodes of this binary tree?
The relationship between the number of leaf nodes in a binary tree and the number of nodes with degree 2 is: the number of nodes with degree 2 = the number of leaf nodes -1;
So, the number of leaf nodes =Number of nodes with degree 2 1=6.
Expansion:
Binary trees are recursively defined, and their nodes are divided into left and right subtrees. Logically, binary trees have five basic forms:
Empty binary tree - as shown in (a);
A binary tree with only one root node - as shown in (b);
Only the left subtree - as shown in (c);
Only the right subtree - as shown in (d);
Complete binary tree - as shown in (e).
Note: Although binary trees have many similarities to trees, binary trees are not a special case of trees.
Type
(1) Complete binary tree - If the height of the binary tree is h, except for the h-th layer, the number of nodes in all other layers (1~h-1) reaches the maximum There are leaf nodes in the h-th layer, and the leaf nodes are arranged from left to right. This is a complete binary tree.
(2) Full binary tree - a binary tree in which every node except leaf nodes has left and right subleaves, and the leaf nodes are all at the bottom.
(3) Balanced binary tree - A balanced binary tree is also called an AVL tree (different from the AVL algorithm). It is a binary sorting tree and has the following properties: it is an empty tree or it The absolute value of the height difference between the left and right subtrees does not exceed 1, and the left and right subtrees are both balanced binary trees.
For more related knowledge, please pay attention toPHP Chinese website! !
The above is the detailed content of A certain binary tree has 5 nodes with degree 2. What is the number of leaf nodes of this binary tree?. For more information, please follow other related articles on the PHP Chinese website!