PROGRAMMING:Binary search tree four traversal【 [template]
This is a template problem!
Here we redefine the binary search tree
The left child and its subtree of all nodes are less than the node, and the right child and its subtree of all nodes are greater than or equal to the node.
Considering that you may not be familiar with how to build a binary search tree, how to insert nodes into it, and how to implement three kinds of traversal, we will give the complete C + + code of how to build a binary search tree from scratch.
The first is the definition of the structure. For a BST node, we will define three information in the structure, namely its data field and two pointers, pointing to the left and right children respectively!
Next is to insert the nodes into the search tree one by one!
Then, we just need to define a root node to be empty, and then run the create function with the elements to be inserted as parameters in turn to get a binary search tree!
Next, we do the preorder, middle order and postorder traversal of the BST, and we can find that the output positions of the three traversals are different!
The following shows sequence traversal, which is different from the other three kinds of traversal. Sequence traversal needs to call a previous data structure queue. The queue here directly calls the STL library of C + +, which must be very simple for you who are good at English!
The above code fragment shows the process of building a binary search tree from scratch and doing four kinds of traversal!
Now give a binary search tree insertion sequence, please insert the number in the sequence into an empty binary search tree in turn, and output its pre order, middle order, post order, sequence traversal!
###Input format:
The first line contains a positive integer n (n < = 1000) indicating the number of elements of the inserted sequence.
The second line contains n integers representing the insertion sequence（ Ensure that all elements are in the range of int
###Output format:
The first line outputs n integers, representing its preamble sequence.
The second line outputs n integers, representing its middle order sequence.
The third line outputs n integers to represent its subsequent sequence.
The fourth line outputs n integers to represent its sequence.
All integers are separated by a space, with no extra space at the end of each line.
###Input example:
Here is a set of inputs. For example:
```in
three
2 1 3
```
###Output example:
The corresponding output is given here. For example:
```out
2 1 3
1 2 3
1 3 2
2 1 3
```
answer：If there is no answer, please comment
Here we redefine the binary search tree
The left child and its subtree of all nodes are less than the node, and the right child and its subtree of all nodes are greater than or equal to the node.
Considering that you may not be familiar with how to build a binary search tree, how to insert nodes into it, and how to implement three kinds of traversal, we will give the complete C + + code of how to build a binary search tree from scratch.
The first is the definition of the structure. For a BST node, we will define three information in the structure, namely its data field and two pointers, pointing to the left and right children respectively!
Next is to insert the nodes into the search tree one by one!
Then, we just need to define a root node to be empty, and then run the create function with the elements to be inserted as parameters in turn to get a binary search tree!
Next, we do the preorder, middle order and postorder traversal of the BST, and we can find that the output positions of the three traversals are different!
The following shows sequence traversal, which is different from the other three kinds of traversal. Sequence traversal needs to call a previous data structure queue. The queue here directly calls the STL library of C + +, which must be very simple for you who are good at English!
The above code fragment shows the process of building a binary search tree from scratch and doing four kinds of traversal!
Now give a binary search tree insertion sequence, please insert the number in the sequence into an empty binary search tree in turn, and output its pre order, middle order, post order, sequence traversal!
###Input format:
The first line contains a positive integer n (n < = 1000) indicating the number of elements of the inserted sequence.
The second line contains n integers representing the insertion sequence（ Ensure that all elements are in the range of int
###Output format:
The first line outputs n integers, representing its preamble sequence.
The second line outputs n integers, representing its middle order sequence.
The third line outputs n integers to represent its subsequent sequence.
The fourth line outputs n integers to represent its sequence.
All integers are separated by a space, with no extra space at the end of each line.
###Input example:
Here is a set of inputs. For example:
```in
three
2 1 3
```
###Output example:
The corresponding output is given here. For example:
```out
2 1 3
1 2 3
1 3 2
2 1 3
```
answer：If there is no answer, please comment