Algorithm | traversal of binary search tree

二分搜索树

Another contribution from my good friend EvilSay, the following is the original text:

1. Basic Definition

  • Each child 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.
  • Stored elements must be comparable
  • The value of each child node of the binary search tree

    • Is greater than the value of all nodes in its left subsection
    • The value of all nodes smaller than its right child node
  • The binary search tree is not necessarily full

2. Java implementation of binary search tree

/**
 * @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;
        }
    }

    //根节点
    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);

    }

    // 向node为根的二分搜索树中插入元素E,递归算法
    // 返回插入新节点后二分搜索树的根
    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;
    }

    // 看二分搜索树中是否包含元素e
    public boolean contains(E e){
        return contains(root,e);
    }

    // 看以node为根的二分搜索树中是否包含元素e,递归算法
    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();
    }

    // 生成以node为根节点,深度为depth的描述二叉树的字符串
    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. Graphical Binary Search Tree

二分搜索树

We can see from the figure that the value of each node of the binary search tree is greater than that of all nodes in its left child node and less than that of all nodes in its right child node.

4. Preorder traversal

Pre-order traversal is also called pre-order traversal. The access order is around the root, that is, the root node is accessed first, then the left subtree, and finally the right subtree. Therefore, the access sequence shown in the above figure is 5, 3, 2, 4, 8, 7 and 9.

The binary search tree traverses the recursive version and the non-recursive version in the preamble.

    //前序遍历以node为根的二分搜索树,递归算法
    private void preOrder(Node node){

        if (node == null)
            return;

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }
    
    //二分搜索树的前序遍历递归调用
    public void preOrder(){
        preOrder(root);
    }
    
    //二分搜索树的前序遍历非递归写法
    public void preOrderNG(){
        Stack<Node> stack = new Stack<>();
        //根节点
        stack.push(root);

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

            System.out.println(cur.e);
            //判断是否还有叶子节点
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
    }

Understand the non-recursive implementation logic and deduce the implementation of pre-order recursion.

  • To create a stack, we push the root node 5 into the stack, then we will visit the root node 5, all pushing the 5 out of the stack.
  • The pushed elements are {5}, and the stack elements are [].
  • The child nodes that push in 5 are 3,8. We enter first and then go out, push in 8 and then push in 3. Now the stack has [8, 3] elements. The 3 at the top of the stack is the node that we visit next time, so we push out 3.
  • The pushed elements are {5,3}, and the elements in the stack are [8].
  • The child node of push-in 3 is 2,4, which continues to be first in and then out, first push-in 4 and then push-in 2. Now there are [8,4, 2] elements in the stack, and 2 at the top of the stack is the node we visit next time, so push-out 2.
  • The pushed elements are {5,3,2}, and the elements in the stack are [8,4].
  • Access stack top 4 because 2 and 4 have no child nodes. So we pushed 4 out of the top of the stack directly.
  • The pushed elements are {5,3,2,4}, and the elements in the stack are [8].
  • Access to the top of the stack 8 pushes 8 out of the stack, and then push the child nodes 7 and 9 of 8 into the stack, pushing 9 first and then 7.
  • The pushed elements are {5,3,2,4,8}, and the elements in the stack are [9,7].
  • Access 7, no child nodes, push out.
  • The pushed elements are {5,3,2,4,8,7}, and the elements in the stack are [9].
  • Access 9, no child nodes, push out.
  • The pushed elements are {5,3,2,4,8,7,9}, and the elements in the stack are [].

5, the middle order traversal

The middle order traversal, access order is left root right, that is to say, first access the left subtree, then to the root node, and finally to the right subtree. Therefore, the access sequence shown in the above figure is 2, 3, 4, 5, 7, 8 and 9.

Sequential traversal recursive version and non-recursive version in binary search tree

    //递归调用
    public void inOrder(){
        inOrder(root);
    }
    //二分搜索树的中序遍历递归写法
    private void inOrder(Node root){
        if (root == null)
            return;

        inOrder(root.left);
        System.out.println(root.e);
        inOrder(root.right);
    }
    //二分搜索树中序遍历给递归写法
    public void preInOrderNG(){
        // 创建栈,和前序遍历类似
        Stack<Node> stack = new Stack<>();
        
        Node node = root;
        //添加暂时完毕,开始pop元素
        while(node!=null || stack.size()>0 ){

            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            //一边pop并且一边进行判断,右结点不会null的,右子树,继续按照添加方法,将最左结点全部添加进去
            if(stack.size()>0){
                Node pop = stack.pop();
                System.out.print(pop.e+"  ");
                if(pop.right!=null){
                    node = pop.right;
                }
            }
        }

Understand the non-recursive implementation logic and deduce the implementation of mid-order recursion.

  • First, we push the node 5 into the stack, then push the left child node 3 of 5, then push the left child node 2 of 3, and then push the left child node of 2 (at this time, the left child node of 2 is empty, node==null while loop exits).
  • The pushed elements are {}, and the stack elements are [5,3,2].
  • Node is empty, but we still have elements in the stack. Visit element 2 at the top of the stack and see if 2 has any right child nodes. If not, push the stack and end the loop.
  • The pushed elements are {2} and the stack elements are [5,3].
  • Access stack top element 3, push 3 out of the stack, and push right child node 4 of 3 into the stack, ending the loop.
  • The pushed elements are {2,3}, and the elements in the stack are [5].
  • Access stack top element 5 and push 5 out of the stack. Push the right child node 8 of 5 into the stack, and push the left child node 7 of 8 into the stack, ending the loop.
  • The pushed elements are {2,3,5}, and the elements in the stack are [8,7]
  • Access stack top element 7 and see if 2 has a right child node. If not, push the stack and end the loop.
  • The pushed elements are {2,3,5,7}, and the elements in the stack are [8].
  • Access stack top element 8 and push 8 out of the stack. Push the right child node 9 of 8 into the stack
  • The pushed elements are {2,3,5,7,8}, and the elements in the stack are [9].
  • Access stack top element 9 and see if 2 has a right child node. If not, push the stack and end the loop.
  • The pushed elements are {2,3,4,5,7,8,9}, and the elements in the stack are [].

6. Sequential traversal

The middle order traversal, access order is left and right roots, that is to say, first access the left subtree, then to the right subtree, and finally to the root node. Therefore, the access sequence shown in the above figure is 2, 4, 3, 7, 9, 8 and 5.

After the binary search tree, the recursive version and the non-recursive version are traversed sequentially.

//递归调用
public void postOrder() {
    postOrder(root);
} 

//二分搜索树的后序遍历递归方法
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<>();
    //利用一个list集合记录已将被遍历过的根节点,防止产生死循环
    ArrayList<Node> list = new ArrayList<>();
    Node node = root;
    Node proud; 
    int flag; 

    //首页检查完树的左子树,再右子数,最后将根节点输出
    while (node != null || stack.size() > 0){
        //将最左子树添加完毕
        while (node != null){
            stack.push(node);

            node = node.left;
        } 

        //和中序遍历相似,为先输出左子节点,但是做节点输出完毕之后,不能直接将根节点弹出,而是必须先将右节点弹出,
        //最后再将根节点弹出来,就会牵扯到一个根节点的访问状态的问题,是否已经被遍历过了
        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 the non-recursive implementation logic and deduce the implementation of subsequent recursion.

  • Push the node 5 into the stack, push the left child node 3 of 5, push the left child node 2 of 3, and push the left child node of 2 (at this time, the left child node of 2 is empty, node==null while loop exits).
  • The pushed elements are {}, and the stack elements are [5,3,2].
  • Node is empty but we still have elements in the stack. Visit element 2 at the top of the stack and see if 2 has left child nodes. If not, push the stack and end the loop.
  • The pushed elements are {2} and the stack elements are [5,3].
  • Accessing the right subsection of stack top elements 3, 3 is 4, judging whether there is 3 in the list, if not, putting 3 in the list and assigning node to 4 to end the loop.
  • The pushed elements are {2} and the stack elements are [5,3].
  • Node is 4, push 4 into the stack, and access the top element 4 of the stack, and see if 4 has a right child node. If not, push the stack and end the loop.
  • The pushed elements are {2,4}, and the elements in the stack are [5,3].
  • Access stack top element 3, 3 in list, push 3 out of stack and end loop.
  • The pushed elements are {2,4,3}, and the elements in the stack are [5].
  • Accessing the right subsection of stack top elements 5, 5 is 8, judging whether there is 8 in lis t, if not, putting 5 in list and assigning node to 8 to end the loop.
  • The pushed elements are {2,4,3}, and the elements in the stack are [5].
  • Node is 8, push 8 into the stack, and access the stack top element 8, 8 has left child node 7. Push 7 into the stack.
  • The pushed elements are {2,4,3}, and the elements in the stack are [5,8,7].
  • Access stack top element 7 and see if 7 has a right child node. If not, push the stack and end the loop.
  • The pushed elements are {2,4,3,7}, and the elements in the stack are [5,8].
  • The right child node accessing the stack top elements 8, 8 is 9. Judge whether there are 9 in the list, if not, put 8 in the list and assign node to 9 to end the loop.
  • The pushed elements are {2,4,3,7}, and the elements in the stack are [5,8].
  • Node is 9, push 9 into the stack, access the top element 9 of the stack, and see if 9 has a right child node. If not, push the stack and end the loop.
  • The pushed elements are {2,4,3,7,9}, and the elements in the stack are [5,8].
  • Access the top element 8 of the stack, there are 8 in the list, push the 8 out of the stack and end the loop.
  • The pushed elements are {2,4,3,7,9,8}, and the elements in the stack are [5].
  • Node is empty, there are elements in the stack, access the top element 5, there are 5 in the list, push the 5 out of the stack and end the loop.
  • The pushed elements are {2,4,3,7,9,8,5}, and the elements in the stack are [].

Recommended reading:

1. java | What is Dynamic Proxy

2. SpringBoot | Startup Principle

3. SpringBoot | Automatic Configuration Principle

一个优秀的废人