java 实现二叉查找树的 安插、删除、查找、深搜和广搜
java 实现二叉查找树的 插入、删除、查找、深搜和广搜
查找树的操纵类:
树的节点类:
package basic; public class node { private int num; public String name; private node left; private node right; public node(int num,String name){ this.num = num; this.name = name; this.left = null; this.right = null; } /** * 获取房钱节点的左子节点 * @return */ public node getLeft(){ return this.left; } /** * 设置左子节点的值 * @param one */ public void setLeft(node one){ this.left = one; } /** * 获取右子节点的值 * @return */ public node getRight(){ return this.right; } /** * 设置右子节点的值 * @param one */ public void setRight(node one){ this.right = one; } /** * 获取当前节点编号 * @return */ public int getNum(){ return this.num; } /** * 获取当前节点名称 * @return */ public String getName(){ return this.name; } }
查找树的操纵类:
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,则返回null return 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 stub String 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; } }