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

This article will explain in detail the example analysis of the tree of data structure for you. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have some understanding of the relevant knowledge after reading this article.

Brief introduction of data structure Tree

A brief introduction to trees

Tree is an abstract data structure, which is a collection of data, and the data in the collection form a tree structure. For example, the picture above looks like an upside-down tree with roots facing up and leaves facing down.

A tree is a hierarchical set of data composed of n (n > = 0) nodes. When nicked 0, there are no nodes in the tree, which is called an empty tree. When n > 0, there is one and only one node is called the root node (Root). If n is 1, the tree has only one root node. If n > 1, divide the other nodes into m (m > 0) disjoint data sets except the root node, each of which satisfies the structure of the tree (there is and only one root node), and the m trees are "hung" on the root node, so recursively until all nodes are "hung" to the tree. Among them, the m trees composed of the m sets are called the subtrees of the root nodes.

When understanding the structure and definition of a tree, we need to apply the idea of recursion. The following figure is an example. The node set of the tree is {A ~ Magi B ·C ~ (1) D}, nforth 8, and the root node is A. except for the root node A, the other nodes form two sets (m _ 1 and m ~ 2), the m _ 1 set is {B ~ D ~ D ~ E}, and the m ~ 2 set is {C ~ (rect) F ~ G ~ Z H}. In M1, B is the root node of M1, except B, the other nodes form two sets, set {D} and set {E}, {D} and {E} all have only one node, forming a tree with only one node, respectively. They "hang" on the root node B of M1, which is a subtree of B, M1 forms a tree, and M1 is a subtree of A. Similarly, in m2, C is the root node of m2, and the other nodes form three sets {F}, {G} and {H}.

II. Terminology of trees

To understand the data structure of trees, you must first understand some commonly used terms.

The tree consists of one node, and the node is the basic unit of the complex data structure.

1. Child node: also known as a child node, the root node of a subtree that a node contains is called a child node of that node. In the following figure, node B has two subtrees, and the root nodes of these two subtrees are D and E, so D and E are both children of B.

two。 Parent node: also known as the parent node, if a node has a child node, the node is called the parent of its child node. In the following figure, node B has two child nodes D and E, then B is the parent node of D and the parent node of E.

3. Sibling node: nodes with the same parent node are called sibling nodes to each other. D and E in the following figure are sibling nodes.

4. Cousin nodes: if the two nodes of the tree are of the same depth, but the parent nodes are different, they are cousins of each other. In the following picture, D and FMague D and GMagol D and HPerry D and I are cousins.

5. The ancestor of the node: starting from the root node, all the nodes on the path of a node are called the ancestors of that node. In the following figure, the ancestor node of node J is A _ Magi B _ D.

6. Descendants of nodes: in a subtree rooted at a node, any node is called the descendant of that node. In the following figure, the descendants of Node C are FMaga, Greco, Hreco, I-Magi, M-Magi, O.

7. The hierarchy of nodes: starting from the root, the root is layer 1, the child node of the root is layer 2, and so on. In the following figure, root node An is at layer 1 and node M is at layer 4.

8. Depth of a node: the hierarchy in which a node is located is called the depth of the node. In the following figure, the depth of root node An is 1 and the depth of node M is 4. (the depth of the cousin node is used when explaining the cousin node above. Now you can go back and have a look.)

9. The depth of the tree: also known as the height of the tree, the maximum node depth in a tree is called the depth of the tree. The depth of the tree in the following figure is 4.

There are two ways to define depth and height, one is to define the depth of the root node as 0, and the other is to define the depth of the root node as 1. In any case, the depth of the child nodes of each node with a depth of k is knew1, which is constant.

10. The degree of a node: the number of subtrees (or child nodes) that a node contains is called the degree of that node. In the following figure, the degree of root node An is 2, that of node C is 4, that of node I is 1, and that of node O is 0.

11. Degree of a tree: the largest node degree in a tree is called the degree of the tree. In the following figure, the maximum node degree is 4, then the degree of the tree is 4.

twelve。 Leaf node: also known as terminal node, the node with zero degree is called leaf node. In the following figure, the nodes F _ H ~ J _ J _ L _ M _ O are all leaf nodes.

13. Forest: a set of m (m > = 0) trees that do not intersect is called a forest. Forest is a term that extends from trees, and the trees in the forest must not intersect each other.

Third, the characteristics of trees

Through the introduction of the definition and terminology of the tree, we can basically understand the data structure of the tree. To sum up, the tree has the following characteristics.

1. If the number of nodes in the tree is n > 0, the root node is unique and there can be no multiple root nodes.

two。 A node that does not have a parent is called the root node. The root node has no parent node.

3. Each non-root node has and only one parent node. All nodes except the root node have a parent node, and there is only one parent node for the same node, so there cannot be more than one.

4. Each node has zero or more child nodes.

5. In addition to the root node, the child node can be divided into multiple disjoint subtrees. These subtrees must not intersect each other.

6. The depth of the child node of each node with a depth of k is kroom1.

IV. Classification of trees

All trees meet the above characteristics, in addition, some trees also have proprietary characteristics. Trees can be classified according to their proprietary characteristics.

1. Unordered tree: also known as a free tree, there is a node in the tree, and there is no sequential relationship between the children of the node. In the following figure, the tree on the right is an unordered tree. Take a node D from the tree. The child nodes of D are node J and node E. they are not sequentially related, so this is an unordered tree.

two。 Ordered tree: there is a sequential relationship between the children of any node in the tree. In the following figure, the tree on the left is an ordered tree, and the child node of any node CMague C from the tree is Fmai GMague H, which is sequentially related (alphabetically), so this is an ordered tree.

The order and disorder in the figure take the alphabetical order as an example. In practical application, "order" is not limited to alphabetical order, numerical order and so on. The actual order mainly refers to "non-interchangeable".

There is no sequential relationship between the nodes of the unordered tree, and the relationship between nodes can not be simulated and controlled by code, so there is basically no actual application scenario.

The use of trees as a data structure is basically the use of ordered trees, which can be divided into the following categories.

1. Binary tree: a tree with at most two subtrees per node is called a binary tree, as shown in the following figure. Binary tree is the most commonly used tree structure, which can be further subdivided (another article will be studied more carefully).

two。 Hoffman tree: also known as the optimal binary tree, is a kind of binary tree with the shortest weighted path.

3. B-tree: a self-balanced binary search tree that optimizes read and write operations, which keeps the data in order and has more than two subtrees.

This is the end of the sample analysis of the tree of data structures. I hope the above content can be helpful to you and learn more knowledge. If you think the article is good, you can share it for more people to see.

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.