Tree structure

Overview

Tree structure refers to a data structure with a "one-to-many" tree relationship between data elements, and is an important type of non-linear data structure.

In the tree structure, the root node of the tree has no predecessor node, and every other node has and only one predecessor node. The leaf node has no follow-up nodes, and the number of follow-up nodes for each of the remaining nodes 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 ways. It can express subordination and parallel relations.

Website tree structure

A lot of channels and directories are formed under the root directory, and each channel directory contains a webpage belonging to this channel.

Basic properties

1. The tree is a finite set of n (n>=0) nodes.

2, in any empty tree.

Related terms

1. Node: indicates the data element in the tree, which is composed of the relationship between the data item and the data element. In the figure, there are 10 nodes in total. 2. Degree of node (DegreeofNode): the number of subtrees owned by the node. In the figure, the degree of node A is 3. 3. Degree of tree (DegreeofTree): the maximum degree of each node in the tree value. In Figure 5.1, the tree has a degree of 3. 4. Leaf Node: A node with a degree of 0 is also called a terminal node. In Figure 5.1, nodes E, F, G, H, I, and J are all leaf nodes. 5. Branch Node (BranchNode): A node whose degree is not 0, also called a non-terminal node or an internal node. In Figure 5.1, nodes A, B, C, and D are branch nodes. 6. Child: The root of the node subtree. In the figure, nodes B, C, and D are the children of node A. 7. Parent: The upper node of the node is called the parent of the node. In the figure, the parents of nodes B, C, and D are node A. 8. Ancestor: From the root to all nodes on the branch of the node. In the figure, the ancestors of node E are A and B. 9. Descendant: any node in the subtree rooted at a certain node. In the figure, all nodes except A are descendants of A. 10. Brother: Children of the same parent. In Figure 5.1, nodes B, C, and D are brothers to each other. 11. Level of node (Level of Node): The number of branches on the path taken from the root node to a node in the tree is called the level of the node. The level of the root node is defined as 1, and the level of the remaining nodes is equal to the level of its parent nodes plus 1.

12. Sibling: Nodes with different parents in the same layer. In the picture, G and H are cousins ​​of each other. 13. Depth of the tree (DepthofTree): the maximum number of layers of nodes in the tree. In Figure 5.1, the depth of the tree is 3.

14. Unordered Tree: The order between the child nodes of any node in the tree constitutes an irrelevant tree. Usually a tree refers to an unordered tree.

15. Ordered tree (OrderedTree): a tree in which each child node of any node in the tree has a strict order. The binary tree is an ordered tree, because each child node in the binary tree is exactly defined as the left child node or the right child node of the node.

16. Forest: A collection of m (m≥0) trees. The concept of trees and forests in nature is very different, but the concept of trees and forests in the data structure is very different. It can be seen from the definition that a tree is composed of a root node and m subtrees. If the root node of the tree is deleted, the tree becomes a forest containing m trees. Of course, by definition, a tree can also be called a forest.