What is the use of binary trees?

Binary trees can be used to implement binary search trees and binary heaps. In computer science, a binary tree is a tree structure with at most two subtrees per node. Usually the subtree is called the "left subtree" and "right subtree", which can be divided into: 1. Complete binary tree; 2. Full binary tree; 3. Balanced binary tree according to different uses.

The role of binary trees

Binary trees are often used to implement binary search trees and binary heaps .

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".

According to different uses, it can be divided into:

1. Complete binary tree - if the height 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. There are leaf nodes in layer h, 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 its The absolute value of the height difference between the left and right subtrees does not exceed 1, and both left and right subtrees are balanced binary trees.

Extended information

A binary tree with depth h has at most one node (h>=1) and at least h nodes. For any binary tree, if the number of leaf nodes is N0 and the total number of nodes with degree 2 is N2, then N0=N2 1.

If each node of a complete binary tree with N nodes is stored in a sequential manner, the following relationship between the nodes is: If I is the node number, then if I>1, then its parent node The number is I/2. If 2*IN, there is no left child. If 2*I 1

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