一、概念
二叉搜索树:又称为二叉排序树,它或是一棵空树,或是一棵具有以下性质的二叉树:
(1)若它的左子树不为空,则左子树上的所有节点的值都小于根节点的值
(2)若它的右子树不为空,则右子树上的所有节点的值都大于根节点的值
(3)它的左右子树也分别是二叉搜索树
例如:
图中二叉搜索树中序遍历的结果:3 5 7 10 11 12 40
由于二叉搜索树的性质,二叉搜索树中序遍历的结果是升序
二、插入数据
若二叉搜索树为空树,则直接将节点放在根节点位置处。
若二叉搜索树不为空树,由二叉树的性质(左子树上的所有节点的值都小于根节点的值,右子树上的所有节点的值都大于根节点的值),可通过比较插入节点和当前节点cur的值,找到插入节点的位置
找到插入节点的位置后,要通过cur的父亲节点将插入节点连接起来,因此我们可以定义一个parent节点,指向cur的父亲节点,来帮助我们插入节点
若插入的值与二叉搜索树中节点的值相同,则插入失败,返回false
代码实现:
public class BinarySearchTree { static class Node{ private int val; private Node left; private Node right; public Node(int val){ this.val = val; } } //创建根节点 public Node root; //插入数据 public boolean insert(int val){ Node node = new Node(val); //根节点为空,直接将数据放在根节点位置 if(root == null){ root = node; return true; } //不为根节点,查找插入位置 Node cur = root; Node parent = null; while(cur != null){ if(node.val < cur.val){ parent = cur; cur = cur.left; }else if(node.val > cur.val){ parent = cur; cur = cur.right; }else {//若相等,则插入失败 return false; } } if(parent.val > node.val){ parent.left = node; }else{ parent.right = node; } return true; } }
三、查找数据
将待查找数据data与节点的值进行比较,若相同,则返回;若data小于节点的值,则向左子树继续查找;若data大于节点的值,则向右子树继续查找
代码实现:
public boolean search(int data){ if(root == null){//若根节点为null,无数据,直接返回false return false; } Node cur = root; while(cur != null){ if(data == cur.val){ return true; }else if(data < cur.val){ cur = cur.left; }else{ cur = cur.right; } } return false; }
四、删除数据
当删除二叉搜索树中节点时,需分情况删除
待删除节点为cur,其父亲节点为parent
1. cur.left = null
(1)若cur = root,则root = cur.right
(2)若cur != root 且 cur = parent.left ,则parent.left = cur.right
(3)若cur != root 且 cur = parent.right,则parent.right = cur.right
2. cur.right = null
(1)cur = root,则 root = cur.right
(2)cur != root 且 cur = parent.left,则parent.left = cur.left
(3)cur != root 且 cur = parent.right,则parent.right = cur.left
3. cur.left != null 且 cur.right != null
此时通过替换进行删除
由于cur中的数据比左子树大,比右子树小,因此我们可以在左子树中寻找最大的数据(即左子树中最右边的数据),或是在右子树寻找最小的数据(即右子树中最左的数据),用找到的值替换掉cur,再删除找到的值
由于替换的值为右子树最左的节点(或左子树最右的节点),此时删除的情况变为 2 中的(2)或(3)(或是 1 中的(2)或(3)),便于删除
代码实现:
public boolean remove(int key){ Node cur = root; Node parent = null; while(cur != null){ //找到需删除节点 if(cur.val < key){ parent = cur; cur = cur.right; }else if(cur.val > key){ parent = cur; cur = cur.left; }else {//找到了,开始删除 removeNode(cur,parent); return true; } } //未找到,删除失败 return false; } private void removeNode(Node cur, Node parent){ if(cur.left == null){ if(cur == root){ root = cur.right; }else if(parent.left == cur){ parent.left = cur.right; }else{ parent.right = cur.right; } }else if(cur.right == null){ if(cur == root){ root = cur.left; }else if(parent.left == cur){ parent.left = cur.left; }else{ parent.right = cur.left; } }else { Node targetParent = cur; Node target = cur.right; //在cur的右子树查找最小值 while(target.left != null){ targetParent = target; target = target.left; } //将cur的值替换为target的值 cur.val = target.val; if(targetParent.left == target){ targetParent.left = target.right; }else { targetParent.right = target.right; } } }