Java数据结构——二叉树 增加、删除、查询

//二叉树系统
public class BinarySystem {
	public static void main(String[] args) {
		BinaryDomain root = null;    //定义头结点
		new BinaryAction().manage(root);
	}
}

public class BinaryDomain {
	private int value;		//二叉树值
	BinaryDomain left;	//左结点
	BinaryDomain right; //右结点
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public BinaryDomain() {
		super();
		// TODO Auto-generated constructor stub
	}
	public BinaryDomain(int value) {
		super();
		this.value = value;
	}
}

public interface BinaryBean {
	public void manage(BinaryDomain root);		//二叉树管理
	public BinaryDomain add(BinaryDomain root);		//二叉树增加
	public BinaryDomain delete(BinaryDomain root);	//二叉树删除
	public void query(BinaryDomain root);	//二叉树查询
	public void update(BinaryDomain root);	//二叉树修改
}

import java.util.Scanner;

public class BinaryAction implements BinaryBean{

	private Scanner input = new Scanner(System.in);
	@Override
	public void manage(BinaryDomain root) {
		while (true) {
			System.out.println("①增加   ②删除   ③查询   ④修改   ⑤返回");
			int select = input.nextInt();
			if (select == 1) {
				root = add(root);
			} else if (select == 2) {
				root = delete(root);
			} else if (select == 3) {
				query(root);
			} else if (select == 4) {
				update(root);
			} else {
				break;
			}
		}
	}

	//增加
	@Override
	public BinaryDomain add(BinaryDomain root) {
		System.out.println("请输入需要增加的值: ");
		int value = input.nextInt();
		if (value < 0) {
			System.out.println("输入的值不合法");
		} else {
			BinaryDomain binary = new BinaryDomain(value);	//将值存入对象
			if (root == null) {	//头为空 
				root = binary;	//将值给头
				System.out.println("二叉树的头结点增加成功");
			} else {
				BinaryDomain temp = root;	//将头保护起来
				while (temp != null) {
					//小左大右
					if (binary.getValue() > temp.getValue()) {
						//要增加的值大于当前头的值
						if (temp.right == null) {
							temp.right = binary;
							System.out.println("添加右子树值成功");
							break;
						} else {
							temp = temp.right;
						}
					} else if (binary.getValue() < temp.getValue()){
						//要增加的值小于当前头的值
						if (temp.left == null) {
							temp.left = binary;
							System.out.println("添加左子树值成功");
							break;
						} else {
							temp = temp.left;
						}
					} else {
						//要增加的值等于当前头的值
						System.out.println("要增加的数值已存在，增加数据失败");
						break;
					}
				}
			}
		}
		return root;
	}
	
	//删除
	@Override
	public BinaryDomain delete(BinaryDomain root) {
		BinaryDomain temp = root;	//保护头结点
		BinaryDomain tempPre = null;	//要删除的前一个结点
		BinaryDomain del = null;	//记录要删除的结点
		System.out.println("请输入需要删除的值: ");
		int value = input.nextInt();
		while (temp != null) {
			if (temp.getValue() == value) {
				//当前结点值 == 要删除的值
				del = temp;		//记录要删除的结点
				break;
			} else if (temp.getValue() > value) {
				//当前结点值 > 要删除的值 往左移至下一个
				tempPre = temp;	//记录要删除结点的前一个结点
				temp = temp.left;
			} else {
				//当前结点值 < 要删除的值	往右移至下一个
				tempPre = temp;
				temp = temp.right;
			}
		}
		//判断要删除的结点是否为头结点
		if (del != null && tempPre == null) {
			System.out.println("要删除的为头结点");
			if (del.left == null && del.right == null) {
				//头结点 无左无右
				root = null;
				System.out.println("删除 无左无右 头结点成功");
			} else if (del.left != null && del.right == null) {
				//要删除的头结点 有左无右
				root = del.left;
				System.out.println("删除 有左无右 头结点成功");
			} else if (del.left == null && del.right != null) {
				//要删除的头结点 无左有右
				root = del.right;
				System.out.println("删除 无左有右 头结点成功");
			} else {
				//要删除的头结点 有左有右
				System.out.println("要删除的头结点有左有右: ①上移左边的最右边结点值   ②上移右边的最左边结点值");
				int option = input.nextInt();
				if (option == 1) {
					//移左边的最右边结点的值
					BinaryDomain delLeft = del.left;	//用一个对象指向要删除结点的左边
					if (delLeft.right == null && delLeft.left == null) {
						//如果要删除的结点的左边结点没有子结点，则把要删除的结点值等于delLeft值，需要删除结点的左结点为空
						del.setValue(delLeft.getValue());
						del.left = null;
						System.out.println("删除 有左有右 头结点成功，头结点的左子树下 无子树");
					} else if (delLeft.right == null && delLeft.left != null) {
						//要删除的结点的左边结点 有左子树无右子树
						del.setValue(delLeft.getValue());
						del.left = delLeft.left;
						System.out.println("删除 有左有右 头结点成功，头结点的左子树下 有左子树无右子树");
					} else {
						//要删除的结点的左边结点有右子树
						BinaryDomain movePre = null; //记录删除结点左边结点的需要移走的最右边的结点的父结点
						while (delLeft.right != null) {
							movePre = delLeft;
							delLeft = delLeft.right;
						}
						del.setValue(delLeft.getValue());
						movePre.right = delLeft.left;
						System.out.println("删除 有左有右 头结点成功，头结点的左子树下 有右子树 需要移动");
					}
				} else {
					//移右边的最左边结点值
					BinaryDomain delRight = del.right;	//用一个对象指向要删除结点的右边
					if (delRight.right == null && delRight.left == null) {
						//如果要删除的结点的右边结点没有子结点，则把要删除的结点值等于delRight值，需要删除结点的右结点为空
						del.setValue(delRight.getValue());
						del.right = null;
						System.out.println("删除 有左有右 头结点成功，头结点的右子树下 无子树");
					} else if (delRight.right != null && delRight.left == null) {
						//要删除的结点的右边结点 有右子树无左子树
						del.setValue(delRight.getValue());
						del.right = delRight.right;
						System.out.println("删除 有左有右 头结点成功，头结点的右子树下 有右子树无左子树");
					} else {
						//要删除的结点的右边结点有左子树
						BinaryDomain movePre = null;	//记录删除结点右边结点的需要移走的最左边的结点的父结点
						while (delRight.left != null) {
							movePre = delRight;
							delRight = delRight.left;
							System.out.println("删除 有左有右 头结点成功，头结点的右子树下 有左子树 需要移动");
						}
					}
				}
			}
		} else {
			//要删除的不是头结点
			if (del.left == null && del.right == null) {
				//要删除的结点无左无右 为叶子结点
				System.out.println("需要删除的为叶子结点");
				if (del.getValue() > tempPre.getValue()) {
					//要删除的值大于父结点的值 删除的为右叶子结点
					tempPre.right = null;
					System.out.println("删除非根结点下的右叶子结点成功");
				} else {
					//要删除的值小于父结点的值 删除的为左叶子结点
					temp.left = null;
					System.out.println("删除非根结点下的左叶子结点成功");
				}
			} else if (del.left == null && del.right != null) {
				//要删除的结点无左有右
				if (del.getValue() > tempPre.getValue()) {
					//要删除的值大于父结点的值 要删除的为父结点下的右子树
					tempPre.right = del.right;
					System.out.println("删除非根结点下的右子树成功，且该右子树下 有右子树无左子树");
				} else {
					//要删除的值小于父结点的值 要删除的为父结点下的左子树
					tempPre.left = del.right;
					System.out.println("删除非根结点下的左子树成功，且该左子树下 有右子树无左子树");
				}
			} else if (del.left != null && del.right == null) {
				//要删除的结点有左无右
				if (del.getValue() > tempPre.getValue()) {
					//要删除的值大于父结点的值 要删除的为父结点下的右子树
					tempPre.right = del.left;
					System.out.println("删除非根结点下的右子树成功，且该右子树下 有左子树无右子树");
				} else {
					//要删除的值小于父结点的值 要删除的为父结点下的左子树
					tempPre.left = del.left;
					System.out.println("删除非根结点下的左子树成功，且该左子树下 有左子树无右子树");
				}
			}else {
				//要删除的结点有左有右
				System.out.println("要删除的结点有左有右: ①上移左边的最右边结点值   ②上移右边的最左边结点值");
				int option = input.nextInt();
				if (option == 1) {
					//移左边的最右边结点
					BinaryDomain delLeft = del.left;		//定义对象指向要删除结点的左边结点
					if (delLeft.right == null && delLeft.left == null) {
						//要删除结点的左边结点 无左子树无右子树
						del.setValue(delLeft.getValue());
						del.left = null;
						System.out.println("删除非根结点下左子树成功，且该左子树下 无左子树无右子树");
					} else if (delLeft.right == null && delLeft.left != null) {
						//要删除结点的左边结点 有左子树无右子树
						del.setValue(delLeft.getValue());
						del.left = delLeft.left;
						System.out.println("删除非根结点下左子树成功，且该左子树下 有左子树无右子树");
					} else {
						//要删除结点的左边结点 无左子树有右子树
						BinaryDomain movePre = null;	//记录删除结点左边结点的需要移走的最右边的结点的父结点
						while (delLeft.right != null) {
							movePre = delLeft;
							delLeft = delLeft.right;
						}
						del.setValue(delLeft.getValue());
						movePre.right = delLeft.left;
						System.out.println("删除非根结点下左子树成功，且该左子树下 有右子树 需要移动");
					}
				} else {
					//移右边的最左边结点
					BinaryDomain delRight = del.right;	//定义对象指向要删除结点的右结点
					if (delRight.right == null && delRight.left == null) {
						//要删除结点的右子树下无子树
						del.setValue(delRight.getValue());
						del.right = null;
						System.out.println("删除非根结点下右子树成功，且该右子树下 无子树");
					} else if (delRight.right != null && delRight.left == null) {
						//要删除结点的右子树下有右子树无左子树
						del.setValue(delRight.getValue());
						del.right = delRight.right;
						System.out.println("删除非根结点下右子树成功，且该右子树下 无左子树有右子树");
					} else {
						//要删除结点的右子树下有左子树
						BinaryDomain movePre = null;	//记录删除结点右边结点的需要移走的最左边的结点的父结点
						while (delRight.left != null) {
							movePre = delRight;
							delRight = delRight.left;
						}
						del.setValue(delRight.getValue());
						movePre.left = del.right;
						System.out.println("删除非根结点下右子树成功，且该右子树下 有左子树 需要移动");
					}
				}
			}
		}
		return root;
	}

	//查询
	@Override
	public void query(BinaryDomain root) {
		System.out.println("①先序查询   ②中序查询   ③后序查询");
		int select = input.nextInt();
		if (select == 1) {
			//先序查询  根 左 右
			preorder(root);
		} else if (select == 2) {
			//中序查询  左 根 右
			inorder(root);
		} else {
			//后序查询  左  右 根
			epilogue(root);
		}
	}

	//先序查询  根 左 右
	public void preorder(BinaryDomain root) {
		BinaryDomain temp = root;
		if (temp != null) {
			System.out.println("先序查询为: "+temp.getValue());	//根
			preorder(temp.left);	//左
			preorder(temp.right);	//右
		}
	}

	//中序查询  左 根 右
	public void inorder (BinaryDomain root) {
		BinaryDomain temp = root;
		if (temp != null) {
			inorder(temp.left);	//左
			System.out.println("中序查询为: "+temp.getValue());	//根
			inorder(temp.right);	//右
		}
	}

	//后序查询  左  右 根
	public void epilogue (BinaryDomain root) {
		BinaryDomain temp = root;
		if (temp != null) {
			epilogue (temp.left);	//左
			epilogue (temp.right);	//右
			System.out.println("后序查询为: "+temp.getValue());	//根
		}
	}
	
	//修改
	@Override
	public void update(BinaryDomain root) {
		System.out.println("请输入需要修改的数据元素: ");
		int update = input.nextInt();
	}
}

修改没写了 ，很麻烦 ，如有需要留言，告诉你具体实现思路。。