二叉排序树的概念（广泛用于查找）

二叉排序树的概念：

满足：

1.树的左子树的如果存在，并且左子树的所有节点都小于根节点；

2.树的右子树如果存在并且右子树的所有节点都大于根节点；

3.左子树和右子树同样是二叉排序树；

二叉排序树常用于查找之上：

package com.ydlclass.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

public class BST {
    //二叉排序树

    public static class Node{
        Integer data;
        Node left;
        Node right;

        public Node(Integer data) {
            this.data = data;
        }
    }

    //递归实现树的遍历
    public static void recursive(Node node){
        if (node == null){
            return;
        }
        recursive(node.left);
        recursive(node.right);
    }

    //递归实现前序遍历
    public static void preOrder(Node node){
        if (node == null){
            return;
        }
        System.out.println(node.data);
        preOrder(node.left);
        preOrder(node.right);
    }


    //递归实现中序遍历
    public static void midOrder(Node node){
        if(node == null){
            return;
        }
        midOrder(node.left);
        System.out.println(node.data);
        midOrder(node.right);

    }

    //递归实现后序遍历
    public static void postOrder(Node node){
        if (node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);

    }

    //使用栈实现前序遍历

    public static void stackImplement(Node node){
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while(!stack.isEmpty()){
            node = stack.pop();
            System.out.println(node.data);
            if(node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
    }

    //使用队列实现层级遍历；
    public static void linkImplement(Node node){
        LinkedList<Node> link = new LinkedList<>();
        link.addFirst(node);
        while (!link.isEmpty()){
            node = link.removeLast();
            System.out.println(node.data);
            if (node.left != null){
                link.addFirst(node.left);
            }
            if (node.right != null){
                link.addFirst(node.right);
            }
        }
    }

    //二叉排序树查找值
    public static void selectVal(Node node,int target){
        while (node != null){
            if (target == node.data){
                System.out.println(node.data);
                if (node.left != null){
                    System.out.println(node.left.data);
                }
                if (node.right != null){
                    System.out.println(node.right.data);//分别验证查找的节点的左子节点和右子节点
                }
                return;
            } else if (target < node.data){
                node = node.left;
            } else if (target > node.data){
                node = node.right;
            }
        }
        return;
    }
    public static void main(String[] args) {
//        Node root = new Node(3);
//        root.left = new Node(5);
//        root.right = new Node(7);
//        root.left.left = new Node(1);
//        root.left.right = new Node(12);
//        root.right.left = new Node(8);
//        root.right.right = new Node(9);
        Node root = new Node(6);
        root.left = new Node(4);
        root.right = new Node(11);
        root.left.left = new Node(1);
        root.left.right = new Node(5);
        root.right.left = new Node(7);
        root.right.right = new Node(12);

//        preOrder(root);
//        System.out.println("___");
//        midOrder(root);
//        System.out.println("___");
//        postOrder(root);
//        System.out.println("___");
//        linkImplement(root);
//        System.out.println("___");
        selectVal(root,4);
    }
}