二叉排序树（Binary Sort Tree）
前言： 二叉排序树是二叉树中十分重要的一种，又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
Node节点类代码
package day7_test; public class Node { public int val; public Node right; public Node left; /** * 查找要删除的节点并返回 * @param index 要删除的节点的val值 * @return 返回要删除的节点 */ public Node searchNode(int index){ if(this.val == index){ return this; }else if(index < this.val) { if(this.left == null){ return null; }else{ return this.left.searchNode(index); } }else { if (this.right == null){ return null; }else { return this.right.searchNode(index); } } } /** * 找到要删除的节点的父节点 * @param index 要删除的节点的索引 * @return 返回父节点 */ public Node searchParent(int index){ //情况一： 当前节点就是要删除节点的父节点 if((this.left != null && this.left.val == index) ||(this.right != null && this.right.val == index)){ return this; }else { //左节点不为空，并且左节点就是parent if(index < this.val && this.left != null){ return this.left.searchParent(index); }else if (index >= this.val && this.right != null){ return this.right.searchParent(index); }else { return null; } } } //添加节点 public void add(Node node){ if(node == null){ return; } if(node.val < this.val){ if(this.left == null){ this.left = node; }else{ this.left.add(node); } }else{ //node.val >= this.val if(this.right == null){ this.right = node; }else{ this.right.add(node); } } } //中序遍历二叉树 public void infix(){ if(this.left != null){ this.left.infix(); } System.out.println(this); if (this.right != null){ this.right.infix(); } } public Node(int val) { this.val = val; } @Override public String toString() { return "Node[" + "val=" + val + ']'; } }
二叉排序树的添加功能
思路：
每传进来一个node节点，我们就与当前节点进行比较
1.node的val值 < 当前节点的val值：
向左进行递归，一直递归到this.left == null时，加入node节点
2.node的val值 >= 当前节点的val值：
向右进行递归，知道this.right == null时，加入node节点
代码实现：
//添加节点 public void add(Node node){ if(node == null){ return; } if(node.val < this.val){ if(this.left == null){ this.left = node; }else{ this.left.add(node); } }else{ //node.val >= this.val if(this.right == null){ this.right = node; }else{ this.right.add(node); } } }
结果：
Node[val=0]
Node[val=1]
Node[val=3]
Node[val=5]
Node[val=7]
Node[val=9]
Node[val=10]
Node[val=12]
二叉排序树删除功能详解
思路：
首先分三种情况进行处理：
① 所删除的节点为叶子节点（left 和right 节点上为空）
② 所删除的节点为非叶子节点，并且left 或 right节点上只有一个不为空
③ 所删除的节点为非叶子节点，并且left 和 right 都不为空
在处理这三种情况之前，先再Node节点类中增添方法，用来查询要删除的目标节点targetNode 以及targetNode的父节点 parent节点
代码如下：
/** * 查找要删除的节点并返回 * @param index 要删除的节点的val值 * @return 返回要删除的节点 */ public Node searchNode(int index){ if(this.val == index){ return this; }else if(index < this.val) { if(this.left == null){ return null; }else{ return this.left.searchNode(index); } }else { if (this.right == null){ return null; }else { return this.right.searchNode(index); } } } /** * 找到要删除的节点的父节点 * @param index 要删除的节点的索引 * @return 返回父节点 */ public Node searchParent(int index){ //情况一： 当前节点就是要删除节点的父节点 if((this.left != null && this.left.val == index) ||(this.right != null && this.right.val == index)){ return this; }else { //左节点不为空，并且左节点就是parent if(index < this.val && this.left != null){ return this.left.searchParent(index); }else if (index >= this.val && this.right != null){ return this.right.searchParent(index); }else { return null; } } }
情况一：删除的是叶子节点
步骤：【
找到目标节点targetNode 及其它的父节点 parent
确定targetNode是parent的left节点 还是right 节点
parent.left = null 或 parent.right = null ;
】
代码：
Node targetNode = root.searchNode(index); if (targetNode == null){ System.out.println("没有找到要删除的节点！"); return; } if (root.left == null && root.right == null){ root = null; return; } Node parent = root.searchParent(index); //要删除的是叶子节点 if(targetNode.left == null && targetNode.right == null){ if(parent.left!= null && parent.left.val == targetNode.val){ parent.left = null; }else if(parent.right != null && parent.right.val == targetNode.val ) { parent.right = null; } }
情况二：要删除的节点只有一个子节点
步骤【
- 找到父节点和targetNode目标节点后
- 先判断targetNode的left 和right 是否为空 ，如果不为空再判断是否有parent节点，因为很可能这个节点是root节点 ，root节点没有parent节点
- 接下来就是四种判断
targetNode 有左节点 ，targetNode是parent的左节点；—–> parent.left = targetNode.left;
targetNode 有左节点 ，targetNode是parent的右节点；—–> parent.right = targetNode.left;
targetNode 有右节点 ，targetNode是parent的左节点；—–>parent.left = targetNode.right;
targetNode 有右节点 ，targetNode是parent的右节点；—–>parent.right = targetNode.right;
】
代码实现：
//要删除的节点只有一个子节点 else{ if(targetNode.left != null){ //要删除的节点有左子节点 if(parent != null){ if (parent.left == targetNode){ parent.left = targetNode.left; }else{ parent.right = targetNode.left; } }else { root = targetNode.left; } } else { if(parent != null){ if (parent.left == targetNode){ parent.left = targetNode.right; }else{ parent.right = targetNode.right; } }else { root = targetNode.right; } } }
情况三：要删除的节点只有一个子节点
这种情况我们有两种解决办法
步骤 【
方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点
方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点
】
代码实现：
//要删除的是有两个子节点的节点 else if (targetNode.left != null && targetNode.right !=null){ /* 方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点 方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点 */ // int tempMin = 0; // Node tempNode = targetNode.right; // while(tempNode.left != null){ // tempNode = tempNode.left; // } // tempMin = tempNode.val; // deleteNode(tempMin); // targetNode.val = tempMin; int tempMax = 0; Node tempNode = targetNode.left; while(tempNode.right != null){ tempNode = tempNode.right; } tempMax = tempNode.val; deleteNode(tempMax); targetNode.val = tempMax; }
main方法代码
public static void main(String[] args) { int arr[] ={7,3,10,12,5,1,9,0}; BinarySortTree b = new BinarySortTree(); for(int i=0;i<arr.length;i++){ b.add(new Node(arr[i])); } b.infix(b.root); b.deleteNode(3); b.deleteNode(12); b.deleteNode(5); b.deleteNode(1); b.deleteNode(7); b.deleteNode(9); b.deleteNode(10); b.deleteNode(0); System.out.println("删除之后~~~"); b.infix(b.root); }
整体代码实现：
package day7_test; public class BinarySortTree { public Node root; public static void main(String[] args) { int arr[] ={7,3,10,12,5,1,9,0}; BinarySortTree b = new BinarySortTree(); for(int i=0;i<arr.length;i++){ b.add(new Node(arr[i])); } b.infix(b.root); b.deleteNode(3); b.deleteNode(12); b.deleteNode(5); b.deleteNode(1); b.deleteNode(7); b.deleteNode(9); b.deleteNode(10); b.deleteNode(0); System.out.println("删除之后~~~"); b.infix(b.root); } /** * 删除二叉树节点 * @param index 要删除的节点的val值 */ public void deleteNode(int index){ if (root == null){ return; } else{ Node targetNode = root.searchNode(index); if (targetNode == null){ System.out.println("没有找到要删除的节点！"); return; } if (root.left == null && root.right == null){ root = null; return; } Node parent = root.searchParent(index); //要删除的是叶子节点 if(targetNode.left == null && targetNode.right == null){ if(parent.left!= null && parent.left.val == targetNode.val){ parent.left = null; }else if(parent.right != null && parent.right.val == targetNode.val ) { parent.right = null; } } //要删除的是有两个子节点的节点 else if (targetNode.left != null && targetNode.right !=null){ /* 方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点 方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点 */ // int tempMin = 0; // Node tempNode = targetNode.right; // while(tempNode.left != null){ // tempNode = tempNode.left; // } // tempMin = tempNode.val; // deleteNode(tempMin); // targetNode.val = tempMin; int tempMax = 0; Node tempNode = targetNode.left; while(tempNode.right != null){ tempNode = tempNode.right; } tempMax = tempNode.val; deleteNode(tempMax); targetNode.val = tempMax; } //要删除的节点只有一个子节点 else{ if(targetNode.left != null){ //要删除的节点有左子节点 if(parent != null){ if (parent.left == targetNode){ parent.left = targetNode.left; }else{ parent.right = targetNode.left; } }else { root = targetNode.left; } } else { if(parent != null){ if (parent.left == targetNode){ parent.left = targetNode.right; }else{ parent.right = targetNode.right; } }else { root = targetNode.right; } } } } } //添加节点 public void add(Node node){ if (root == null){ root = node; }else { root.add(node); } } //中序遍历 public void infix(Node root){ if (root == null){ System.out.println("空树！"); return; } root.infix(); } }
运行结果：
删除3 后
Node[val=0]
Node[val=1]
Node[val=5]
Node[val=7]
Node[val=9]
Node[val=10]
Node[val=12]
删除3,12,5,1 后
Node[val=0]
Node[val=7]
Node[val=9]
Node[val=10]
删除3,12,5,1,7,9 后
Node[val=0]
Node[val=10]
删除所有的之后
空树！
