Binary search tree

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;
    }
    public void add(E e){

        root = add(this.root, e);

    }

    //  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)
            node.left = add(node.left, e);
        else if (e.compareTo(node.e) > 0)
            node.right = add(node.right,e);
        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

 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){
        // Add the leftmost subtree 
        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{
                    list.add(peek);
                    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 .

 programing language

 A good loser