二叉树搜索
/**
* @Author: wangshiyu javapub rodert
* @Date: 2021/3/28 16:11
*/
public class BSTree {
//定义Node类
public static class Node {
int val;
Node left;
Node right;
Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
//定义根节点
private Node root = null;
//查找
public Node find(int val) {
if (root == null) {
return null;
}
Node cur = root;
while (cur != null) {
if (cur.val == val) {
return cur;
} else if (cur.val > val) {
cur = cur.left;
} else {
cur = cur.right;
}
}
return null;
}
// 插入
// 新的节点都是插入在叶子节点或者不完全的子树上
public boolean insert(int val) {
if (root == null) {
root = new Node(val);
return true;
}
Node cur = root;
Node parent = null;
//搜索要插入的位置
while (cur != null) {
parent = cur;
if (cur.val == val) {
//保证插入的节点不重复
return false;
} else if (cur.val > val) {
cur = cur.left;
} else {
cur = cur.right;
}
}
// 找到了合适的位置,根据与父节点的大小关系建立连接
Node node = new Node(val);
if (val > parent.val) {
parent.right = node;
} else {
parent.left = node;
}
return true;
}
//删除
public boolean remove(int val) {
if (root == null) {
return false;
}
Node cur = root;
Node parent = null;
// 搜索要删除的节点
while (cur != null) {
if (cur.val == val) {
break;
} else if (cur.val > val) {
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
if (cur == null) {
return false;
} else {
remove(parent, cur);
return true;
}
}
public void remove(Node parent, Node cur) {
if (cur.left == null) {
if (cur != root) {
if (parent.left == cur) {
parent.left = cur.right;
} else {
parent.right = cur.right;
}
} else {
root = cur.right;
}
} else if (cur.right == null) {
if (cur != root) {
if (parent.left == cur) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
} else {
root = cur.left;
}
} else {
// 左右都不为空选取一个新的节点作为子树的根
// 1.左子树的最右节点 ---> 大于左子树中的所有节点,小于右子树中的所有节点
// 2.右子树的最左节点 ---> 小于右子树中的所有节点,大于左子树中的所有节点
// 以下为选取左子树的最右节点
parent = cur;
Node next = cur.left;
while (next.right != null) {
parent = next;
next = next.right;
}
cur.val = next.val;
if (parent.left == next) {
parent.left = next.left;
} else {
parent.right = next.left;
}
}
}
public void inOrder() {
inOrderInternal(root);
System.out.println();
}
private void inOrderInternal(Node root) {
if (root != null) {
inOrderInternal(root.left);
System.out.print(root.val + " ");
inOrderInternal(root.right);
}
}
public static void main(String[] args) {
BSTree bs = new BSTree();
bs.insert(10);
bs.insert(5);
bs.insert(6);
bs.insert(8);
bs.insert(3);
bs.insert(7);
bs.insert(2);
bs.insert(6);
bs.insert(11);
bs.insert(14);
bs.insert(12);
bs.insert(13);
bs.inOrder();
bs.remove(3);
bs.inOrder();
bs.remove(14);
bs.inOrder();
bs.remove(2);
bs.inOrder();
bs.remove(10);
bs.inOrder();
}
}