java 实现二叉查找树的 插入、删除、查找、深搜和广搜

树的节点类：

package basic;import basic.node;import java.util.Queue;import java.util.LinkedList;import java.util.Stack;public class Main {private node firstNode;public Main(node first){this.firstNode = first;}/** * 插入操作 * @param newOne * @return */public boolean insert(node newOne){node now = this.firstNode;while(true){if(now.getNum() < newOne.getNum()){if(null == now.getRight()){now.setRight(newOne);return true;}else{now = now.getRight();continue;}}else if(now.getNum() > newOne.getNum()){if(null == now.getLeft()){now.setLeft(newOne);return true;}else{now = now.getLeft();continue;}}else{return false;}}}/** * 删除操作；根据num删除相同num的值 * @param num * @return */public boolean delete(int num){node now = this.firstNode;while(true){if(null == now){return false;}if(now.getNum() < num){if(num == now.getRight().getNum()){now.setRight(this.deleteNode(now.getRight()));return true;}else{now = now.getRight();}continue;}else if(now.getNum() > num){if(num == now.getLeft().getNum()){now.setLeft(this.deleteNode(now.getLeft()));return true;}else{now = now.getLeft();}continue;}else if(now.getNum() == num){now = this.rightTreeHandle(now.getRight());return true;}}}/** * 删除形参节点，根据形参节点的子节点情况返回相应的值 * @param one * @return */private node deleteNode(node one){if(null == one.getLeft() && null == one.getRight()){//如果形参节点的左右节点均为null，则返回nullreturn null;}else if(null != one.getLeft() && null != one.getRight()){//如果形参节点的左右节点均不为null，则该节点右子树的最左叶子节点来替代当前节点node temp = this.rightTreeHandle(one.getRight());temp.setRight(one.getRight());temp.setLeft(one.getLeft());return temp;}else if(null != one.getLeft()){//如果形参节点的左子节点不为空，则返回形参节点的左子节点return one.getLeft();}else{//如果形参节点的右子节点不为空，则返回形参节点的右子节点return one.getRight();}}/** * 处理形参节点的子树 * 将形参节点子树的最左叶子节点返回，并且若该节点存在右子节点则将其右子节点替换到该节点的位置 * @param one * @return */private node rightTreeHandle(node one){if(null == one.getLeft()){return one;}else{node temp;while(true){if(null == one.getLeft().getLeft()){temp = one.getLeft();if(null != one.getLeft().getRight()){//如果该左子节点的右子节点不为空，则将该左子节点的右子节点挂到当前节点的左子节点位置上one.setLeft(one.getLeft().getRight());}return temp;}else{one = one.getLeft();continue;}}}}/** * 搜索对应num的节点 * @param num * @return */public node select(int num){node now = this.firstNode;while(true){if(null == now){return null;}if(now.getNum() == num){return now;}else if(now.getNum() < num){now = now.getRight();}else if(now.getNum() > num){now = now.getLeft();}}}/** * 广度优先遍历 */public void BreadthErgodic(){Queue<node> queue = new LinkedList<node>();node temp;queue.offer(this.firstNode);while(!queue.isEmpty()){//Queue接口本身没有生命isEmpty方法，但是这个对象可以使用isEmpty方法，这说明用接口声明一个变量可以用来引用实现了该接口的类，并使用类中的方法temp = queue.poll();if(null == temp){System.out.println("null");continue;}queue.offer(temp.getLeft());queue.offer(temp.getRight());System.out.println(temp.getNum()+"\t"+temp.getName());}}/** * 深度优先遍历 */public void DeepErgodic(){Stack<node> stack = new Stack<node>();node temp;stack.push(this.firstNode);while(!stack.isEmpty()){temp = stack.pop();if(null == temp){System.out.println("null");continue;}stack.push(temp.getLeft());stack.push(temp.getRight());System.out.println(temp.getNum()+"\t"+temp.getName());}}public static void main(String[] args) {// TODO Auto-generated method stubString names[] = {"aaaaa","bbbbb","cccc","dddd","eeeee","ffffff","gggggg","hhhhhhh","iiiii","jjjjj","kkkkk"};int num[] = {24,12,40,10,18,13,16,32,46,20,52};node first = new node(num[0],names[0]);Main main = new Main(first);int i = 1 ;node temp ;//生成查找树for(;i<11;i++){temp = new node(num[i],names[i]);if(main.insert(temp)){System.out.println("success");}else{System.out.println("Error");}}System.out.println();main.BreadthErgodic();//temp = main.select(11);//System.out.println(temp.getName());if(main.delete(12)){System.out.println("delete success");}System.out.println();main.BreadthErgodic();System.out.println();main.DeepErgodic();return;}}