In order to better understand the selection of sorting algorithm will be introduced later – heap (other articles may introduce more professional but difficult to understand, this article as concise as possible to express the key points), so I first introduce the binary tree in the data structure.
The tree
A tree is a one-to-many data structure. There are many subsets of trees, such as binary trees, binary search trees, 2-3 trees, red black trees and so on. Tree features:
1. A node with no parent is called a root, and a number has only one root.
2. Each node has 0 or more children;
3. A tree can also have subtrees, and the subtrees cannot intersect.
The treeExample:
The ones marked in red are the subtrees of the tree above:
The degree of
The number of subtrees each node has is called the degree of the node. Simply speaking, the number of children of a node is its degree. For example, in the figure above, the degree of node D is 3. Nodes with degree 0 become leaf nodes, that is, nodes with no children.
The name ‘leaf node’ is very figurative, it is a branch can grow twigs, twigs can grow leaves, but leaves do not grow branches, a leaf is the end of a branch.
Binary tree
Binary trees are a special kind of trees. The characteristics of binary trees are:
1. A tree where each node has at most 2 children (that is, no node with a degree greater than 2);
2. The left and right subtrees have a certain order (for example, ascending or descending order. In the figure below, the right child node of 8 is larger than the left child node, and so is the child node of node 2 and node 7);
Full binary tree
A full binary tree is one where all non-leaf nodes have two children, and it looks horizontal. Its characteristics are as follows:
1. All leaves are in the last layer;
2. The degree of all non-leaf nodes is 2;
Complete binary tree
Characteristics of complete binary trees:
1. All nodes in the non-last layer of the tree are full;
2. The leaves of the last layer must be concentrated to the left, that is, the nodes of the penultimate layer are not allowed to have only right children but no left nodes.
It can be seen from the above:
A full binary tree must be a complete binary tree, and not the other way around.
Complete binary tree is an efficient data structure, and heap is a data structure that makes complete binary tree easier to operate (such as add and delete) from the level of program implementation. The heap will be covered in the next article.
Thanks for reading! Welcome to pay attention! Continuously updated…