Java二叉树查询原理深入分析讲解

public class BinarySearchTree { Node root; //定义根节点 //结点插入方法 public void insert(int value) { if (root == null) { //1.如果树是空树，插入节点就直接放入到根结点 root = new Node(value); } else { //如果树不是空树，则插入的数字于根结点的数字进行比较 //2.如果插入的值小于于结点的数字，则往左子树插入 Node node = root; //声明一个游标结点，开始指向根节点 while (true) { //并且再次和待插入的执行左子结点进行比较，直到找到插入的位置 if (value < node.value) { //如果插入的值小于于结点的数字，则往左子树插入 //2.1如果左子结点没有元素就插入到左子结点中 if (node.left == null) { node.left = new Node(value); break; //如果找到插入的位置，则跳出while循环 } else { //如果左子结点有元素，就可以设计一个引用(游标)指向左子节点，并且再次和待插入的执行左子结点进行比较，直到找到插入的位置 //游标指向左子节点 node = node.left; } } else { //如果插入的值大于结点的数字，则往右子树插入 //判断右子结点是否存在值，如果不存在则直接插入 if (node.right == null) { node.right = new Node(value); break; } else { //判断右子结点是否存在值，如果存在则通过一个引用指向右子结点继续和待插入的值进行比较，直到找到插入的位置 //游标指向右子节点 node = node.right; } } } } } //定义左右结点常量 public static final int LEFT = 0; //左子节点 public static final int RIGHT = 1; //右子节点 //结点查找方法 public void deleteNode(int value) { //定义游标从根节点开始查询 Node node = root; //定义目标结点 Node target = null; //定义目标结点的父类结点 Node parent = null; //目标结点的类型为，左子节点或者右子节点 int nodeType = 0; //0代表左子节点 1代表右子节点 while (node != null) { //游标不为空，如果为空则没有子节点，无法删除 if (node.value == value) { //如果目标结点的值和需要删除结点的值相同 //找到结点 target = node; break; } else if (value < node.value) { //如果值不同，则判断目标结点值是否小于node结点 //保存父类结点 parent = node; //游标指向左子节点 node = node.left; nodeType = LEFT; } else { //如果值不同，且目标结点值大于node结点 //保存父类结点 parent = node; //游标指向右子节点 node = node.right; nodeType = RIGHT; } } //如果没找到需要删除的目标结点 if (target==null){ System.out.println(“没有找到要删除的结点”); return; } //删除结点的三种情况 if (target.left == null && target.right == null) { //情况1：待删除的结点没有子结点 if (parent==null){ //删除的结点没有子结点 //将root设置为null即可 root=null; return; } //判断目标的结点是左子节点还是右子节点 if (nodeType == LEFT) { //将父类的左子节点设置为null parent.left = null; } else { //将父类的右子节点设置为null parent.right = null; } } else if (target.left != null && target.right != null) { //情况2：待删除的结点有2个子节点 //两个子节点，从target右子树查找最小的值 Node min=target.right; //遍历左子树 while (min.left!=null){ min = min.left; } //将最小的结点进行删除 deleteNode(min.value); //将待删除的结点替换成最小的结点的值 target.value= min.value; }else { //情况3：待删除的结点有1个子节点 //删除结点是根节点 if (parent==null){ if (target.left!=null){ //判断是左子节点还是右子节点有值 root=target.left; //根节点=目标左子结点 }else { root=target.right; //根节点=目标右子结点 } } //只有一个子节点 if (nodeType==LEFT){ //如果是左子节点 if (target.left!=null){ //将父类的左子节点，指向待删除结点的左子节点 parent.left=target.left; }else { //如果是右子节点 //将父类的左子节点，指向待删除结点的右子节点 parent.left=target.right; } }else { if (target.right!=null){ //将父类的右子节点，指向待删除结点的左子节点 parent.right=target.left; }else { //如果是右子节点 //将父类的右子节点，指向待删除结点的右子节点 parent.right=target.right; } } } } //实现中序遍历 public void midTraversal(Node node) { if (node == null) { //进行判断结点不能为空，如果为空则退出 return; } else { //如果结点不为null，则执行下列遍历语句 //首先，遍历左节点 midTraversal(node.left); //打印根节点 System.out.print(node.value + “,”); //最后遍历右子结点 midTraversal(node.right); } } //创建一个结点类 public static class Node { int value; //存储值 Node left; //左子树 Node right; //右子树 // 带参构造方法，传入value赋值 public Node(int value) { this.value = value; } } }

package Algorithm; public class TestBST { public static void main(String[] args) { int[] arrs = {5, 2, 1, 4, 3, 9, 7, 6, 8}; //创建二叉查询树 BinarySearchTree tree = new BinarySearchTree(); //将数组中的元素构造成二叉查询树 for (int i = 0; i < arrs.length; i++) { tree.insert(arrs[i]); } //删除结点 tree.deleteNode(20); //中序遍历根结点 tree.midTraversal(tree.root); } }

您可能感兴趣的文章: java响应式编程之handle用法解析 JavaScrip如何安全使用Payment Request API详解 java中如何使用HttpClient调用接口 详解Java中的字节码增强技术 JavaScript正则表达式获取图片链接地址 java比较两个json文件的差异及说明 Java设计模式之享元模式 Java Handler同步屏障浅析讲解