一、二叉排序树概述
二叉排序树是一种特殊的二叉树，满足左子树节点值小于根节点值，右子树节点值大于根节点值。
如图中所示
二、二叉排序树的创建
1.我们先定义一个节点的数据结构TreeNode，一个节点包含左右孩子指针和数据项。
public class TreeNode { public TreeNode lchild; public TreeNode rchild; public Integer data; public TreeNode(Integer data){ this.data = data; } }2.我们需要一个指针root用来指向树的根节点，还需要一个指针curNode来指向当前判断的节点，除了判断新节点是否大于或小于curNode，还需要判断curNode的左右孩子节点是不是空，如果不是空我们需要循环把curNode指向其孩子节点继续判断，直到curNode的孩子节点为空插入新节点。
以下是代码流程：新插入节点判断
（1）如果root == null，新插入节点作为根节点，不为null进行值的判断
（2）循环判断新插入节点的值是否小于当前节点，如果小往左走直到为null插入
（3）循环判断新插入节点的值是否大于当前节点，如果大往右走直到为null插入
public class BinaryTree { public TreeNode root; public void create(Integer data){ TreeNode newNode = new TreeNode(data); //选择一个节点作为根节点 if(root == null){ root = newNode; return; } TreeNode curNode = root; while(true){ //新节点大于当前判断节点 if(curNode.data < newNode.data){ //判断节点的右孩子节点是空的可以插入，否则右孩子节点做下次判断节点 if(curNode.rchild == null){ curNode.rchild = newNode; return; } curNode = curNode.rchild; }else { //判断节点的左孩子节点是空的可以插入，否则左孩子节点做下次判断节点 if(curNode.lchild == null){ curNode.lchild = newNode; return; } curNode = curNode.lchild; } } } }三、深度优先遍历
深度优先遍历是指按照某种规则访问树中的所有节点，且每个节点仅访问一次。三种主要的遍历方式：
先序遍历：根节点 → 左子树 → 右子树
中序遍历：左子树 → 根节点 → 右子树
后序遍历：左子树 → 右子树 → 根节点
这里的"先"、"中"、"后"指的是根节点被访问的时机。
3.1先序遍历
访问顺序：（1）访问根节点（2）先序遍历左子树（3）先序遍历右子树
//先序遍历 public void beforeOrder(TreeNode root){ if(root == null){ return; } System.out.println(root.data); //访问根节点 beforeOrder(root.lchild); //先序遍历左子树 beforeOrder(root.rchild); //先序遍历右子树 }我们以上图排序树为例给出遍历过程
（1）访问根节点5
（2）遍历5的左子树（3为根）
访问3
遍历3的左子树（0为根）
访问0，0无左子树，0无右子树
遍历3的右子树（4为根）
访问4，4无左子树，4无右子树
（3）遍历5的右子树（7为根）
访问7
遍历7的左子树（6为根）
访问6；6无左子树；6无右子树
遍历7的右子树（9为根）
访问9；9无左子树；9无右子树
结果：5 3 0 4 7 6 9
先序遍历的输出整体看是从根到左再到右，所以先序遍历适合用在复制树的结构和前缀表达式中
3.2中序遍历
访问顺序：（1）中序遍历左子树（2）访问根节点（3）中序遍历右子树
//中序遍历 public void inOrder(TreeNode root){ if(root == null){ return; } inOrder(root.lchild); //中序遍历左子树 System.out.println(root.data); //访问根节点 inOrder(root.rchild); //中序遍历右子树 }遍历分析过程与上面先序同理，中序遍历上图结果：0 3 4 5 6 7 9
我们不难发现中序遍历结果是顺序的，所以中序遍历适合二叉排序树的有序输出
3.3后续遍历
访问顺序：（1）后序遍历左子树（2）后序遍历右子树（3）访问根节点
//后续遍历 public void afterOrder(TreeNode root){ if(root == null){ return; } afterOrder(root.lchild); //后续遍历左子树 afterOrder(root.rchild); //后续遍历右子树 System.out.println(root.data); //访问根节点 }遍历上述图结果：0 4 3 6 9 7 5
后序遍历整体输出是从叶子节点到根节点，所以后序遍历适合用在删除树和后缀表达式中
四、广度优先遍历
广度优先遍历又称层次遍历，原理是按层次从上到下访问节点，同一层从左到右访问，使用队列（先进先出）保证访问顺序。
以下是代码流程：
（1）根节点先入队
（2）循环执行队列不为空时
1.队头节点出队并访问该节点
2.如果该节点的左孩子节点存在，则左孩子节点入队
3.如果该节点的右孩子节点存在，则右孩子节点入队
（3）直到队列为空
//层次遍历 public void levelOrder(TreeNode root){ LinkedList<TreeNode> linklist = new LinkedList<TreeNode>(); linklist.add(root); while(!linklist.isEmpty()){ root = linklist.pop(); System.out.println(root.data); if(root.lchild != null){ linklist.add(root.lchild); } if (root.rchild != null){ linklist.add(root.rchild); } } }五、查找算法
二叉排序树的查找可以递归实现，先判断是否为空树，然后判断根节点是否为要找的目标节点，最后判断如果根节点大于目标节点则递归返回把根节点左孩子作为形参，否则递归返回根节点右孩子作为形参。
public TreeNode find(TreeNode root,Integer target){ if(root == null){ return null; } if(Objects.equals(root.data, target)){ return root; } else if(root.data > target){ return find(root.lchild,target); }else { return find(root.rchild,target); } }
