Brief introduction of tree structure

The tree structure is a hierarchical nested structure. The outer layer and the inner layer of the tree structure have similar structures, so this structure can be expressed recursively. Various tree diagrams in classical data structures are a typical tree structure: a tree can be simply represented as root, left subtree and right subtree. Both the left subtree and the right subtree have their own subtrees.

In the tree structure, the root node has no predecessor node, and every other node has only one predecessor node. The leaf node has no successor nodes, and the number of successor nodes of each other node can be one or more. In addition, the tree structure in mathematical statistics can represent hierarchical relationships. The tree structure is also used in many other aspects. It can indicate subordination and juxtaposition.

Second, unordered trees and ordered trees

Unordered tree: the order between the children of any node in the tree constitutes an irrelevant tree. Usually a tree refers to an unordered tree. Ordered tree: A tree in which the children of any node in the tree have a strict arrangement order. A binary tree is an ordered tree, because each child node in the binary tree is precisely defined as the left or right child node of the node.

Tree diagram and minimum tree diagram:

1, tree diagram

Tree diagram, also known as dendritic diagram. A tree diagram is a graphical representation of a data tree, which organizes objects in a parent-child hierarchy. Is an expression of enumeration. Tree diagram is also a kind of graph that junior high school students need to draw for learning probability problems. The tree diagram of phenotype is drawn according to population analysis, and the tree diagram of system is drawn according to a simulated hypothetical character evolution direction, that is, by computer.

2. Minimum tree diagram

The minimum tree graph is to specify a special point V in the directed weighted graph and find a directed spanning tree T, so that the root of the directed tree is V and the total weight of all edges in T is the minimum. The first algorithm of the minimum tree graph is the algorithm with O(VE) proposed by Zhu and Liu in 1965.

The method of judging whether there is a tree diagram is simple. It only needs to traverse the graph once with V as the root. Before all operations begin, we need to clear all the self-loops in the diagram. Obviously, a self-ring cannot be on any tree diagram. Only through this operation can the total complexity of the algorithm be truly guaranteed to be O(VE).