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

This article will explain in detail the example analysis of binary tree in web development. The editor thinks it is very practical, so I share it with you for reference. I hope you can get something after reading this article.

0. Preface

So far, we have talked about four data structures: sequential tables, linked lists, stacks, and queues. One thing they have in common is that they are all linear tables, in other words, they are all linear structures, like a rope.

Four linear data structures

In the article [Linear Table], the definition of linear table has been introduced, that is, a finite sequence composed of several elements according to linear structure (one-to-one relationship).

The key word is an one-to-one relationship.

Obviously, in the complex real society, this one-to-one relationship can not better meet our needs.

For example, the relationship between parents and multiple children, one father / mother corresponds to multiple children, this is obviously not an one-to-one relationship, but an one-to-many relationship. So how do we describe this one-to-many relationship at this time?

Use a data structure with an one-to-many relationship, of course! Is there such a data structure? Yes! This paper introduces this data structure-tree and its special form of binary tree.

1. Know the tree 1.0. What is a tree?

When it comes to Tree, the first image that comes to mind should be something like this:

The picture is from the Internet.

The reason why we use the term "tree" to name a data structure with a "one-to-many relationship" is because the tree happens to be a very vivid interpretation of this feature. Let's analyze it.

Look at the tree in the picture above (above the ground). It has a root that forks upward from the root, the main trunk forks into many trunks, the secondary trunk continues to fork into many twigs, and there are many leaves on the twigs.

The main trunk to the secondary trunk, the secondary trunk to the twigs, and the twigs to the leaves are all one-to-many. We use circles to represent the trunks and leaves, and we abstract the trees in nature upside down to get the following picture (for convenience, our data are all character types):

A tree

As you can see, the real tree fits perfectly with the data structure we need, so we call this data structure Tree.

1.1. Nouns and concepts

We follow the clues to find out the relevant nouns of trees.

Subtree: a tree is a finite set, and a subtree is a subset of that set. Like nesting dolls, there are sub-trees under a tree.

For example, the subtrees of tree T1 are T2, T3 and T4, and the subtrees of T2 are T5 and T6. There are still many subtrees in the picture above that are not marked.

Node (Node): a node includes a data element and several branches pointing to its subtree.

For example, in tree T1, node An includes a data element An and three branches that point to its subtree. There are 17 nodes in the picture above.

Root: it is common sense that a tree has only one root. In the data structure, the "root" is the root node.

For example, node An is the root node of tree T1, and node C is the child node of tree T1 and the root node of tree T3.

Degree (Degree): the number of subtrees owned by a node.

For example, the degrees of node A, node G and node H are 3, 3 and 1.

Leaf / terminal node: a node with a degree of 0 is called a leaf node, which is very vivid.

For example, for tree T1, nodes F, I, K, L, M, N, O, P, Q are all leaves.

Branch node / non-terminal node: the node opposite to the leaf node, that is, the node whose degree is not zero.

Internal node: as the name implies, a node within a tree, that is, a node that is not a root node and a leaf node.

The concepts of children (Child), parents (Parent), brothers (Sibling), cousins, ancestors and descendants are the same in genealogy.

For example, for node B, node An is its parent node, node E and F are its child node, node C and D are its brother node, and node K is its descendant node.

Level: starting from the root node, the root is the first time, and the child of the root is the second layer, descending in turn.

For example, the level of node K in tree T1 is 4. 5.

Depth / height: refers to the maximum level of the tree.

For example, the depth of tree T1 is 4. 5.

Ordered tree: if the subtrees of a node are ordered from left to right and cannot be reversed, it is an ordered tree, otherwise it is an unordered tree. For the children of orderly trees, the leftmost child is called the first child, and the rightmost child is called the last child.

For example, if tree T1 is an ordered tree, the first child of its root node is node B and the last child is node D.

1.2. The Recursive concept of Tree

We have already introduced the outline of the tree and the concepts of related nouns, and in order to answer the question of what a tree is, we also need to introduce three common tree structures.

[empty tree]: an empty tree, that is, a tree without nodes.

Empty tree

[tree with only root nodes]: there is only one root node and no other nodes.

A tree with only root nodes

[ordinary tree]

Common tree

Now we can answer what a tree is:

A Tree is a finite set of N (N > = 0) nodes.

When N = 0, the tree is empty.

When N = 1, the tree has only one root node.

When N > 1, except for one root node, the other nodes of the tree can be divided into several disjoint finite sets, which are called subtrees.

A non-empty tree has one and only one root node.

The one-to-many relationship of the tree exists between the parent node and the child node.

In a tree, because of the concept of tree and subtree, the subtree of the tree is still a tree, and the subtree of the subtree is still a tree.

For example: the children of human beings are still human, and the children of human children are still human.

Because of the concept of parents, children and grandchildren, the child node of the root node can be the root node of its subtree.

For example, a person is a father to his child and a son to his parents.

This concept is the concept of recursion.

That is, for a "thing", its "child" is no different from itself. What it does, its "child" will also do and have to do. All the way down, the same is true of "grandchildren", "great-grandchildren" and "great-grandchildren".

To illustrate the concept of recursion, we recursively decompose the tree in the above image into subtrees, and each area in the following image is a tree (or subtree):

Recursive solution tree

In the end, what we get is either a leaf node or a tree with only root nodes. For example, nodes F, K, L.

In the process of decomposition, we can also find that for each node, we can regard it as the root node of a tree (subtree). For example, nodes E and I are the root nodes of a subtree. This is not contradictory to the fact that the tree has only one root node.

This is like saying that Xiaoming can only have one biological father, but it does not affect him to become the father of others.

The whole process is like finding descendants from ancestors in genealogy. So if you don't know anything about the concept of trees, you can find a genealogy to look through.

At this point, we can say that the definition of a tree is a recursive definition, a tree is composed of a root node and its subtrees, and a subtree is also composed of a root node and its subtrees. That is, the definition of tree is also used in the definition of tree.

1.3. Comparison between tree and linear table

Compare

Look at the picture to see what is the one-to-one relationship (between the precursor node and the successor node) and what is the one-to-many relationship (between the parent node and the child node).

two。 Recognize binary tree 2.0. What is a binary tree?

What is a binary tree? First of all, it has to be a tree, and secondly, it has to be binary.

I already have a preliminary understanding of the tree, and there is no limit to the number of children in its nodes, that is, you can have as many children as you want, and you can divide as many forks as you want.

On the other hand, the binary tree limits the number of children, that is, each node can only have two children (left and right children). For example, it is a "second child tree".

Binary tree

The left child of node An is node B and the right child is node C.

A binary tree is an ordered tree in which each node has at most two subtrees (that is, the maximum degree of each node is 2).

2.1. Several forms of binary tree

1. Empty binary tree

2. Binary tree with only root nodes

3. Binary tree with empty left subtree

4. Binary tree with empty right subtree

5. A binary tree in which the left and right subtrees are not empty

2.2. Full binary tree and complete binary tree

The characteristic of full binary tree is "full", that is, the number of nodes in each layer is the maximum number of nodes.

Full binary tree

The third level of T2 did not reach the maximum number of nodes, missing 1; the fourth level of T3 did not reach the maximum number of nodes, missing 7.

A complete binary tree is relative to a full binary tree, as shown in the following figure:

The red part is numbered.

A binary tree is an ordered tree, numbering a full binary tree and a complete binary tree in the order of "top-down, left-to-right", as shown in the figure above.

The number of all nodes in a complete binary tree must be exactly the same as the same number of nodes in the full binary tree.

In other words, the nodes of a complete binary tree cannot be interrupted in the order of "top-down, left-to-right". Node C of T3 has no left child and is obviously interrupted in that order.

3. Traversal of binary tree 3.0. How to traverse?

In the online table, our traversal is very simple and rough, find the linear header, use the loop directly to the linear footer, that is, complete the traversal. In the tree, we can no longer do such a simple and rude thing, because the tree is an one-to-many relationship, so it is impossible to traverse from beginning to end.

The essence of traversal is to print out the order of linear elements. (traversing is not just a matter of printing, for convenience, our traversal is a printing element)

The contradiction of traversing the tree is that our tree is not linear. In order to solve this contradiction, can we agree on a certain order in which the elements of the tree are arranged linearly, and then traversing is a simple and rude thing from beginning to end? The answer is yes.

We know that a tree is a recursive definition, and a binary tree is a recursive combination of root nodes, left subtrees and right subtrees. So what we need to agree on is which of these three parts comes first and who comes later.

According to the agreement that people write first, left then right, we also agree on the order of left subtree followed by right subtree (of course, you can first right and then left), so that there are only three positions for the root node.

Root node > > left subtree > > right subtree, which is called preorder (root) traversal

Left subtree > root node > right subtree, which is called middle order (root) traversal

Left subtree > right subtree > root node, which is called post-order (root) traversal.

After the agreement is made, you just need to come recursively in order, just like looking for a genealogy.

Let's take traversing the binary tree in the following figure as an example:

For convenience, we draw the null and color all the subtrees.

3.1. Preorder traversal

The recursive description of preorder traversal is as follows:

If the binary tree is empty, the operation is empty; otherwise:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Access to the root node

Preorder traversing the left subtree

Traverse the right subtree first

You may ask, why is it only the step of visiting the root node? What about the node between the left child and the right child? As mentioned earlier, for each node, we can think of it as the root node of a tree (subtree). Just like your son will be someone else's father. So as long as we recursively visit the root node and change each node to a "root node" recursively, we can complete the traversal.

So instead of traversing the nodes, we are traversing the "root nodes". We are just recursively finding and outputting the "all root nodes". (because each node can be regarded as a root node)

So the key point of traversal is to transform all nodes into root nodes, and because each tree has one and only one root node, we have to recursively decompose the subtree (first the left subtree and then the right subtree) until it is decomposed to NULL.

The process is as follows:

The order of preorder traversal is: A B D E G C F

If you feel that the text description is not intuitive, you can find a dynamic diagram of the binary tree traversal process in my previous articles [1].

3.2. Mid-order traversal

The recursive description of mid-order traversal is as follows:

If the binary tree is empty, the operation is empty; otherwise:

Traversing left subtree in middle order

Access to the root node

Traverse the right subtree in the middle order

The process is as follows:

The order of traversal in the middle order is: D B G E A C F

3.3. Post-order traversal

The recursive description of post-order traversal is as follows:

If the binary tree is empty, the operation is empty; otherwise:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Traversing the left subtree in post-order

Traversing the right subtree in post-order

Access to the root node

The process is no longer described, and the sequence of traversal is: D G E B F C A

This is the end of this article on "sample analysis of binary trees in web development". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please 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.