Tree
Tree is a typical nonlinear data structure, It can be well applied to data collections that describe branching and hierarchical characteristics. It is a limited collection T composed of one or more nodes.A tree has at least one node.
degree of tree, the number of subtrees of a node is the node The “degree” of a point, the number of nodes directly connected to this node below this node is the degree of this node. The degree of a number is equal to the maximum degree of each node in this tree.
The level of the tree, the root node level is 1, Add 1 in turn from the bottom.
Tree traversal, pre-order traversal (left and right root), back Sequence traversal (left and right root), level traversal.
Binary Tree
A binary tree is a finite set of nodes. The set is either empty or consists of a root node and its two disjoint left and right nodes. Consists of fork trees. Each node can have no more than two child nodes.
full binary tree: except for the last level Except for no nodes, all nodes on each layer have two sub-node binary trees.
Complete Binary Tree< /strong>: Only the lowest two-level node degree can be less than 2, and the lowest-level nodes are concentrated in the leftmost position of the binary tree.
Binary tree traversal : Pre-order traversal (left and right root), middle-order traversal (left root and right), post-order traversal (left and right root).
Huffman tree
< p>
The path length of the tree is from the root to the tree The sum of the path length of each node, in the binary tree with the same number of nodes, the path length of the complete binary tree is the shortest.
Power. In some applications, a meaningful real number is assigned to the node in the tree. This number is called weight.
Weighted path length, end The product of the length of the path from a point to the root of the tree and the weight of the node is called the weighted path length of the node.
In all binary trees composed of n leaf nodes with the same weight, with The binary tree with the smallest weight path length is called the optimal binary tree, also called the Huffman tree. Method of constructing Huffman tree< /strong>: Each time, two binary trees with the smallest weight value are selected to merge, using the greedy method.
I always didn’t know these concepts before. Write it again, it will be clearer in my heart, and I hope it will help you too.