增加元素
判断root是否为null -为null,则将元素封装成节点,称为root,返回true -不为null,和root进行比较,比较的目的是将元素尝试添加为root的left/right子树 - 和root相等,添加失败,返回false,结束 - 大于>root,尝试添加为root的right;判断right是否为null, - 为null,则让新元素封装成节点,称为right,添加成功,返回true - 不为null,继续和right的节点进行比较,尝试将元素添加为right的left/right子树 - 小于,同理
增加元素需要先判断root是否为null
为null，将元素封装成根结点，返回true；
非null，和root进行比较，这是为了判断新元素是添加左子树还是右子树，但不一定添加成功
和root相等，那么添加失败，返回false，结束
大于root，尝试添加为root的右子树，判断right是否为null；
为null，将新元素封装成节点，成为右子树right，添加完成，返回true；
不为null，和right节点进行比较，尝试将该元素添加为right的left/right子树（这里递归就出现了）
小于root，尝试添加为root的左子树，判断left是否为null；
为null，将新元素封装成节点，成为左子树left，添加完成，返回true；
不为null，和left节点进行比较，尝试将该元素添加为left的left/right子树（这里递归就出现了）
思路理清了，那我们就开始写代码：
//添加元素 public boolean add(E e){ //判断root是否为null，为null，成为根节点 if (root==null) { root = new Node(e); return true; } //root不为null，添加 return root.append(e); }
Node内的添加方法：
//向某个节点上添加给定的元素,尝试让新元素称为其左/右子树 public boolean append(E e) { if (e.compareTo(ele) == 0) { return false; } else if (e.compareTo(ele) < 0) { if (left == null) { left = new Node(e); return true; } return left.append(e); } else { if (right == null) { right = new Node(e); return true; } return right.append(e); } }
查询元素
查询元素也需要先判断root是否为null
为null，树中没有节点，返回null；
非null，判断root节点是否为需要查找的元素
相等，root节点就是需要的元素，返回root节点，结束；
大于ele，就到节点的right去查找相等节点，判断right节点是否存在
为null，说明查询的元素不在此树中，返回null
非null，判断right节点是不是要找的节点，往后一直重复上述操作，直到找到或找不到为止
小于ele，就到节点的left去查找相等节点，判断left节点是否存在
为null，说明查询的元素不在此树中，返回null
非null，判断left节点是不是要找的节点，往后一直重复上述操作，直到找到或找不到为止
用代码来写下这个过程：
//根据元素查询对应的节点对象 public Node get(E e){ //判断root是否为null if (root==null) return null; //root不为空,则判断root是否为目标节点 return root.isDestNode(e); }
Node内的查询：
//用于判断调用方法的节点是否为目标节点 public Node isDestNode(E e) { //判断e是否和当前节点的元素相等,若相等,说明为目标节点,返回当前节点即可 if (e.compareTo(ele)==0) return this; else if (e.compareTo(ele)>0){ //e大于当前节点,到right上继续查找 //若right为null,说明目标元素不存在树中,返回null if (right==null) return null; return right.isDestNode(e); }else { //e小于当前节点,到left上继续查找 if (left==null) return null; return left.isDestNode(e); } }
修改元素
修改其实很简单，首先是查找，查找到之后，直接将新的元素指向那个节点。
我们可以定义这个方法如下：
set(E ele, E newEle)
修改理论上是可行的，但是在修改的时候，会不会引起重新排序呢？这对整个树结构是有影响的，代码似乎也没有刚开始说的那么简单了，重新排序对性能也有影响，所以二叉树可不提供修改方法。
删除元素
这要看删的是谁，如果删除的是叶子结点，那直接删了就好，不需要做什么判断，也不存在排序问题。一旦删除的是中间的节点，看下图：
假如删的是2或者6，这时候就要考虑谁上去的问题了。
所以删除分为三种情况：
删除叶子结点：将其父节点指向它的引用置为null；
删除有一棵子树的节点：将其父节点的指向变更为被删除的节点的子节点；
删除有两颗子树的节点：让被删除节点的前驱节点或者后继节点上来替换此节点；
前驱节点和后继节点是指升序排列后，删除节点的前一个元素叫做前驱节点，删除节点的后一个元素叫做后继节点
代码写起来会非常复杂，体验很差，所以就不写了，理解了就行，有兴趣的同学可自行尝试。
遍历二叉树
遍历的方式分为三种：
先序遍历：根 左 右
中序遍历：左 根 右
后序遍历：左 右 根
什么意思呢？我们根据一棵树来说：
先序遍历：4，2，1，3，6，5，7（即先根，后左，再右）
中序遍历：1，2，3，4，5，6，7（即先左，后根，再右，也叫升序排列）
后序遍历：1，3，2，5，7，6 ，4（即先左，后右，再根）
重写toString
目的是为了实现输出引用，将二叉树中的元素遍历，并以此格式输出：[1,2,3,4,5,6,7]输出，没有节点，返回[]。
//重写toString @Override public String toString() { //判断root是否为null,为null,返回"[]" if (root==null) return "[]"; //进行中序遍历 StringBuilder builder = new StringBuilder("["); return root.middleOrder(builder).replace(builder.length()-1,builder.length(),"]").toString();
Node内的方法：
public StringBuilder middleOrder(StringBuilder builder) { //左 if (left!=null){ left.middleOrder(builder); } //取根的值 builder.append(ele).append(","); //取右 if (right!=null){ right.middleOrder(builder); } //以上三步操作结束,得到遍历树后的元素拼接结果，将最后的逗号替换为] return builder; }
中序遍历这里有个递归，我们要明白的是，最终所有的代码都要取到根的值，这个节点是相对的，每个节点都会是这个根，这样才能拼接出字符串。大家可以动手尝试下其他遍历方式的写法，这里不再赘述。
二叉排序树的极端情况
这就是失衡二叉树，失衡二叉树是不希望存在的，因为它失去了二叉树本身的优势特点，这种状态和单向链表一样，单向链表的效率如何，想必大家都是知道的。
所以在设计数据结构的时候，已经考虑了这种情况，出现了两种新的数据结构，他们都基于二叉排序树，保留了其优势，又避免了这个缺点。
他们是平衡二叉树和红黑树。
