二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
结点的定义
package com.tree;
public class TreeNode {
private int data = 0;
private TreeNode Lchild;
private TreeNode Rchild;
public TreeNode() {
}
public TreeNode(int data, TreeNode lchild, TreeNode rchild) {
super();
this.data = data;
Lchild = lchild;
Rchild = rchild;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLchild() {
return Lchild;
}
public void setLchild(TreeNode lchild) {
Lchild = lchild;
}
public TreeNode getRchild() {
return Rchild;
}
public void setRchild(TreeNode rchild) {
Rchild = rchild;
}
}
二叉排序树的实现
package com.tree;
public class BinSearchTree {
private TreeNode root;
public BinSearchTree() {
this(null);
}
public BinSearchTree(TreeNode root) {
this.root = root;
}
public void makeEmpty()
{
root = null;
}
public boolean isEmpty()
{
return (root == null)?true:false;
}
/**
* 查找树中是否有元素value，如果有返回true
* @param value
* @return
*/
public boolean contains(int value)
{
return contains(value,root);
}
private boolean contains(int value,TreeNode node)
{
if(node == null)
{
return false;
}
if(value < node.getData())
{
return contains(value,node.getLchild());
}
else if(value > node.getData())
{
return contains(value,node.getRchild());
}else
{
return true;
}
}
/**
* 查找二叉树中的最小值
* @return
*/
public int findMin()
{
return findMin(root).getData();
}
private TreeNode findMin(TreeNode node)
{
if(node == null)
{
return null;
}else if(node.getLchild() == null)
{
return node;
}
return findMin(node.getLchild());
}
/**
* 查找二叉树中的最大值
* @return
*/
public int findMax()
{
return findMax(root).getData();
}
private TreeNode findMax(TreeNode node)
{
if(node == null)
{
return null;
}
else if(node.getRchild() == null)
{
return node;
}
return findMax(node.getRchild());
}
/**
* 插入元素
* @param value
*/
public void insert(int value)
{
root = insert(value,root);
}
private TreeNode insert(int value,TreeNode node)
{
if(node == null)
{
return new TreeNode(value,null,null);
}
if(value < node.getData()){
node.setLchild(insert(value,node.getLchild()));
}else if(value > node.getData())
{
node.setRchild(insert(value,node.getRchild()));
}
return node;
}
/**
* 删除节点
* @param value
*/
public void remove(int value)
{
if(!contains(value))
{
return;
}
root = remove(value,root);
}
private TreeNode remove(int value,TreeNode node)
{
if(node == null)
{
return null;
}
if(value < node.getData())
{
node.setLchild(remove(value,node.getLchild()));
}else if(value > node.getData())
{
node.setRchild(insert(value,node.getRchild()));
}else if(node.getLchild() != null && node.getRchild() != null){
//如果当前节点有两个孩子节点，则将当前节点左子树中的最小值替换到当前节点
TreeNode temp = findMin(node.getRchild());
node.setData(temp.getData());
//将右子树的最小值删除
node.setRchild(remove(temp.getData(),node.getRchild()));
}else
{
//如果被删除节点只有一个儿子节点 或是叶子节点
node = (node.getLchild() != null) ? node.getLchild():node.getRchild();
}
return node;
}
public void inOrder()
{
inOrder(root);
}
private void inOrder(TreeNode node)
{
if(node != null)
{
inOrder(node.getLchild());
System.out.println(node.getData());
inOrder(node.getRchild());
}
}
}
测试
package com.tree;
public class Demo {
public static void main(String[] args) {
BinSearchTree tree = new BinSearchTree();
tree.insert(5);
tree.insert(7);
tree.insert(3);
tree.insert(1);
tree.insert(9);
tree.insert(6);
tree.insert(4);
System.out.println("最小值:"+tree.findMin());
System.out.println("最大值:"+tree.findMax());
System.out.println("查找元素9是否存在:"+tree.contains(9));
System.out.println("查找元素8是否存在:"+tree.contains(8));
System.out.println("遍历二叉树");
tree.inOrder();
}
}
