(四).二叉查询树
1.二叉查找树的插入原理
二叉树的插入原理:
假如说是空树。
1.那么插入的结点直接放到根节点的位置
假如说插入的数比父节点要小。
1.如果左字节点没有元素，那么就插入左子树。 2.如果左子结点有元素。那么就设计一个引用执行左结点，
并且再次和待插入的结点进行比较，直到找到插入的位置。
如果插入的数比父节点要大。
1.如果右边不存在元素，那么就插入右子树。
2.如果右结点有元素那么 就引用一个执行右结点，并且再次和待插入的结点进行比较，直到找到插入的位置。
2.二叉查询树的顺序遍历:
使用树的中序遍历，即可达到二叉查询树的顺序遍历
3.二叉查询树的查找原理
1.提供一个你要查找的值。
2.假如说查找的值比结点大，那么就走右子树，假如说比结点小，那么就走左子树。
4.二叉查询树的删除原理
1.提供一个待删除结点的值，根据值从二叉树找到需要删除的值的结点。
2.找到待删除结点的父类结点，并且要根据待删除的点在父类的左右子树的位置，设置为null进行删除，
3.需要考虑结点的三种情况:
情况一：待删除的结点没有子结点 直接让父类结点的对应子结点的引用设置为null 情况二:待删除的结点有一个子结点 将待删除的父类结点对应的子结点的引用指向，待删除的结点的子结点即可。 情况三：待删除的结点有两个子结点 1.从左子树中找到最小的结点进行删除，并且将最大的结点的值覆盖到待删除结点。 2.从右子树找到最小的结点进行删除，并且将最小的结点替换到待删除的结点（需要将待删除的结点指向新创建的结点） 情况四:考虑删除的结点是根节点: 1.根结点没有子结点，直接将根节点指向null 2.根结点有一个子结点，直接将根节点指向子结点。 3.跟结点有两个子结点，可以从左子树中找到最大值删除结点，然后然后将最大值覆盖根节点。或则从右节点找到最小值和跟根节点进行替换（需要将跟结点指向新创建的结点，然后将新结点分别指向左右子树即可）
5.增删改查（全部代码）
import java.awt.*; public class TreeSelect { //创建树结点 public static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } //设置根结点； Node root; //构造查询二叉树 public void insert(int value) { //假如说根结点为空，那么直接把值给根节点 if (root == null) { root = new Node(value); } else { //声明一个游标结点，开始指向根节点 Node idex = root; while (true) { //假如说插入的值小于游标的值 if (value < idex.value) { //假如说游标左子结点没有值了,那么就把该值给游标的左边 if (idex.left == null) { idex.left = new Node(value); break; } else {//假如说游标左子节点有值的话，那么就把游标指向游标的左子节点 idex = idex.left; } } else { //如果游标右子节点没有值的话 if (idex.right == null) { idex.right = new Node(value); break; } else {//如果不为空，那么就游标指向游标的右节点 idex = idex.right; } } } } } //实现中序遍历 public void MidTraversal(Node node) { if (node == null) { return; } //遍历左结点 MidTraversal(node.left); //输出中结点 System.out.print(node.value + " "); //输出右结点 MidTraversal(node.right); } //二叉树的删除 public static int LEFT = 0; public static int RIGHT = 1; public void deleteNdde(int value) { //定义游标从根结点开始查询 Node idex = root; //定义目标结点. Node target = null; //定义目标结点的父类结点 Node parent = null; //定义目标结点的类型 int nodeType = 0; //0代表左子结点，1代表右子结点 //==========查值 while (idex != null) { //假如说游标的值等于删除的值 if (idex.value == value) { //找到了结点 target = idex; break; } else if (value < idex.value) {//假如说删除的值小于游标的值 //保存父节点 parent = idex; //将游标节点指向左子节点 idex = idex.left; nodeType = LEFT; } else { //保存父节点 parent = idex; //将游标节点指向右子节点 idex = idex.right; nodeType = RIGHT; } } if(target==null){ System.out.println("没有找到要删除的结点"); } //==========删除结点的三种情况 //情况一：没有子结点 if (target.left == null && target.right == null) { if(parent==null){ //假如跟结点 //直接将rroot为空 root=null; return; } //判断目标值的结点是左子节点还是右子节点 if (nodeType == LEFT) { //将父类的左子节点设置为null parent.left = null; } else { parent.right = null; } } else if (target.left != null && target.right != null) { //假如说有两个子结点 //从目标值的右子树方法中查找最小值的方法 Node min=target.right; //遍历左子树 while (min.left!=null){ min=min.left; } //将最小的结点进行删除 deleteNdde(min.value); //将待删除的结点与最小值进行替换 target.value=min.value; } else {//假如只有一个子结点的情况 if(parent==null){ //加入删除根节点 if(target.left!=null){ root=target.left; }else{ root=target.right; } return; } if (nodeType == LEFT) { if (target.left != null) { //将父类的子结点指向待删除结点的左子节点 parent.left = target.left; } else { //将父类的子节点指向待删除结点的右子结点 parent.left = target.right; } } else { if (target.left != null) { //将父类的子结点指向待删除结点的左子节点 parent.right = target.left; } else { //将父类的子节点指向待删除结点的右子结点 parent.right = target.right; } } } } }
import org.jetbrains.annotations.NotNull; import java.awt.event.KeyEvent; import java.awt.event.KeyListener; import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String []avgs){ int []arr=new int[]{5,2,1,4,3,9,7,6,8}; TreeSelect ts=new TreeSelect(); //将二叉树构造成查询二叉树 for(int i=0;i<arr.length;i++){ ts.insert(arr[i]); } ts.deleteNdde(11 ); //对查询二叉树进行遍历 ts.MidTraversal(ts.root); } }
