Shulou(Shulou.com)06/03 Report--

This article shows you Python binary tree example analysis, concise and easy to understand, absolutely can make your eyes shine, through the detailed introduction of this article I hope you can gain something.

1. Introduction to Binary Tree

Binary tree is a tree structure with at most two subtrees per node, which is a special tree, as shown below, which is a binary tree.

A binary tree is a data set consisting of n(n>=0) nodes. When n=0, there are no nodes in the binary tree, which is called empty binary tree. When n=1, the binary tree has only one root node. When n>1, each node of a binary tree can have at most two subtrees, which are recursively constructed into a complete binary tree.

The two subtrees of a binary tree are called the left subtree and the right subtree. In a binary tree, if the node has no subtree, the left subtree and the right subtree are empty; if the node has only one subtree, it is necessary to distinguish whether the subtree is the left subtree or the right subtree according to the left and right of the subtree; if the node has two subtrees, both the left subtree and the right subtree have.

If there is a node in the tree that has more than two subtrees, then the tree is not a binary tree, as shown in the following figure, node C has three subtrees, so this is not a binary tree.

Two, several special binary trees

As long as all nodes in the tree have no more than two subtrees (0, 1, 2), this is an ordinary binary tree. In binary tree, there are some special, in addition to meeting the structure of binary tree, but also meet some special rules, mainly as follows.

1. Complete binary tree: Suppose that the depth of a binary tree is d(d>1), except for the d layer, the number of nodes in other layers has reached the maximum, and all nodes in the d layer are closely arranged continuously from left to right.

The leaf nodes of a complete binary tree can only appear at the lowest and sub-lower levels, and the leaf nodes at the lowest level are closely arranged to the left, and if there are leaf nodes at the sub-lower level, the leaf nodes are closely arranged to the right.

As shown in the figure below, the depth of the tree is 4, except for the fourth layer, the number of nodes reaches the maximum ("full"), and the nodes of the fourth layer are closely arranged to the left (no empty space in the middle), so this is a complete binary tree.

As shown in the figure below, the depth of the tree is also 4, except for the fourth layer, the number of nodes has also reached the maximum, but the nodes of the fourth layer are not arranged on the left side (node E has no child nodes, empty two positions), so this is not a complete binary tree, just an ordinary binary tree.

2. Full binary tree: A complete binary tree with all leaf nodes at the bottom is called a full binary tree. A full binary tree is a special case of a complete binary tree, which satisfies not only the characteristics of a complete binary tree, but also that all leaf nodes are at the lowest level. A full binary tree is a tree with the most leaves in a binary tree of the same depth.

As shown below, this is first a complete binary tree, and second, all leaf nodes are at the bottom, so this is a full binary tree. In fact, full binary tree can also be defined as such, binary tree has all layers of nodes, the number of nodes has reached the maximum value, then this is a full binary tree.

3. A balanced binary tree (AVL tree) is called a balanced binary tree if the height difference between two subtrees of all nodes of the binary tree is not greater than 1.

As in the full binary tree above, the height difference between the two subtrees of any node is 0(the height is equal, and the height difference is not greater than 1), so this is a balanced binary tree.

As shown in the binary tree in the figure below, for the root node A, the left subtree is a subtree rooted at node B with a height of 4, the right subtree is a subtree rooted at node C with a height of 2, and the height difference between the left subtree and the right subtree of A is 2(the height difference is greater than 1), so this is not a balanced binary tree.

AVL tree is named after its inventor G. M. Adelson-Velsky and E. M. Landis is an abbreviation for both surnames. The height difference between the two subtrees of any node in the AVL tree is not greater than 1, and it is judged whether it is balanced by height, so it is also called a height balanced tree.

4. Binary Search Tree (Binary Search Tree): Also known as Binary Search Tree, Ordered Binary Tree.

The binary tree needs to have the following properties:

4.1 If the left subtree of a binary tree is not empty, then the values of all nodes in the left subtree are less than the values of its root node.

4.2 If the right subtree of a binary tree is not empty, then the values of all nodes in the right subtree are greater than the values of its root node.

4.3 If you look at it independently, the left subtree and the right subtree are also sorted binary trees, respectively, using recursive ideas until the leaf nodes of the tree.

As shown below, in the left subtree of root node 8, the values of all nodes are less than the root node, and in the right subtree, the values of all nodes are greater than the root node, and the left subtree and the right subtree are sorted binary trees, so this is a sorted binary tree.

5. Oblique tree: A binary tree in which all nodes except leaf nodes have only left subtrees is called a left oblique tree. A binary tree in which all nodes except leaf nodes have only right subtrees is called a right oblique tree. They are collectively referred to as oblique trees, to determine whether a binary tree is an oblique tree, mainly to see the structure of the tree, there is no requirement for the value of the node.

As shown below, in the tree on the left, except for leaf node D, all nodes have only left subtrees, which is a left oblique tree. Similarly, the tree on the right is a right oblique tree.

3. Characteristics and properties of binary tree

Through the introduction of binary trees and understanding of several special binary trees, we can see that binary trees have the following characteristics:

1. Each node has at most two subtrees, so the degree of the node in the binary tree is not greater than 2, and the degree of the binary tree is not greater than 2.

2. The order of left and right subtrees cannot be reversed.

3. Even if a node has only one subtree, it is distinguished whether it is a left subtree or a right subtree according to left and right.

In addition, binary tree also has the following properties:

1. At the ith level of the binary tree, there are at most 2^(i-1) nodes (i>0).

Here is the case at most, each layer of nodes of the full binary tree is "full", so you can use the full binary tree in the following figure to verify that the number of nodes in the first layer is 2^(1-1)=1,... The maximum number of nodes in level 4 is 2^(4-1)=8.

2. A binary tree of depth i has at most 2^i - 1 nodes (k>0).

This is also the case of at most, so it is also verified with a full binary tree. When the depth is 4, the maximum number of nodes in the binary tree is 2^4 - 1=16-1=15.

3. For any binary tree, if the number of leaf nodes is M and the total number of nodes with degree 2 is N, then M=N+1.

For the sake of generality, the tree in the figure below is an ordinary binary tree with 6 leaf nodes F,H,I,J,K,L and 5 degree 2 nodes A,B,C,D,G.

4. A full binary tree with n nodes must have a depth of log2(n+1). This property is the inverse of point 2 above.

5. For a complete binary tree, if numbered from top to bottom and from left to right, then the node numbered i must have a left child numbered 2i (except leaf nodes), a right child numbered 2i +1 (except leaf nodes), and a parent numbered i/2(divisible)(except root nodes).

As shown below, this is a complete binary tree, has been numbered according to the rules, you can arbitrarily take a node to verify, are in line with this nature.

The above content is an example analysis of Python binary tree. Have you learned knowledge or skills? If you want to learn more skills or enrich your knowledge reserves, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.