前言需要介绍
给你一个数列(7,3, 10,12,5,1,9)，要求可能高效的实现对数据的查问和增加。
依据后面咱们学习了数据结构：数组、链表、树等等来看看思路吧
➢应用数组
- [数组未排序]长处:间接在数组尾增加，速度快。
- [数组未排序]毛病:查找速度慢.
- [数组排序]长处:能够应用二分查找，查找速度快。
- [数组排序]毛病:为了保障数组有序，在增加新数据时，找到插入地位后，前面的数据需整体挪动，速度慢
➢应用链式存储链表
- 毛病:不论链表是否有序，查找速度都慢
- 长处:增加数据速度比数组快，不须要数据整体挪动。
➢应用二叉排序树
那么二叉排序树是什么呢？
一、什么是二叉排序树
根本介绍
二叉排序树: BST: (Binary Sort(Search) Tree)
对于二叉排序树的任何一个非叶子节点
要求：左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。
特地阐明:如果有雷同的值，能够将该节点放在左子节点或右子节点
如果咱们在以后的数列中插入：2 ，会怎么样呢？
二、通过示例意识二叉排序树
二叉排序树的创立和遍历
创立数组为Array(7,3, 10, 12,5, 1,9)，对应的二叉排序树
并应用中序遍历对应的二叉排序树测验
思路剖析
- 判断左子节点的值是否比以后节点的值小
- 否则判断右子节点的值比以后节点的值大
- 递归判断是否合乎左子节点、右子节点的条件
- 中序遍历的特点：先遍历左子树，再输入父节点，再遍历右子树
代码逻辑
//创立节点信息class Node{ int value; Node left; Node right; public Node(int value) { this.value = value; } //增加节点办法 //递归形式增加节点，要满足二叉排序树的要求 //要求是：`左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。` public void add(Node node) { if (node == null) { return; } //判断传入的节点的值，和以后节点值的关系 //增加的节点小于以后节点 if (node.value < this.value) { if (this.left == null) { this.left = node; } else { this.left.add(node); } } else {//增加的节点大于以后节点 if (this.right == null) { this.right = node; } else { this.right.add(node); } } } @Override public String toString() { return "Node{" +"value=" + value +'}'; } //中序遍历 public void infixOrder(){ if(this.left != null){ this.left.infixOrder(); } System.out.println(this); if(this.right != null){ this.right.infixOrder(); } }}//二叉排序树class BinarySortTree{ private Node root; //增加节点的办法 public void add(Node node){ if(root == null){ root = node; }else{ root.add(node); } } //调用中序遍历的办法 public void infixOrder(){ if(root == null){ System.out.println("以后二叉排序根节点为空，无奈遍历"); return; }else{ root.infixOrder(); } }}public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9}; BinarySortTree binarySortTree = new BinarySortTree( ); //循环的增加结点到二叉排序树 for(int i = 0; i< arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder();}运行后果如下：Node{value=1}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}Node{value=12}二叉排序树的删除
二叉排序树的删除状况有些简单，须要思考以下状况
1.删除叶子节点：2、5、9、12
2.删除有一颗子树的节点：1
3.删除有两颗子树的节点：7、3、10
图解二叉排序树删除节点三种状况进行思路剖析
第一种状况：删除叶子节点：2、5、9、12
第二种状况：删除有一颗子树的节点：1
第三种状况：删除有两颗子树的节点：7、3、10
依照图解思路咱们须要给Node类增加一个办法返回心愿删除的节点信息
- 判断查找的Value是否等于以后节点的值，返回值
- 判断查找的Value是否小于以后节点的值，递归往左子树找
- 判断查找的Value是否大于以后节点的值，递归往右子树找
/** * @param value 心愿删除的结点的值 * @return如果找到返回该结点，否则返回null */public Node search(int value) { if(value == this.value) { //找到就是该结点 return this; } else if(value < this.value) {//如果查找的值小于以后结点，向左子树递归查找 //如果左子结点为空 if(this.left == null) { return null; } return this.left.search(value); } else { //如果查找的值不小于以后结点，向右子树递归查找 if(this.right == null) { return null; } return this.right. search(value); }}依照图解思路咱们须要给Node类增加一个办法返回删除节点的父节点信息
- 判断以后节点左子节点是否为空！并且左子节点的值等于删除节点的值
- 判断以后节点右子节点是否为空！并且右子节点的值等于删除节点的值
- 判断删除节点的值是否小于以后节点的值，并且前节点左子节点不为空！
- 判断删除节点的值是否大于等于以后节点的值，并且前节点右子节点不为空！
public Node searchParent(int value){ //如果以后节点是须要删除节点的父节点则返回 if((this.left!=null && this.left.value == value) || (this.right!=null && this.right.value == value)){ return this; }else{ //如果查找的值小于以后节点的值，并且以后节点的左子节点不为空 if(value <this.value && this.left!=null){ return this.left.searchParent(value); }else if(value >= this.value && this.right!=null){ //如果查找的值大于等于于以后节点的值，并且以后节点的右子节点不为空 return this.right.searchParent(value); }else { return null;//没有找到父节点，比如说节点7 } }}咱们须要给BinarySortTree增加刚刚Node的办法调用
//查找须要删除节点的办法public Node search(int value){ if(root == null){ return null; }else{ return root.search(value); }}//查找须要删除节点的父节点信息public Node searchParent(int value){ if(root == null){ return null; }else{ return root.searchParent(value); }}二叉排序树删除节点代码实现
第一种状况：删除叶子节点
叶子节点特点：left == null && right ==null
public void delNode(int value){ if(root == null){ System.out.println("以后根节点为空！无奈删除节点！"); return; }else{ //1.须要先找到删除的值的对应节点 Node targetNode = search(value); //如果没有找到须要删除的节点 if(targetNode == null){ System.out.println("对不起！没有找到删除节点信息！"); return; } //如果咱们发现根节点没有左子节点与右子节点 if(root.left == null && root.right == null){ root = null; return; } //找到targetNode 的父节点 Node parent = searchParent(value); //如果删除节点是叶子节点 if(targetNode.left == null && targetNode.right == null){ //判断删除节点是父节点的左子节点还是右子节点 if(parent.left!= null && parent.left.value == targetNode.value){ parent.left = null; }else if (parent.right!= null && parent.right.value == targetNode.value){ parent.right = null; } } }}咱们在Demo里进行增加叶子节点：2 并测试看看吧！
public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; BinarySortTree binarySortTree = new BinarySortTree( ); //循环的增加结点到二叉排序树 for(int i = 0; i< arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); binarySortTree.delNode(2); System.out.println("删除叶子节点：2 后的数据================="); //中序遍历二叉排序树 binarySortTree.infixOrder(); binarySortTree.delNode(12); System.out.println("删除叶子节点：12 后的数据================="); //中序遍历二叉排序树 binarySortTree.infixOrder(); binarySortTree.delNode(9); System.out.println("删除叶子节点：9 后的数据================="); //中序遍历二叉排序树 binarySortTree.infixOrder();}运行后果如下：Node{value=1}Node{value=2}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}Node{value=12}删除叶子节点：2 后的数据=================Node{value=1}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}Node{value=12}删除叶子节点：12 后的数据=================Node{value=1}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}删除叶子节点：9 后的数据=================Node{value=1}Node{value=3}Node{value=5}Node{value=7}Node{value=10}第二种状况：删除有一颗子树的节点
有一颗子树的特点：left != null || right !=null
public void delNode(int value){ //省略第一种状况判断 /如果删除节点是叶子节点 if(targetNode.left == null && targetNode.right == null){ //.... }else if (targetNode.left != null && targetNode.right != null){ }else{//删除只有一颗子树的节点 //如果删除节点的子节点是左子节点 if(targetNode.left !=null){ //判断删除节点是父节点的左子节点还是右子节点 if(parent.left!= null && parent.left.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.left = targetNode.left; }else if (parent.right!= null && parent.right.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.right = targetNode.left; } }else if (targetNode.right != null){ //如果删除节点的子节点是右子节点 //判断删除节点是父节点的左子节点还是右子节点 if(parent.left!= null && parent.left.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.left = targetNode.right; }else if (parent.right!= null && parent.right.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.right = targetNode.right; } } } }}咱们在Demo删除携带一个子节点的节点1 测试看看是否胜利
public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; BinarySortTree binarySortTree = new BinarySortTree(); //循环的增加结点到二叉排序树 for (int i = 0; i < arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); binarySortTree.delNode(1); System.out.println("删除节点：1 后的数据================="); //中序遍历二叉排序树 binarySortTree.infixOrder();}运行后果如下：Node{value=1}Node{value=2}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}Node{value=12}删除叶子节点：1 后的数据=================Node{value=2}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}Node{value=12}第三种状况：删除有两颗子树的节点
有两颗子树的特点：left != null && right !=null
依照图解思路咱们须要增加一个办法
- 传入一个node，当做新二叉排序树的根节点
- 返回这根节点的最小值节点
- 删除最小值节点，返回它的value
/** * @param node 传入的节点（当做新二叉排序树的根节点） * return 返回新跟节点的最小节点的值 */ public int delRigthTreeMin(Node node){ Node target = node; //循环的查找左子节点，找到最小值 while(target.left!=null) { target = target.left; } //删除最小值 delNode(target.value); //返回最小值 return target.value;}public void delNode(int value){ //省略第一种状况判断 /如果删除节点是叶子节点 if(targetNode.left == null && targetNode.right == null){ //.... }else if (targetNode.left != null && targetNode.right != null){ int minValue = delRigthTreeMin(targetNode.right); targetNode.value = minValue;//重置值 }else{//删除只有一颗子树的节点 //省略第三种状况逻辑代码 }}public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; BinarySortTree binarySortTree = new BinarySortTree(); //循环的增加结点到二叉排序树 for (int i = 0; i < arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); binarySortTree.delNode(7); System.out.println("删除节点：7 后的数据================="); //中序遍历二叉排序树 binarySortTree.infixOrder();}运行后果如下：Node{value=1}Node{value=2}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}Node{value=12}删除叶子节点：7 后的数据=================Node{value=1}Node{value=2}Node{value=3}Node{value=5}Node{value=9}Node{value=10}Node{value=12}三、二叉排序树删除注意事项
如果咱们进行这样的删除程序，会呈现什么问题呢？
public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; BinarySortTree binarySortTree = new BinarySortTree(); //循环的增加结点到二叉排序树 for (int i = 0; i < arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); binarySortTree.delNode(2); binarySortTree.delNode(5); binarySortTree.delNode(9); binarySortTree.delNode(12); binarySortTree.delNode(7); binarySortTree.delNode(3); binarySortTree.delNode(10); binarySortTree.delNode(1); //中序遍历二叉排序树 binarySortTree.infixOrder(); }java.lang.NullPointerException at com.bdqn.it.tree.binarySearchTree.BinarySortTree.delNode(BinarySortTreeDemo.java:119) at com.bdqn.it.tree.binarySearchTree.BinarySortTreeDemo.main(BinarySortTreeDemo.java:23)那么是什么起因造成的？空指针？看看是什么起因造成的？
public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; BinarySortTree binarySortTree = new BinarySortTree(); //循环的增加结点到二叉排序树 for (int i = 0; i < arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); binarySortTree.delNode(2); binarySortTree.delNode(5); binarySortTree.delNode(9); binarySortTree.delNode(12); binarySortTree.delNode(7); binarySortTree.delNode(3); // binarySortTree.delNode(10); // binarySortTree.delNode(1); //中序遍历二叉排序树 System.out.println("删除后的数据================="); binarySortTree.infixOrder(); } 运行后果如下：Node{value=1}Node{value=2}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}Node{value=12}删除后的数据=================Node{value=1}Node{value=10}咱们发现此时的节点数据是Node{value=1}、Node{value=10}
再回来看删除有一个节点状况的逻辑代码
//如果删除节点的子节点是左子节点if(targetNode.left !=null){ //判断删除节点是父节点的左子节点还是右子节点 if(parent.left!= null && parent.left.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.left = targetNode.left; }else if (parent.right!= null && parent.right.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.right = targetNode.left; }}else if (targetNode.right != null){ //如果删除节点的子节点是右子节点 //判断删除节点是父节点的左子节点还是右子节点 if(parent.left!= null && parent.left.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.left = targetNode.right; }else if (parent.right!= null && parent.right.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.right = targetNode.right; }}有没有发现，若依据代码逻辑，咱们这里的节点十是没有parent的！会爆空指针！
//如果删除节点的子节点是左子节点if(targetNode.left !=null){ if(parent!=null){ //判断删除节点是父节点的左子节点还是右子节点 if(parent.left.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.left = targetNode.left; }else if (parent.right.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.right = targetNode.left; } }else{ root = targetNode.left; }}else if (targetNode.right != null){ //如果删除节点的子节点是右子节点 if(parent!=null){ //判断删除节点是父节点的左子节点还是右子节点 if( parent.left.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.left = targetNode.right; }else if (parent.right.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.right = targetNode.right; } }else{ root = targetNode.right; }}接下来咱们依据更正后的逻辑代码，测试看看是否还会造成空指针问题！
public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; BinarySortTree binarySortTree = new BinarySortTree(); //循环的增加结点到二叉排序树 for (int i = 0; i < arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 binarySortTree.infixOrder(); binarySortTree.delNode(2); binarySortTree.delNode(5); binarySortTree.delNode(9); binarySortTree.delNode(12); binarySortTree.delNode(7); binarySortTree.delNode(3); binarySortTree.delNode(10); binarySortTree.delNode(1); //中序遍历二叉排序树 System.out.println("删除后的数据================="); binarySortTree.infixOrder(); } 运行后果如下：Node{value=1}Node{value=2}Node{value=3}Node{value=5}Node{value=7}Node{value=9}Node{value=10}Node{value=12}删除后的数据=================以后二叉排序根节点为空，无奈遍历