1. 插入节点
插入节点，在满足二叉搜索树的性质情况下我们可以列出以下几种情况：
- 如果树是空树，则之间插入即可。
- 如果树不是空树，查找顺序确定插入的位置从而插入新节点。
(1)树是空树
我们直接插入一个新节点:
if(root == null) { TreeNode node = new TreeNode(key);//新节点node root == node;//把新节点node赋值给root return;//结束程序 }
以上代码中，key是我们要插入的值，因此我们要new一个新节点node来存放key值。然后直接将新节点node赋值给根节点root即可。
(2)树不是空树
按照顺序查找可以插入的位置，插入新节点。插入前的查找插入位置，跟上方的 findNode 方法是一样的，因此我们需要了解到的思想是如何进行插入这个环节。
在插入节点的操作时，我们要用一个 parent 来代表根节点的双亲结点，因为当根节点往后遍历走到空时我们无法确认要插入到哪个位置，这时可以使用 parent 这个结点作为根节点来插入新节点。
TreeNode parent = root;//根节点的双亲结点 TreeNode cur = root; //根节点的代表结点
当然，我们得使用一个根节点的代表结点 cur 来进行遍历。如何判断插入的位置是 parent 的左子树还是右子树呢？我们可以通过 parent 的 val 值与被插入值 key 进行比较，如果 key 小于 parent 的 val 值则插入到 parent 的左子树否则插入到右子树。因此，我们可以写出以下代码：
TreeNode node = new TreeNode(key);//创建一个新结点node存放key值 if(parent.val < key) { parent.right = node;//key值大于parent的val值，放在右子树 }else { parent.left = node;//否则放在左子树 }
把上述所有的代码综合起来，我们就能组成以下完整的代码。插入节点的方法名我定义为insertNode，当然你也可以根据自己的设计思想设定方法名以及变量名。
方法内的流程为：1.判断树是否为空，为空直接把插入的结点赋值给根节点。2.找到要插入的位置。3.插入到相应的位置。
//插入节点 public void insertNode(int val) { if (root == null) { root = new TreeNode(key);//新节点就是val值所在的节点 return;//结束程序 } TreeNode cur = root;//一个cur代替root根节点 TreeNode parent = null;//根节点的上一个节点 while(cur != null) { if (cur.val == key) { return;//如果这个节点存在直接结束程序 }else if (cur.val > key) { parent = cur; cur = cur.left;//这个值小于根节点则往左子树走 }else { parent = cur; cur = cur.right;//这个值大于根节点则往右子树走 } } TreeNode node = new TreeNode(key);//使key值成为一个节点 if (key > parent.val) { parent.right = node;//如果key值大于根节点值则把key值所在节点放在根节点右子树 }else { parent.left = node;//否则放在左子树 } } }
