一、构建二叉树
1.引入：
如图，树的一个节点拥有三个关键部分，分别是左子节点（lChild）、右子节点（rChild）和值（data）。
就拿有序二叉树来说，它的特点是：左子节点的值比父节点小，右子节点比父节点大
例如：构建有序二叉树4871923
2.我们该如何用代码构建构建它呢？
①先定义一个树的Java类，把它里边所含有的成员变量声明出来：
public class TreeNode { public TreeNode lChild; public TreeNode rChild; public Integer data; public TreeNode(Integer data){ this.data = data; } }类是创建对象的模板，我们先创建了类才能创建对象。
②再创建一个有序二叉树的类，我们把我们要写的构建方法写在里边：
首先创建头指针：
TreeNode root;然后在下边我们就改写相应的构建二叉排序树的方法了，我们就要先思考它的逻辑，新加入节点该如何用代码实现判断？怎么根据数值大小判断是该往左子节点走还是右子节点走？
a.如果root=null，新插入节点为根节点，如果不为null，那么就进行值得判断，继续往下走；
b.循环判断（用while（true））插入节点的值是否比当前的值小，小则左走，直到左边为null，大则右走，直到右边为null。
//1.判断根节点是否为空 if(root==null){ root=newNode; return; } //2.不为空就循环判断值 while(true){ TreeNode curNode=root; if(curNode.data<newNode.data){ if(curNode.rChild==null){ curNode.rChild=curNode; return; } curNode=curNode.rChild; if(curNode.data>newNode.data){ if(curNode.lChild==null){ curNode.lChild=curNode; return; } curNode=curNode.lChild;然后我们在Test类中测试该create（）方法就行了
public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.create(5); bt.create(3); bt.create(7); bt.create(0); bt.create(4); bt.create(6); bt.create(9);二、树的遍历
1.我们创建好了树，那么树该怎么实现遍历呢？
首先我们要知道树的遍历有哪些种类：
通常形况下树的遍历自己一个一个走太麻烦了，所以昨天新学了一个方法，感觉还是比较好用的：
画三角法。
就拿刚才的树来说吧：
画三角，把各个节点小树划分出来，之后变成了：
①前序遍历：
前序遍历是根左右，就先看最上边的树对应写出【4 1 8】；
然后再遍历左边1的子节点，1左右是2、3，也就是【4 12 38】；
2和3下边没有子节点，我们就再遍历右边8的子节点，8的左右是7、9，也就是【4 1 2 3 87 9】；
②中序遍历：
中序遍历是左根右，依旧先看上边的树，对应写出【1 4 8】；
然后遍历左边1的子节点，对应写出【2134 8】；
遍历右边写出【2 1 3 4789】；
③后序遍历：
根据上述规则，最后写出【2 3 1 7 9 8 4】；
④层序遍历：
从上到下、从左到右一层一层遍历：【4 1 8 2 3 7 9】；
2.我们已经搞清楚了树的遍历逻辑，那么如何用代码实现树的遍历呢？
①前序遍历
写出相应的前序遍历（beforeOrder）方法，先判断根节点是否为null，空则返回，不为空就分别输出根的值、左子节点的值和右子节点的值：
// 前序遍历 void beforeOrder(TreeNode root) { if (root == null) { return; } System.out.println(root.data); beforeOrder(root.lChild); beforeOrder(root.rChild); }②中序遍历
写出相应的中序遍历（inOrder）方法，先判断根节点是否为null，空则返回，不为空就分别输出左子节点的值、根的值和右子节点的值：
//后序遍历 void afterOrder(TreeNode root) { if (root == null) { return; } afterOrder(root.lChild); afterOrder(root.rChild); System.out.println(root.data); }③后序遍历
写出相应的中序遍历（afterOrder）方法，先判断根节点是否为null，空则返回，不为空就分别输出左子节点的值、右子节点的值和根节点的值：
//后序遍历 void afterOrder(TreeNode root) { if (root == null) { return; } afterOrder(root.lChild); afterOrder(root.rChild); System.out.println(root.data); }④层序遍历
a.初始化队列，根节点入队；
b.循环出队节点，访问该节点；
c.把该节点的左、右子节点（下一层）入队；
d.重复步骤 b和c，直到队列为空。
//层序遍历 void levelOrder(TreeNode root) { LinkedList<TreeNode> queue=new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ root=queue.pop(); System.out.println(root.data); if(root.lChild!=null){ queue.add(root.lChild); } if(root.rChild!=null){ queue.add(root.rChild); } } }三、树的查询
1.查询树的逻辑是什么？
①利用二叉搜索树 “左小右大” 的特性，通过递归缩小查找范围；
②递归终止条件：找到目标节点（返回节点）或遍历到空节点（返回 null）；
③分岔逻辑：目标值大于当前节点则查右子树，小于则查左子树，实现 “二分式” 高效查找。
//节点查询 public TreeNode searchNode(TreeNode root,Integer target){ if(root==null||root.data==target){ return root; } if(target>root.data){ return searchNode(root.rChild,target); }else{ return searchNode(root.lChild,target); } }Test代码
运行结果
