二叉搜索树的性质：所有左子树节点的元素小于根节点数据，所有右子树节点的数据大于根节点数据。
- 一个节点的左子树只能包含键值小于该节点键值的节点
- 一个节点的右子树只能包含键值大于该节点键值的节点
- 左子树和右子树也都必须是二叉搜索树
- 寻找二叉搜索树中的最大值
public static Node findMax(Node root)
{
if (root==null)
{
throw new RuntimeException("Invalid input");
}
if (root.right!=null)
{
return findMax(root.right);
}
else
return root;
}
- 在二叉搜索树中插入元素
public static Node insert(Node root,int data)
{
if (root==null)
{
root=new Node(data);
return root;
}
if (data<root.data)
{
root.left=insert(root.left,data);
}
else if (data>root.data)
{
root.right=insert(root.right,data);
}
return root;
}
- 在二叉搜索树中删除元素
public static Node delete(Node root,int data)
{
if (root==null)
{
throw new RuntimeException("No such element");
}
if (data<root.data)
{
root.left=delete(root.left,data);
}
else if (data>root.data)
{
root.right=delete(root.right,data);
}
//如果要删除的是当前元素
else
{
//如果当前元素有左子树而且有右子树
if (root.left!=null&&root.right!=null)
{
//找到左子树中的最大值
Node temp=findMax(root.left);
//当前元素的值替换为左子树中的最大值
root.data=temp.data;
//删除左子树中的最大值
root.left=delete(root.left,temp.data);
}
//如果当前元素只有左子树，直接返回左子树
else if (root.left!=null)
{
root=root.left;
}
//如果当前元素只有右子树，直接返回右子树
else if (root.right!=null)
{
root=root.right;
}
//如果当前元素没有左子树而且没有右子树，直接删除当前元素
else
return null;
}
return root;
}
