【一起来学数据结构java】——二叉搜索树一、概念二、二叉搜索树的方法
搜索插入删除
一、概念
二叉搜索树的左子树比根节点都小，右子树比根节点的值都大。它的每一个子树也是这个样子。
二叉搜索树中的元素不会重复
这样如果想要搜索某一个值的话，很方便去搜索。
二、二叉搜索树的方法 搜索先使用递归方法：
public Node Search_val(int val,Node node) {
if(root==null)
return null;
if(val==root.val)
return root;
else if(val>root.val)
return Search_val(val, node.right);
else {
return Search_val(val, node.left);
}
}
public Node Search(int val) {
return Search_val(val,root);
}
迭代方法：
public Node Search2(int val) {
if(root==null)
return null;
Node cur=root;
while(cur!=null) {
if(cur.val==val)
return cur;
else if(cur.val
插入
二叉树不会插入相同的数据，遇到相同的就会报错二叉树的插入只会插入到其二叉树的叶子节点上面。
下面是代码：
public Boolean Insert(int val) {
//如果二叉树中有该数据
if(Search2(val)!=null)
return false;
//如果root是null就直接插入
if(root==null) {
root=new Node(val);
return true;
}else {
Node cur=root;
Node parent=null;
//先找到要插入的位置
while(cur!=null) {
if(val>cur.val){
parent=cur;
cur=cur.right;
}else {
parent=cur;
cur=cur.left;
}
}
//val和parent的val比较哪个大
if(val>parent.val) {
parent.right=new Node(val);
return true;
}else {
parent.left=new Node(val);
return true;
}
}
删除
删除需要的步骤就麻烦了。
要分下面三种情况分析：
一、cur的左边为空
if(cur.left==null) {
if(cur==root) {
root=cur.right;
}else if(cur==parent.left)
parent.left=cur.right;
else if(cur==parent.right)
parent.right=cur.right;
二、cur的右侧为空
else if(cur.right==null) {
if(cur==root) {
root=cur.left;
}else if(cur==parent.left)
parent.left=cur.left;
else if(cur==parent.right)
parent.right=cur.left;
** 三、左右子树都不为空**
这个就麻烦了，左右子树都不是空。我们可以从左子树中找到最大的或者从右子树中找到最小的和cur替换，然后将找到的该值删掉即可
}else {//左右树都不是空的情况
//右子树的最小值
Node taNode=cur.right;
Node ptaNode=cur;
while(taNode.left!=null) {
ptaNode=taNode;
taNode=taNode.left;
}
cur.val=taNode.val;
//！！易错，这一点着重重要
if(ptaNode.left==taNode)
ptaNode.left=taNode.right;
else {
ptaNode.right=taNode.right;
}
但是，那个易错的一定要去注意。
总体代码：
public void remove(int val) {
if(root==null) return;
Node cur=root;
Node parent=null;
while(cur!=null) {
if(val>cur.val) {
parent=cur;
cur=cur.right;
}
else if(val 
