Traversal and properties of binary trees

Related terms
① node ： It contains a data element and some information pointing to the branches of the subtree .
② Degree of node ： The number of subtrees a node has is called the degree of nodes .
③ Leaf node ： Also known as terminal node , Nodes without subtree or nodes with zero degree .
④ Branch nodes ： Also known as non terminal node , A node whose degree is not zero is called a non terminal node .
⑤ The degree of a tree ： The maximum degree of all nodes in the tree .
⑥ Hierarchy of nodes ： Start at the root node , Assume that the root node is the second node 1 layer , The child node of the root node is the 2 layer , And so on , If a node is located in the L layer , Then the child node is located in the L+1 layer .
⑦ Depth of tree ： Also known as the height of the tree , The maximum hierarchical value of all nodes in the tree is called the depth of the tree .
⑧ Ordered trees ： If the order of the trees is in order , The tree is called an ordered tree .
⑨ Disordered trees ： If there is no order among the trees , The tree is called unordered tree .
⑩ The forest ： from m（m≥0） Disjoint trees form a forest . If you delete the root node of a non empty tree , Then the tree becomes a forest , The trees in the forest are made up of the original root nodes .

Special type
1、 Full binary tree ： The depth of a tree is one k And there are 2^k-1 A binary tree with two nodes is called a full binary tree .
2、 Perfect binary tree ： Except for the lowest level , Every other layer is full , The nodes of the lowest layer are concentrated in several positions on the leftmost side of the layer .
The characteristic of complete binary tree is that leaf nodes can only appear on the two largest layers of sequence , And the maximum sequence of the descendants of the left branch of a node is equal to or larger than that of the descendants of the right branch 1.

Properties of binary trees
nature 1： The second fork is the tree i The maximum number of nodes on the layer is 2^i-1.
nature 2： Depth is k At most, the binary tree of 2^k-1 Nodes (k≥1).
nature 3： Two fork tree , The number of leaf nodes is n0, Degree is 2 The node number of is n2, be no=n2+1.

Traversal operation of binary tree （ Recursive definition ）
(1) The first sequence traversal ： root , The left subtree , Right subtree
(2) In the sequence traversal ： The left subtree , root , Right subtree
(3) After the sequence traversal ： The left subtree , Right subtree , root

chart 1：

First ：2 7 1 6 5 3 8 9 4;
in ：1 7 5 6 3 2 8 4 9;
after ：1 5 3 6 7 4 9 8 2;

chart 2：

First ：A B C K D E H F J G;
in ：B K C A H E D J F G;
after ：K C B H E J G F D A;

notes ：
First and middle orders are known , Binary tree is the only .
Known post order and middle order , Binary tree is the only .
The first order and the second order are known , Binary tree is not unique .
Because order first and then order can only judge the root , In order to judge the right and left subtrees .

Question 1 ： Some of the traversal results are known , Find other traversal results .
Question 2 ： Transformation from infix expression to prefix and suffix expression
Question 3 ： Statistics ｎ How many different binary trees can be constructed from different points ? Catalan Count =C(n,2*n)/(n+1).
After simplification ：(2n)!/n!(n+1)!

practice
1、 We know the antecedent ：1 2 4 3 5 7 6, Middle preface ：2 4 1 7 5 3 6, Please draw the whole binary tree .
2、 After knowing the sequence ：4 5 2 6 7 3 1, Middle preface ：4 2 5 7 6 3 1, Please draw the whole binary tree .
3、 We know the antecedent ：1 2 3 4 5 6, In the following order ：3 2 5 6 4 1, Please draw all binary trees .
4、 If you only know the sequence ａｂｃ, Draw all possible binary tree shapes , And calculate how many ？
5、 If you only know the middle order ａｂｃ, Draw all possible binary tree shapes , And calculate how many ？
6、 If you only know the sequence ａｂｃ, Draw all possible binary tree shapes , And calculate how many ？

Over the years
2010 Improve （ Same as 2010 Universal ）
5、 The preorder traversal sequence of a binary tree is ABCDEFG, The postorder traversal sequence is CBFEGDA, Then the number of nodes of the left subtree of the root node may be （ ）.
A．0 B．2 C．4 D． 6
2009 Improve （ Same as 2009 Universal ）
6、 expression a*(b+c)-d The suffix expression for is ：
A) abcd*± B) abc+d- C) abc+d- D) -+*abcd
2008 Improve
16、 Binary tree T, It is known that its preorder traversal is 1 2 4 3 5 7 6（ The number is the node number , The following are the same as ）, Postorder traversal is 4 2 7 5 6 3 1, Then the middle root traversal of the binary tree is （ ）
A．4 2 1 7 5 3 6 B．2 4 1 7 5 3 6 C．4 2 1 7 5 6 3 D．2 4 1 5 7 3 6
2008 Universal
13、 Binary tree T, It is known that its first root traversal is 1 2 4 3 5 7 6（ The number is the node number , The following are the same as ）, The middle root traversal is 2 4 1 5 7 3 6, Then the post root traversal of the binary tree is （ ）
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1
2007 Improve
12、 It is known that 7 The first root traversal of a binary tree of nodes is 1 2 4 5 6 3 7( The number is the number of the node , The following are the same as ), The last root traversal is 4 6 5 2 7 3 1, Then the possible middle root traversal of the binary tree is ( )
A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 6 7 D. 4 2 5 6 1 7 3
2007 Universal
20、 It is known that 7 The first root traversal of a binary tree of nodes is 1 2 4 5 6 3 7（ The number is the number of the node , The following are the same as ）, The middle root traversal is 4 2 6 5 1 7 3, Then the post root traversal of the binary tree is （ ）
A．4 6 5 2 7 3 1 B．4 6 5 2 1 3 7 C．4 2 3 1 5 4 7 D．4 6 5 3 1 7 2
2006 Improve （ Same as 2006 Universal ）
14、 It is known that 6 The first root traversal of a binary tree of nodes is 1 2 3 4 5 6（ The number is the number of the node , The following are the same as ）, The last root traversal is 3 2 5 6 4 1, Then the possible middle root traversal of the binary tree is （ ）
A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5
answer ：
2010 Improve ：B
2009 Improve ：6B
2008 Improve ：16ABD
2008 Universal ：13B
2007 Improve ：14ABD
2007 Universal ：20A
2006 Improve ：14BC