Binary tree formulas you must understand

1. Properties of general binary trees

Properties 1. On the i level of a non-empty binary tree, there are at most 2^i nodes .

Property 2. In a binary tree with height K, there are at most 2^(k 1)-1 nodes.

Property 3. For any non-empty binary tree, if the number of leaf nodes is n0 and the number of nodes with degree 2 is n2, then n0=n2 1.

2, Complete Binary Tree

Definition: If in a binary tree, only the degrees of the nodes at the bottom two levels are less than 2, the degrees of the nodes at all other levels are equal to 2, and the nodes of the bottom layer are concentrated in the leftmost positions of the layer, then this binary tree is called a complete binary tree.

Property 1. The height k of a complete binary tree with n nodes is [log^2n].

Property 2. For a complete binary tree with n nodes, if all the nodes in the binary tree are sequenced from top (root node) to bottom (leaf node) and from left to right, Numbering starts from 0 to n-1, then for any node whose subscript is i, there are:

(1) If i=0, it is the root node and it has no parent node; If i>0, then the subscript of its parent node is (i-1)/2.

(2) If 2i 1<=n-1, then the subscript of the left child node of the node with subscript i is 2i 1; otherwise, the node with subscript i has no left child Node.

(3) If 2i 2<=n-1, then the subscript of the right child node of the node with subscript i is 2i 2; otherwise, the node with subscript i has no right child Node.

3, Full Binary Tree

Definition: If any node of a binary tree is either a leaf, or has two non-empty subtrees, then this binary tree is called Full binary tree.

Property, in a full binary tree, the number of leaf nodes is 1 more than the number of branch nodes.

4, Expanded Binary Tree

Definition: An expanded binary tree is an expansion of an existing binary tree. After the expansion, the nodes of the original binary tree become branches with degree 2. Node. That is to say, if the degree of the original node is 2, it will remain unchanged; if the degree is 1, then one branch will be added; if the degree is 0, then two branches will be added.

Property 1. In the extended binary tree, the number of external nodes is 1 more than the number of internal nodes.

Property 2. For any extended binary tree, the following relationship is satisfied between the external path length E and the internal path length I: E=I 2n, where n is the number of internal nodes.

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

The above is the detailed content of Binary tree formulas you must understand. For more information, please follow other related articles on the PHP Chinese website!