Algorithm Clearance Village Level 6 – Bronze Challenge Tree

Hello everyone, my name is Su Lin. Today I’m going to talk about trees.

Outline

    • tree concept
      • Binary tree
        • full binary tree
        • complete binary tree
    • tree nature
    • Definition and storage of trees
    • tree traversal
    • Construct a binary tree from sequences
      • Front and middle sequence traversal
      • Middle and back sequence traversal

The concept of tree

Tree is a very important data structure in our computers. At the same time, using this data structure, trees can describe many things in real life, such as family trees, organizational structures of units, etc.
A tree is a collection of hierarchical relationships composed of n (n>=1) finite nodes. It’s called a “tree” because it looks like an upside-down tree, which means it has the roots facing up and the leaves facing down.

Better understanding:

Such as the rank relationship in the enterprise:

Such as the table of contents of a book:

The picture below is a standard tree structure:


Trees have the following characteristics:

1. Each node has zero or more child nodes
2. A node without a parent node is the root node.
3. Each non-root node has only one parent node
4. Each node and its descendant nodes can be regarded as a tree as a whole, which is called a subtree of the parent node of the current node.

Referring to the above structure, you can easily understand the following concepts of trees:

1. Degree of a node: The number of child nodes that a node contains is called the degree of the node
2. Degree of tree: In a tree, the degree of the largest node is called the degree of the tree. Pay attention to the difference from the degree of the node.
3. Leaf node or terminal node: A node with degree 0 is called a leaf node
4. Non-terminal nodes or branch nodes: nodes with a degree other than 0
5. Parent node or parent node: If a node contains child nodes, this node is called the parent node of its child node.
6. Child node or child node: The root node of the subtree contained by a node is called the child node of the node.
7. Sibling nodes: Nodes with the same parent node are called sibling nodes.
8. Ancestors of a node: all nodes on the branches from the root to the node
9. Descendants: Any node in the subtree rooted at a node is called a descendant of that node.
10. Forest: A set of m (m>=0) disjoint trees is called a forest.
11. Unordered tree: There is no sequential relationship between the child nodes of any node in the tree. This kind of tree is called an unordered tree, also called a free tree.
12. Ordered tree: There is a sequential relationship between the child nodes of any node in the tree. This kind of tree is called an ordered tree.
13. Binary tree: A tree with each node containing at most two subtrees is called a binary tree.

Binary tree

A binary tree is a special form of tree. Binary, as the name suggests, each node of this tree has at most 2 child nodes. Note that there are at most 2, there may be only 1, or there may be no child nodes.

The structure of a binary tree is as shown in the figure:

There are two child nodes of a binary tree node, one is called the left child and the other is called the right child. The order of these two child nodes is fixed, just like a person’s left hand is the left hand, and the right hand is the right hand, and cannot be reversed or confused.

In addition, there are two special forms of binary trees, one is called a full binary tree and the other is called a complete binary tree.

Full binary tree

If all non-leaf nodes of a binary tree have left and right children, and all leaf nodes are at the same level, then the tree is a full binary tree.

To put it simply, every branch of a full binary tree is full.

Complete binary tree

For a binary tree with n nodes, numbered in hierarchical order, all nodes are numbered from 1 to n. If all the nodes in this tree have the same position as the nodes numbered from 1 to n in a full binary tree of the same depth, then the binary tree is a complete binary tree.

As shown in the picture:

In the figure above, the 12 nodes of the binary tree numbered from 1 to 12 exactly correspond to the positions of the nodes of the previous full binary tree numbered from 1 to 12. Therefore this tree is a complete binary tree.

The conditions for a complete binary tree are not as demanding as a full binary tree: a full binary tree requires that all branches are full;
A complete binary tree only needs to ensure that all nodes before the last node are complete.

Properties of trees

Property 1: There are at most 2^(i-1) nodes (i>0) on the i-th level of the Eryou tree
Property 2: The Eryou tree with depth k has at most 2^k – 1 nodes (k>0)
Property 3: For any binary tree, if the number of leaf nodes is N0 and the total number of nodes with degree 2 is N2, then NO=N2 + 1:
Property 4: The depth of a complete binary tree with n nodes must be log2(n + 1)
Property 5: For a complete binary tree, if it is numbered from top to bottom and from left to right, then the node numbered i will have its left child numbered 2i.
The number of its right child must be 2i + 1; the number of its parents must be i/2 (except when i= 1 is the root). Full binary trees and complete binary trees are often confused problems, and we need to look at them separately. A full binary tree means that if a binary tree only has nodes with degree 0 and nodes with degree 2, and the nodes with degree 0 are on the same level, then the binary tree is a full binary tree.

This Ermata tree is a full Ermata tree, which can also be said to be a Ermata tree with a depth of k=4 and 2^k-1=15 nodes. The definition of a complete binary tree is as follows: In a complete binary tree, except for the bottom node, which may not be filled, the number of nodes in each layer reaches the maximum and the nodes in the bottom layer are concentrated at the leftmost position of the layer. This definition The most bizarre thing is that most people probably still don’t understand what a complete binary tree is after reading this. Just look at this picture:

The first n-1 layers of the first two trees are full, and all the nodes of the last layer are concentrated in the left area, and there can be no gaps between nodes. Why not the last one? Because one node is missing a left child node.

Definition and storage method of tree

Definition of binary tree: A node can point to up to two child nodes on the left and right, so each node of the binary tree contains 3 parts.

  • data variable to store data
  • left pointer pointing to the left child
  • right pointer pointing to the right child
public class Node{<!-- -->
int value;
Node left;
Node right;
}

chain storage structure

Array storage


When using array storage, the nodes of the binary tree will be placed in the corresponding positions in the array in hierarchical order. If the left child or right child of a node is vacant, the corresponding position in the array is also vacant.

For a sparse binary tree, using array representation is very wasteful of space.

Tree traversal

There are 4 types of binary tree traversal:

  1. Preorder traversal
  2. inorder traversal
  3. Postorder traversal
  4. level-order traversal

From a more macro perspective, binary tree traversal boils down to two major categories:

  1. Depth-first traversal (pre-order traversal, in-order traversal, post-order traversal)

  2. Breadth-first traversal (level-order traversal)

These two traversal methods are not just binary trees, N-ary trees also have these two methods, and graph structures also have them, but we are more accustomed to calling them breadth first and depth first, which are essentially the same thing. There are three types of depth priority: front, middle, and last. Some students can’t tell the difference between these three orders. The problem is that they don’t know who the front, middle, and back are relative to. Remember one thing: the front refers to the order of the middle parent nodes in the traversal. As long as everyone remembers that the front, middle and back seats refer to the position of the middle node.

Preorder traversal of a binary tree, the output order is the root node, left subtree, and right subtree.

In-order traversal of a binary tree, the output order is the left subtree, root node, and right subtree.


Post-order traversal of a binary tree, the output order is left subtree, right subtree, and root node.


A large number of subsequent algorithms are related to these four traversal methods. Some questions can be implemented using hierarchical traversal or one or even two depth-first methods depending on the processing angle.

Construct a binary tree through sequences

We have introduced the basic process of front, middle and back order traversal before. Now let’s look at how to restore the original binary tree through the given sequence to see three sequences:

(1) Preface: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
(2) Middle order: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
(3) Sequence: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

First and middle sequence traversal

Let’s first look at how to restore a binary tree through the front and middle sequences

(1) Preface: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
(2) Middle order: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12

We know that the first accessed in the preorder is the root node, so the root node is 1. The characteristic of in-order traversal is that the elements of the left subtree of the root node are all on the left side of the root node, and the elements of the right subtree are all on the right side of the root node. We can divide the in-order traversal sequence into the following structure:

In-order sequence division:
[3 4 8 6 7 5 2] 1 [10 9 11 15 13 14 12]
The preorder sequence is divided into:
1 [2 3 4 5 6 8 7 ] [9 1 11 12 13 15 14]

The first brackets in the above sequence are all elements of the left subtree, and the second brackets must be elements of the right subtree. So how do we know where the two brackets are separated? Refer to the two in the sequence. Array divided. We see that the elements before 7 in the preorder are in the first array in the midorder, and all the elements after 9 are in the second array, so we divide between 7 and 9. From this, draw a diagram to represent the structure of the tree known at this time:

Let’s first look at the first array of the two sequences:
Preface: 2 3 4 5 6 8 7
Middle order: 3 4 8 6 7 5 2
At this time, we can use the above conclusion to divide: the root node is 2, and then according to the position of 2 in the mid-order, it can be divided into:

Preamble: 2 [3 4 5 6 8 7 ]
Middle order: [3 4 8 6 7 5 ]2

![Insert image description here]

Continue dividing 3 4 5 6 8 7:

Preamble: 3 [4 5 6 8 7]
Mid-order: 3 [4 8 6 7 5]

The structure at this time is:

Continue dividing 4 5 6 8 7:

Preamble: 4 [5 6 8 7]
Mid-order: 4 [8 6 7 5]


Continue dividing 5 6 8 7:
Preface: 5 [6 8 7]
Middle sequence: [8 6 7] 5

Continue dividing 6 8 7:
Preface: 6 [8 7]
Mid-order: [8]6 [7]


The same goes for the right side. Let’s try it yourself…
Give the final version directly:

Mid-post sequence traversal

Let’s first look at how to restore a binary tree through the front and middle sequences

(2) Middle order: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
(3) Sequence: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

  • first round

We know that the last visited node in the postorder is the root node, so the root node is 1.

The characteristic of in-order traversal is that the elements of the left subtree of the root node are all on the left side of the root node, and the elements of the right subtree are all on the right side of the root node. We can divide the in-order traversal sequence into the following structure:

Mid-order division
[3 4 8 6 7 5 2] 1 [10 9 11 15 13 14 12]
Post-order division
[8 7 6 5 4 3 2] [10 15 14 13 12 11 9] 1

In the above postorder sequence, the first brackets are all elements of the left subtree, and the second brackets must be all elements of the right subtree.

So how do we know where the two brackets are separated? They are divided by referring to the two arrays in the middle order. We see that the elements before 7 in the preorder are in the first array in the midorder, and all the elements after 9 are in the second array, so we divide between 7 and 9.

  • second round

Mid-order: [10 9 11 15 13 14 12]
Sequence: [10 15 14 13 12 11 9]

Divide at this time:

[10] 9 [11 15 13 14 12]
[10 15 14 13 12 11 ] 9

The structure of the tree at this time:

  • third round

Mid-order: 11 [15 13 14 12]
Sequence: [10 15 14 13 12 ] 11

Divide at this time:

[] 11 [ 15 13 14 12]
[15 14 13 12 ] 11

The structure at this time is:

  • third round

Mid-order: [15 13 14 12]
Sequence: [15 14 13 12]

Divide at this time:

[15 13 14 ] 12 []
[15 14 13 ] 12

Structure at this time:

  • fourth round

Middle sequence: [15 13 14]
Sequence: [15 14 13]

Divide at this time:

[15] 13 [14]
[15 14] 13


The same goes for the left side, so I won’t show it here. You can try it yourself…
Directly display the full version:

That’s it for this issue, see you next time!