From my good friend again EvilSay The contribution of , Here is the original ：

1、 The basic definition

• Each sub node of the binary search tree has at most two leaf nodes
• Each node of the binary search tree has at most one root node
• The stored elements must be comparable
• The value of each sub node in the binary search tree
• Greater than the value of all nodes in its left sub section
• Less than the value of all nodes of its right child
• Binary search trees are not necessarily full

2、 Binary search tree Java Realization

```/**
* @Author: EvilSay
* @Date: 2019/8/6 19:00
*/
public class BSTMain <E extends Comparable<E>> {
private class Node {
public E e;
private Node left, right;

public Node(E e) {
this.e = e;
left = null;
right = null;
}
}

// The root node
private Node root;
private int size;

public BSTMain() {
root = null;
size = 0;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

}

//  towards node Insert elements for the binary search tree of the root E, A recursive algorithm
//  Return to the root of the binary search tree after inserting a new node
private Node add(Node node, E e){

if (node == null){

size ++;
return new Node(e);
}

if (e.compareTo(node.e) < 0)
else if (e.compareTo(node.e) > 0)
return node;
}

//  See if the binary search tree contains elements e
public boolean contains(E e){
return contains(root,e);
}

//  Look at it node Whether the binary search tree for the root contains elements e, A recursive algorithm
private boolean contains(Node node, E e){
if (node == null)
return false;
if (e.compareTo(node.e) == 0)
return true;
else if (e.compareTo(node.e) < 0)
return contains(node.left, e);
else
return contains(node.right,e);
}

@Override
public String toString() {
StringBuilder res = new StringBuilder();
generateBSTSString(root,0,res);
return res.toString();
}

//  Generate to node Root node , Depth is depth A string describing a binary tree
private void generateBSTSString(Node root, int depth, StringBuilder res) {
if (root == null){
res.append(generateDepthString(depth) + "null\n");
return;
}
res.append(generateDepthString(depth) + root.e + "\n");
generateBSTSString(root.left, depth + 1 ,res);
generateBSTSString(root.right, depth + 1, res);

}

private String generateDepthString(int depth) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; i++)
res.append("--");
return res.toString();
}
}```

3、 Graphic binary search tree

From the figure, we can see that the value of each node in the binary search tree is greater than the value of all nodes in its left sub section and less than the value of all nodes in its right sub node .

4、 The former sequence traversal

Preorder traversal is also called preorder traversal , The order of access is around the root , That is, access the root node first , Then to zuozhu , Finally, I came to the right subtree . So the order of access shown above is 5、3、2、4、8、7、9.

Binary search tree traversal before recursive version and non recursive version

```	// Preorder traversal to node Binary search tree for roots , A recursive algorithm
private void preOrder(Node node){

if (node == null)
return;

System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}

// The previous traversal recursive call of binary search tree
public void preOrder(){
preOrder(root);
}

// The pre traversal non recursive writing method of binary search tree
public void preOrderNG(){
Stack<Node> stack = new Stack<>();
// The root node
stack.push(root);

while (!stack.isEmpty()){
Node cur = stack.pop();

System.out.println(cur.e);
// Judge whether there are leaf nodes
if (cur.right != null)
stack.push(cur.right);
if (cur.left != null)
stack.push(cur.left);
}
}```

Understand non recursive implementation logic 、 Deduce the implementation of preamble recursion

• Create a stack , We put the root node 5 Push into the stack , Next we will visit 5 This root node , All of them 5 Push... Out of the stack .
• The elements introduced are {5}, The elements in the stack are [] .
• Pushing in 5 The child node of is 3,8, We go in first, then out , Push in first 8 Push in again 3, Now the elements of the stack are [8,3], Top of stack 3 It's the next node we visit, so 3 Introduction .
• The elements introduced are {5,3}, The elements in the stack are [8] .
• Pushing in 3 The child node of is 2,4 Keep going in and out , Push in first 4 Push in again 2, Now the elements of the stack are [8,4,2], Top of stack 2 It's the next node we visit, so 2 Introduction .
• The elements introduced are {5,3,2}, The elements in the stack are [8,4] .
• Visit the top of the stack 4, because 2 and 4 No child node . So let's just put the 4 Introduction .
• The elements introduced are {5,3,2,4}, The elements in the stack are [8] .
• Visit the top of the stack 8 hold 8 Push out stack , And then 8 Child nodes of 7、9 Push into the stack , Push in first 9 Push back 7 .
• The elements introduced are {5,3,2,4,8}, The elements in the stack are [9,7] .
• visit 7, No child node , Introduction .
• The elements introduced are {5,3,2,4,8,7}, The elements in the stack are [9] .
• visit 9, No child node , Introduction .
• The elements introduced are {5,3,2,4,8,7,9}, The elements in the stack are [] .

5、 In the sequence traversal

In the sequence traversal , The order of access is left root right , That is to visit the left subtree first , And then to the root node , Finally, I came to the right subtree . So the order of access shown above is 2、3、4、5、7、8、9.

Binary search tree in order to traverse recursive version and non recursive version

```    // Recursively call
public void inOrder(){
inOrder(root);
}
// Middle order traversal recursive writing of binary search tree
private void inOrder(Node root){
if (root == null)
return;

inOrder(root.left);
System.out.println(root.e);
inOrder(root.right);
}
// Order traversal in binary search tree is written recursively
public void preInOrderNG(){
//  Create a stack , Similar to preamble traversal
Stack<Node> stack = new Stack<>();

Node node = root;
// Add temporarily finished , Start pop Elements
while(node!=null || stack.size()>0 ){

while(node!=null){
stack.push(node);
node = node.left;
}
// On one side pop And make judgments at the same time , The right node will not null Of , Right subtree , Continue with the addition method , Add all the leftmost nodes
if(stack.size()>0){
Node pop = stack.pop();
System.out.print(pop.e+"  ");
if(pop.right!=null){
node = pop.right;
}
}
}```

Understand non recursive implementation logic 、 Deduce the implementation of middle order recursion

• First of all, we put 5 This node is pushed into the stack , And then 5 The left child of 3 push , And then 3 Of The left child node 2 push , And then 2 The left child node of the ( here 2 The left child node of is empty ,node==null while Loop exit ).
• The elements introduced are {}, The elements in the stack are [5,3,2].
• node It's empty , But there are elements in our stack , Access the top element of the stack 2, And look at 2 Whether there is a right child node . If not, push out the stack and end the loop .
• The elements introduced are {2}, The elements in the stack are [5,3].
• Access the top element of the stack 3, hold 3 Push out the stack , And put 3 Right child of 4 Push into the stack , End of cycle .
• The elements introduced are {2,3}, The elements in the stack are [5].
• Access the top element of the stack 5, hold 5 Push out the stack . hold 5 Right child of 8 Push into the stack , And put 8 The left child of 7 Push into the stack , End of cycle .
• The elements introduced are {2,3,5}, The elements in the stack are [8,7]
• Access the top element of the stack 7, And look at 2 Whether there is a right child node . If not, push out the stack and end the loop .
• The elements introduced are {2,3,5,7}, The elements in the stack are [8].
• Access the top element of the stack 8, hold 8 Push out the stack . hold 8 Right child of 9 Push into the stack
• The elements introduced are {2,3,5,7,8}, The elements in the stack are [9].
• Access the top element of the stack 9, And look at 2 Whether there is a right child node . If not, push out the stack and end the loop .
• The elements introduced are {2,3,4,5,7,8,9}, The elements in the stack are [].

6、 After the sequence traversal

In the sequence traversal , The order of access is left and right , That is to visit the left subtree first , Then to the right subtree , At last, it comes to the root node . So the order of access shown above is 2、4、3、7、9、8、5.

The binary search tree traverses the recursive version and the non recursive version

```// Recursively call
public void postOrder() {
postOrder(root);
}

// The recursive method of post order traversal of binary search tree
private void postOrder(Node node){
if (node == null)
return;

postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}

public void postOrderNG(){
Stack<Node> stack = new Stack<>();
// Using a list Collection records the root nodes that will be traversed , To prevent a dead cycle
ArrayList<Node> list = new ArrayList<>();
Node node = root;
Node proud;
int flag;

// Check the left subtree of the tree , Count the right ones , Finally, output the root node
while (node != null || stack.size() > 0){
while (node != null){
stack.push(node);

node = node.left;
}

// Similar to the middle order traversal , To output the left child node first , But after the node output is finished , You cannot pop the root node directly , You must first pop up the right node ,
// Finally, pop up the root node , It will involve the access state of a root node , Has it been traversed
if (stack.size() > 0){

Node peek = stack.peek();
if (peek.right != null){
boolean con = list.contains(peek);
if (con){
Node pop = stack.pop();
System.out.println(pop.e);
}else{
node = peek.right;
}
}else {
Node pop = stack.pop();
System.out.println(pop.e);
}

}

}
}```

Understand non recursive implementation logic 、 Deduce the implementation of post order recursion

• hold 5 This node is pushed into the stack , And then 5 The left child of 3 push , And then 3 The left child of 2 push , And then 2 The left child node of the ( here 2 The left child node of is empty ,node==null while Loop exit ).
• The elements introduced are {}, The elements in the stack are [5,3,2].
• node It's empty, but we have elements in the stack , Access the top element of the stack 2, And look at 2 Whether there are left child nodes . If not, push out the stack and end the loop .
• The elements introduced are {2}, The elements in the stack are [5,3].
• Access the top element of the stack 3,3 The right subsection of is 4, Judge list If there 3, If it doesn't, put 3 Put in list And put node The assignment is 4 End of cycle .
• The elements introduced are {2}, The elements in the stack are [5,3].
• node by 4, hold 4 Push into the stack , And access the top element of the stack 4, And look at 4 Whether there is a right child node . If not, push out the stack and end the loop .
• The elements introduced are {2,4}, The elements in the stack are [5,3].
• Access the top element of the stack 3,list There is 3, hold 3 And end the loop .
• The elements introduced are {2,4,3}, The elements in the stack are [5].
• Access the top element of the stack 5,5 The right subsection of is 8, Judge lis t If there 8, If it doesn't, put 5 Put in list And put node The assignment is 8 End of cycle .
• The elements introduced are {2,4,3}, The elements in the stack are [5].
• node by 8, hold 8 Push into the stack , And visit the top element of the stack plain 8,8 There are left child nodes 7. hold 7 Push into the stack .
• The elements introduced are {2,4,3}, The elements in the stack are [5,8,7].
• Access the top element of the stack 7, And look at 7 Whether there is a right child node . If not, push out the stack and end the loop .
• The elements introduced are {2,4,3,7}, The elements in the stack are [5,8].
• Access the top element of the stack 8,8 The right child node of is 9. Judge list If there 9, If it doesn't, put 8 Put in list And put node And put node The assignment is 9 End of cycle .
• The elements introduced are {2,4,3,7}, The elements in the stack are [5,8].
• node by 9, hold 9 Push into the stack , And access the top element of the stack 9, And look at 9 Whether there is a right child node . If not, push out the stack and end the loop .
• The elements introduced are {2,4,3,7,9}, The elements in the stack are [5,8].
• Access the top element of the stack 8,list There is 8, hold 8 And end the loop .
• The elements introduced are {2,4,3,7,9,8}, The elements in the stack are [5].
• node There are elements in the empty stack , Access the top element of the stack 5,list There is 5, hold 5 And end the loop .
• The elements introduced are {2,4,3,7,9,8,5}, The elements in the stack are [].

Last

If you see this , Like this article , Please forward 、 give the thumbs-up . WeChat search 「 A good loser 」, Welcome to your attention .

reply 「1024」 Send you a complete set java、python、c++、go、 front end 、linux、 Algorithm 、 big data 、 Artificial intelligence 、 Small program and English Course .

reply 「 e-book 」 Send you 50+ Ben java e-book .