Algorithm Clearance Village Sixth Level – How to use inorder and postorder to restore a binary tree

1 Tree basics

1.1 Definition of tree

Tree (Tree): represents a hierarchical relationship, for

(

≥

)

n (n≥0)

A finite set of n (n≥0) nodes, when n=0, is called empty tree, for any non-empty tree (n >0), which has the following properties:

? There is a root node in the tree, denoted by r
? The remaining nodes can be divided into m(m>0) finite sets of disjoint

T

1

,

T

2

,

.

.

.

,

T

m

\bold{T_1,T_2, …,T_m}

T1?,T2?,…,Tm? , where each set is itself a tree, called the subtree(Subtree) of the original tree. Subtrees are disjoint; except for the root node, each node has one and only one parent node; a tree with N nodes has N-1 side.

Some basic terms for trees:

Degree of a node (Degree): Number of subtrees of a node

Degree of the tree: the largest degree of all nodes in the tree

Leaf: a node with degree 0

Parent: A node with a subtree is the parent node of the root node of its subtree

Child: If node A is the parent node of node B, then node B is called the child node of node A; child nodes are also called child nodes.

Sibling: Nodes with the same parent node are sibling nodes of each other.

Path and path length: from node
no

1

n_1

n1?to

no

x

n_x

The path of nx? is a sequence of nodes

no

,

no

2

,

.

.

.

,

no

x

n,n_2 ,… , n_x

n,n2?,…,nx? ,

no

i

n_i

ni? yes

no

i

+

1

n_{i + 1}

The parent node of ni + 1?. The number of edges contained in the path is the length of the path.

Ancestor: All nodes along the path from the root of the tree to a certain node are the ancestor nodes of this node.

Descendant: All nodes in the subtree of a certain node are descendants of this node.

Node level (Level): It is stipulated that the root node is at level 1, and the level of any other node is the level of its parent node plus 1.

Tree Depth: The maximum level of all nodes in the tree is the depth of the tree.

Forest: A collection of m(m > 0) disjoint trees is called a forest.

Unordered tree: There is no order relationship between the child nodes of any node in the tree. This kind of tree is called unordered tree or free tree.

Ordered tree: There is an order relationship between any nodes in the tree, and this kind of tree is called an ordered tree;

Binary tree: A tree with at most two subtrees per node is called a binary tree

1.2 Properties of trees

The maximum number of nodes in layer i of a binary tree is:

2

i

?

1

,

i

≥

1

2^{i-1},i≥1

2i?1,i≥1
A binary tree with a depth of k has a maximum total number of nodes:

2

k

?

1

,

k

≥

1

2^k-1,k≥1

2k?1,k≥1
For any non-empty binary tree

T

T

T , if

no

0

n_0

n0? Indicates the number of leaf nodes,

no

2

n_2

n2? is the number of non-leaf nodes with a degree of 2, then the two satisfy the relationship

no

0

=

no

2

+

1

n_0=n_2 + 1

n0?=n2? + 1
The depth of a complete binary tree with n nodes must be

l

o

g

2

(

no

+

1

)

log_2(n + 1)

log2?(n + 1)
For a complete binary tree, if it is numbered from top to bottom and from left to right, then the node numbered i , its left child must be numbered 2i, and its right child must be numbered Must be 2i+1; the number of its parent must be

i

2

\frac{i}{2}

2i? (except when i=1 is the root)

Important operations on binary trees: mainly traversal.

Full binary tree: If a binary tree only has nodes with degree 0 and nodes with degree 2, and the degree is 0 code> nodes are on the same level, then this binary tree is a full binary tree.

Complete binary tree: In a complete binary tree, except for the bottom node that may not be filled, the number of nodes in each layer reaches the maximum value, and the nodes in the bottom layer are all concentrated in the leftmost node of the layer several locations.

1.3 Tree storage method

sequential storage structure
- ? Complete binary tree: according to the order structure from top to bottom, from left to right

linked list storage

1.4 Tree traversal method

Depth-first traversal: Go deep first, and then go back when you encounter a leaf node.
- Preorder traversal (middle left)
- Inorder traversal (left, middle, right)
- Post-order traversal (left and right middle)

Breadth-first traversal (hierarchical traversal): to traverse layer by layer, and then visit the next layer after visiting one layer.

2 Construct a binary tree through a sequence

2.1 Restore the binary tree according to the middle sequence

Given three sequences:

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

(2) Inorder: 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

Analysis:

The idea of restoring a binary tree based on post-order and in-order traversal is to first determine the root node according to post-order traversal, and then in in-order traversal, the left subtree is the left subtree, and the right subtree is the right subtree. The left and right subtrees are divided according to the in-order traversal, and the left and right subtrees are divided in the post-order traversal. We know that the post-order traversal traverses the intermediate nodes at the end, then we can determine the root nodes of the left and right subtrees in the divided left and right subtrees in the post-order traversal, and then return to the in-order traversal to divide the left and right subtrees. And so on until the binary tree is restored.

First round:
Medium: 3 4 8 6 7 5 2 | 10 9 11 15 13 14 12

After: 8 7 6 5 4 3 2 | 10 15 14 13 12 11 9


second round:
Medium: 3 4 8 6 7 5 | null 10 | 11 15 13 14 12

After: 8 7 6 5 4 3 | null 10 | 15 14 13 12 11


Third round:
Middle: null | 4 8 6 7 5 null | 15 13 14 12

After: null | 8 7 6 5 4 null | 15 14 13 12


Fourth round:
Medium: null | 8 6 7 5 15 13 14 | null

After: null | 8 7 6 5 15 14 13 | null


Fifth round:
Medium: 8 6 7 | null 15 | 14

After: 8 7 6 | null


Sixth round:
Medium: 8 | 7

The restored binary tree:

2.2 Restore the binary tree according to the front sequence

Analysis:

Restoring a binary tree based on pre-order traversal and in-order traversal is different from restoring a binary tree based on post-order traversal and in-order traversal in that pre-order traversal first traverses the root node, and then traverses the left and right nodes. First find the root node according to the pre-order traversal, then divide the left and right subtrees in the in-order traversal, then divide the left and right subtrees of the pre-order traversal according to the left and right subtrees divided by the in-order traversal, and then find the left and right subtrees root node. And so on until recovery.

The process will not be described in detail, and it is similar to restoring a binary tree based on post-order traversal and in-order traversal.