Explanation of exercises related to binary tree

   Personal home page ： Welcome to ——> Populus euphratica under the desert

  Ladies and gentlemen , It's beautiful

  If you think the article is helpful to you

  You can support bloggers with one key and three links

  Your every care is the driving force of my persistence

 

 ： This issue focuses on ： Explanation of binary tree exercises

   I hope everyone can study and work happily every day . 

Today, let's look at some simple topics in binary trees ：

1. Let a binary tree have 3 Leaf node , Yes 8 The individual degree is 1 The node of , Then the total number of nodes in the binary tree is ：___

This topic examines our two knowledge points ：

1. Sum up the number of points = leaf node + Degree is 1 The node of + Degree is 2 The node of .

2. Number of leaf nodes = Degree is 2 Number of nodes +1. 

After knowing the above knowledge points, we can easily know that the total number of nodes is 3+8+2 = 13 individual

2. It is known that the preorder traversal sequence of a binary tree is 5 7 4 9 6 2 1, The middle order traversal sequence is 4 7 5 6 9 1 2, Then the subsequent traversal sequence is _______

First, we find the root according to the previous order , Then traverse according to the middle order to find the subtree of the root , In order to determine the interval of the subtree , So we come to the following conclusion ：

5 It is the root contact , 4,7 It's a left tree ,6,9,1,2 It's the right subtree

5 The root of the left subtree of is 7 ,5 The root of the right subtree of is 9.

7 The left subtree of is 4, The right subtree is empty ,

9 The left subtree of is 6, The right subtree is 2,

2 The left subtree of is 1.

The diagram of the whole binary tree is as follows ：

The subsequent traversal is ：4,7,6,1,2,9,5

3. It is known that the middle order traversal sequence of a binary tree is JGDHKBAELIMCF, The postorder traversal sequence is JGKHDBLMIEFCA, Then the preorder traversal sequence is _____________

We need to look at the sequence first, and determine according to the root node , Look at the previous order to determine the root of the left subtree , Then look at the following order to determine the root of the right subtree , In this way, the tree can be drawn by looping and determining the node .

First, according to the subsequent traversal, the root node is ：A, According to the pre sequence and post sequence traversal

A The left tree of is JGDHKB  A The right tree of is ELIMCF

A The root of the left subtree of B,A The root of the right subtree of is C

B The left subtree JGDHK,B The right tree of is empty   ,C The left subtree ELIM,C The right subtree of is F

B The root of the left subtree of is D, The right subtree is empty ,C The root of the left subtree of is E, The right subtree is F

D The root of the left subtree of is G,D The right subtree of is H

G The left subtree of is J, The right subtree is empty ,H The left subtree of is empty , The right subtree is K

C The root of the left tree of is E, The right tree is F

E The left tree of is I M L

E The root node of the left tree of is I 

 I  The left tree of is L,I The right tree of is M

At this point, we have finished the analysis , The schematic diagram is as follows

 

 

 

4. Binary tree ____ Traversal is equivalent to breadth first traversal ,_____ Traversal is equivalent to depth first traversal

Sequence traversal of binary tree is equivalent to breadth first convenience , The most convenient thing in line with depth first is the preorder traversal .（ Middle order and post order can also be called depth first traversal , But the most consistent is the preface ）

Breadth first needs to traverse all possible positions in the next step , Will carry out deeper traversal .

Depth first is to traverse a complete path first （ The complete path from root to leaf ）, Will turn back to the upper layer , Then go to the next path .

5. If the result of the preorder traversal of a binary tree is ABCD, Then the different binary trees satisfying the conditions have ____ Kind of

This binary tree must be 3 Layer to 4 layer , We analyze the situation ：

3 When the layer ：

 

4 layer ：

 

4 When the layer , our D There are two ways （ stay C About ） We C There are two ways （ stay B About ） We B There are two forms ( stay A About ) Is the total 2*2*2 = 8 Kind of  

 

The two cases add up ： 6+8 = 14

6. The preorder traversal sequence of a non empty binary tree is just opposite to the postorder traversal sequence , Then the binary tree must satisfy

The preorder traversal is ： root , The left subtree , Right subtree     The subsequent traversal is ： The left subtree , Right subtree , root

If only one of the left and right subtrees exists , Then the traversal result must be the opposite .

therefore , The conclusion is that there is only one leaf node , The traversal result is the opposite .